Open toFrankie opened 1 year ago
快速排序,简称 快排,是最常见的算法之一。桶排序 虽然快,但是空间消耗大,冒泡排序 利用的空间较为合理但是 O(n²),显然在数据量较大时不够快。快速排序 算是从两者取长补短的算法。
快速排序
快排
桶排序
冒泡排序
O(n²)
以升序为例:
基准数
arr1
arr2
0~1
function sort(arr) { // 设置递归出口 if (arr.length <= 1) return arr // 设置基数,并将基数移出 let base = Math.floor(arr.length / 2) let baseValue = arr.splice(base, 1)[0] // 临时数组。1)小于等于基数放入 arr1;2)大于放入基数放入 arr2 let arr1 = [] let arr2 = [] for (let i = 0; i < arr.length; i++) { if (arr[i] <= baseValue) { arr1.push(arr[i]) } else { arr2.push(arr[i]) } } // 递归 return sort(arr1).concat([baseValue], sort(arr2)) } let array = [4, 9, 3, 6, 21, 5, 0, 30, 2, 14] console.log(sort(array)) // [0, 2, 3, 4, 5, 6, 9, 14, 21, 30]
快速排序的平均时间复杂度为 O(nlogn),快速排序的时间复杂度计算较为复杂。
O(nlogn)
有兴趣的同学可参考:如何证明快速排序法的平均复杂度为 O(nlogn)? 可以看到的是 快速排序 的时间复杂度是介于 桶排序 O(n) 和 冒泡排序 O(n^2) 之间的: O(1) < O(logn) < O(n) < O(n*logn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)。
桶排序 O(n)
冒泡排序 O(n^2)
O(1) < O(logn) < O(n) < O(n*logn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)
快速排序
,简称快排
,是最常见的算法之一。桶排序
虽然快,但是空间消耗大,冒泡排序
利用的空间较为合理但是O(n²)
,显然在数据量较大时不够快。快速排序
算是从两者取长补短的算法。原理
以升序为例:
基准数
。(一般习惯选择中间的数,但选择其他数也可以)arr1
,大于放到一个临时数组arr2
。arr1
或arr2
只有0~1
个则当前数组退出。arr1
,arr2
执行步骤 1、2、3。(即递归实现)图示
实现
时间复杂度
快速排序的平均时间复杂度为
O(nlogn)
,快速排序的时间复杂度计算较为复杂。有兴趣的同学可参考:如何证明快速排序法的平均复杂度为 O(nlogn)? 可以看到的是
快速排序
的时间复杂度是介于桶排序 O(n)
和冒泡排序 O(n^2)
之间的:O(1) < O(logn) < O(n) < O(n*logn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)
。