快速排序

一、原理解析

快速排序使用分治法策略来把一个序列分为两个子序列。

步骤为:

  1. 从数列中挑出一个元素,称为“基准”,
  2. 重新排序数列,所有比基准值小的元素摆放在基准前面,所有比基准值大的元素摆在基准后面(相同的数可以到任何一边)。在这个分区结束之后,该基准就处于数列的中间位置。这个称为分区(partition)操作。
  3. 递归地(recursively)把小于基准值元素的子数列和大于基准值元素的子数列排序。
  4. 递归到最底部时,数列的大小是零或一,也就是已经排序好了。这个算法一定会结束,因为在每次的迭代(iteration)中,它至少会把一个元素摆到它最后的位置去。

以下是 JavaScript 版本的的代码实现:

function quickSort(arr) {
  if(arr.length <= 1) {
    return arr
  }
  let leftArr = [] 
  let rightArr = []
  for(let i = 1; i < arr.length; i++) {
    if(arr[i] >= arr[0]) {
      rightArr.push(arr[i])
    } else {
      leftArr.push(arr[i])
    }
  }
  return quickSort(leftArr).concat(arr[0]).concat(quickSort(rightArr))
}
 
var arr = [10, 34, 21, 47, 3, 28]
quickSort(arr)
console.log(arr)

上面quickSort 函数内每次执行新创建两个数组,多次递归后会创建大量数组,在空间上存在"浪费"。我们可以在原数组上操作

function quickSort(arr) {
  function _quickSort(arr, start, end) {
    if(start >= end) return
    let key = arr[end]
    let left = start, right = end - 1
    while(left < right) {
      while(arr[left] < key && left < right) left++
      while(arr[right] >= key && left < right) right--
      [arr[left], arr[right]] = [arr[right], arr[left]]
    }
    if(arr[left] >= arr[end]) { 
      [arr[left], arr[end]] = [arr[end], arr[left]]
    } else {  // 如 [2, 1, 3, 4]
      left++
    }
    _quickSort(arr, start, left - 1)
    _quickSort(arr, left + 1, end)
  }
  _quickSort(arr, 0, arr.length - 1)
  return arr
}

讲过上面的处理后,就会把数组变成以原数组末尾数字为分割(左边都比它小,右边都比它大)的数组。然后分别对参考值左侧和右侧通过类似的逻辑继续处理。

二、效率测试

下面我们测试排序性能

let arr = randomArr(10000, 100)
console.time('quickSort')
quickSort(arr)
console.timeEnd('quickSort')
 
 
function randomArr( arrLen = 100, maxValue = 1000 ) {
  let arr = []
  for(let i = 0; i < arrLen; i++) {
    arr[i] = Math.floor((maxValue+1)*Math.random())
  }
  return arr
}
 
function quickSort(arr) {
  function _quickSort(arr, start, end) {
    if(start >= end) return
    let key = arr[end]
    let left = start, right = end - 1
    while(left < right) {
      while(arr[left] < key && left < right) left++
      while(arr[right] >= key && left < right) right--
      [arr[left], arr[right]] = [arr[right], arr[left]]
    }
    if(arr[left] >= arr[end]) { 
      [arr[left], arr[end]] = [arr[end], arr[left]]
    } else {  // 如 [2, 1, 3, 4]
      left++
    }
    _quickSort(arr, start, left - 1)
    _quickSort(arr, left + 1, end)
  }
  _quickSort(arr, 0, arr.length - 1)
  return arr
}

经浏览器测试,对于长度为10000的数组,排序约需要2.67ms(100次平均值), 对于长度为100000的数组,排序约需要 94ms(100次样本平均值)。

三、复杂度分析

时间复杂度为 O(nlogn)

四、参考

https://link.zhihu.com/?target=https%3A//zh.wikipedia.org/wiki/%25E5%25BF%25AB%25E9%2580%259F%25E6%258E%2592%25E5%25BA%258F

饥人谷一直致力于培养有灵魂的编程者,打造专业有爱的国内前端技术圈子。如造梦师一般帮助近千名不甘寂寞的追梦人把编程梦变为现实,他们以饥人谷为起点,足迹遍布包括facebook、阿里巴巴、百度、网易、京东、今日头条、大众美团、饿了么、ofo在内的国内外大小企业。 了解培训课程:加微信 xiedaimala03,官网:https://jirengu.com

本文作者:饥人谷若愚老师