一个先递增后递减的数组，如何排序最简单

Question

例如

var arr = [1, 3, 6, 10, 2, 7, 9];

排序后

var arr = [1, 2, 3, 6, 7, 9, 10];

！！！特别说明，我没写错！！！ 不是你们以为的先递增后递减！！！ 那些想当然还踩别人题目的 怕不是常规题做多了！！！！

这是我出去面试的时候碰见的，那个人特地强调不是先增后减！！！

!!!不能用sort方法 ，纯原生的方法写

Answer 1

你的例子写错了吧，难道不应该是var arr = [1, 3, 6, 10, 9, 7, 2];这样的话，维护两个指针，一个从其往后，一个从后往前，谁小排谁，两个指针遇到了，就全排好了。

Answer 2

let arr = [1, 3, 6, 10, 9, 7, 2];function trans (arr) {&nbsp; let i = 0&nbsp; let j = arr.length - 1&nbsp; let result = []&nbsp; while (i <= j) {&nbsp; &nbsp; if (arr[i] <= arr[j]) {&nbsp; &nbsp; &nbsp; result.push(arr[i++])&nbsp; &nbsp; } else {&nbsp; &nbsp; &nbsp; result.push(arr[j--])&nbsp; &nbsp; }&nbsp; }&nbsp; return result}trans(arr)

Answer 3

如果确定时先递增再递减的数组, 直接头尾合并 时间复杂度 o(n)思路let i=0let j=arr.length-1let newArr = []if(arr[i]<arr[j]){&nbsp; &nbsp; newArr.push(arr[i++])}else{&nbsp; &nbsp; newArr.push(arr[j--])}加个循环 一遍就能排好