老规矩,还是先回顾下排序算法的种类

本篇文章准备聊聊其中的 快速排序,废话不多说,开搞!

ppx.jpg

快速排序的简述

从这个算法的名字我们就可以知道它的特点就是 快,效率高,因此它的平均时间复杂度只有 **O(nlogn)**,但空间复杂度为 **O(logn)**,且 不是 一种稳定的算法

由于其高性能,因此实际开发中应该使用此法解决数据排序的相关问题,所以一定要掌握

算法的稳定性指的是如果在某一无序集合中a=b,且a在b前面,经过排序后,如果a依旧在b前面,那么可以认为使用的排序算法是稳定的,反之,就是不稳定的

快速排序的实现过程

快速排序是利用 分治 的思想对数据进行排序的,以升序为例,实现的关键点如下

  1. 首先需要确定一个 基准元素,通常可以选择 最后 一个元素、
  2. 以基准元素为依据,所有比它小的元素放左边,所有比它大的元素放右边
  3. 然后 递归地 对左右两边的数据序列重复2步骤
  4. 直到最后待排序的序列的元素个数为1时,证明子序列排序完毕,跳出递归
  5. 所有子序列排序完毕,就代表整个序列排序完毕,就此完成排序过程

下面给出代码示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function quickSort(arr,left,right) {
if(right - left < 1){
return arr
}
let index = left,base = arr[right]
for(let i = left;i <= right;i++) {
if(arr[i] <= base) {
[arr[i],arr[index]] = [arr[index],arr[i]]
index++
}
}
quickSort(arr,left,index-2)
quickSort(arr,index,right)

return arr
}

上面给出的示例是 不占用 额外空间的方案,下面再给出一个 需要占用 额外空间的例子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function quickSort(arr) {
if(arr.length < 2) {
return arr
}
let index = arr.length - 1
let base = arr[index]
let left = arr.filter((item,indexInner)=>{
return item <= base && index !== indexInner
})
let right = arr.filter((item,indexInner)=>{
return item > base && index !== indexInner
})

return [...quickSort(left),base,...quickSort(right)]
}

结语

快速排序是一种高效的算法,在遇到数据排序的场景时,应该优先想到使用此法进行解决,好啦,就到这啦,over!