高级排序 (in-place)

要解决问题: 交换位置递归的同时不增加内存的开销


function inPlace(arr) {
// 交换值
let _swap = function(arr, i, j) {
let temp = arr[i]
arr[i] = arr[j]
arr[j] = temp
}
// left 是起始位置, right
let _findCenterIdx = function(arr, left, right) {
let flag = arr[left]
let idx = left + 1 // 即将发生交换的下标位置
for (let i = idx; i <= right; i++) {
if (arr[i] < flag) {
_swap(arr, idx, i)
idx++  // 交换后往下移一位
}
}
_swap(arr, left, idx - 1)  // 第一轮结束后,将这一轮作为对比值与下标的上一位进行交换, 从而使idx 左边部分都是有序且小于idx下标对应的值
return idx
}

let _sort = function (arr, left, right) { if (left < right) { let center = _findCenterIdx (arr, left, right) // 找到第一轮结束后的下标(用于交换)位置 _sort(arr, left, center - 1) // 左边 _sort(arr, center, right) // 右边 } } _sort(arr, 0, arr.length-1) return arr }



test: [3,44,38,5,47,15,36,26,27,2,46,4,19,50,48]

lynhao / day-by-day

高级排序 (in-place) #8

快速排序之高级排序 (in-place)