JavaScirpt基础-数组排序之快速排序

JavaScirpt基础-数组排序之快速排序

快速排序

快速排序的基本思想是通过一趟排序，将待排记录分隔成独立的两部分，
其中一部分记录的关键字均比另一部分的关键字小，
则可以分别对这两部分记录继续进行排序，以达到整个序列有序。

var a = [1, 3, 6, 38, 23, 64, 2, 34, 222, 6, 456, 221, 73];
function quickSort(array) {
var quick = function(arr) {

if (arr.length <= 1) return arr
const len = arr.length
const index = Math.floor(len >> 1)
const pivot = arr.splice(index, 1)[0]
const left = []
const right = []
for (let i = 0; i < len; i++) {
  if (arr[i] > pivot) {
    right.push(arr[i])
  } else if (arr[i] <= pivot) {
    left.push(arr[i])
  }
}
return quick(left).concat([pivot], quick(right))

}
const result = quick(array)
return result
}

quickSort(a);// [1, 2, 3, 6, 6, 23, 34, 38, 64, 73, 221, 222, 456]