JavaScript的排序算法——快速排序
2019-01-15 本文已影响41人
流浪的三鮮餡
快速排序（Quicksort）
快速排序（Quicksort）是对冒泡排序的一种改进。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
快速排序（Quicksort）
复杂度
| 算法 | 最好情况 | 平均情况 | 最坏情况 | 空间复杂度 | 稳定性 |
|---|---|---|---|---|---|
| 快速排序 | O(n log n) | O(n log n) | O(n2) | O(log n) | 不稳定 |
ES6 实现
function QuickSort(array) {
const sort = (arr, left = 0, right = arr.length - 1) => {
if (left >= right) {
return array;
}
let i = left;
let j = right;
const baseVal = arr[j] ;
while (i < j) {
while (i < j && arr[i] <= baseVal) {
i++;
}
arr[j] = arr[i] ;
while (j > i && arr[j] >= baseVal) {
j--;
}
arr[i] = arr[j] ;
}
arr[j] = baseVal ;
sort(arr, left, j-1) ;
sort(arr, j+1, right) ;
}
const newArr = array.concat() ;
sort(newArr);
return newArr;
}
参考
相关阅读
JavaScript的排序算法——冒泡排序
JavaScript的排序算法——选择排序
JavaScript的排序算法——插入排序
JavaScript的排序算法——归并排序
JavaScript的排序算法——快速排序
