头条前端面经之算法题,快速排序

2018年9月, 头条前端面试, 手写快速排序算法

快速排序于1960年提出,是目前公认的最快的排序算法

快速排序

快速排序的基本思想是:

1、先从待排序列中取出一个数作为基准数(一般可以取第一个数)
2、通过比较分区,将比这个基准数大的全部替换到基准数右边,比它小的数放到左边
3、重复步骤1、2的过程,对基准数左边的区间和右边的区间,继续分区

经过一些列的递归分治过程,最后完成排序

我们来举个例子来看下:
假设序列是 34 1 45 21 89 76 23 5 38

第一步
取基准数 34
从右向左,找到第一个比 34 小的,然后替换:
[5] 1 45 21 89 76 23 [34] 38

第二步
从左向右,找到第一个比 34 大的,然后替换:
5 1 [34] 21 89 76 23 [45] 38

第三步
继续重复上面的两个过程,最后得到:
5 1 23 21 34 76 89 45 38

基准数左边 和 右边区间:
[5 1 23 21] 34 [76 89 45 38]

第四步
对左边区间继续执行第一、二、三步:5 1 23 21
对右边区间继续执行第一、二、三步:76 89 45 38

最后
1 5 21 23 34 38 45 76 89

排序完成

一定要仔细理解这些步骤的意义
下面我们来看下代码实现

代码实现

我们线来先一个分区函数,这个函数功能就是实现比基准数大的在它右边,比它小的在它左边

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
* 函数分区
* @param arr: 原始数组序列
* @param left: 待排序列在原数组的起始下标
* @param right: 待排序列在原数组的结尾下标
* @return 分区后基准数的下标索引
*/
function partition(arr, left, right) {
let observe = arr[left]

while (left < right) {
while (arr[right] > observe && left < right) {
right --;
}

arr[left] = arr[right]

while (arr[left] <= observe && left < right) {
left ++;
}

arr[right] = arr[left]
}

arr[left] = observe

return left
}

我们执行一次看下

1
2
3
4
5
let arr = [34, 12, 56, 3, 19, 90, 39, 2, 45]
partition(arr, 0, arr.length - 1)

arr
// [2, 12, 19, 3, 34, 90, 39, 56, 45]

基准数 34 左侧都比其小,右侧比其大

接下来我们看下分治法递归实现分区后的左侧区间和右侧区间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
* 可以理解为快排排序算法入口
*/
function quickSort(arr) {
qsort(arr, 0, arr.length - 1)
}

// 分治法
function qsort(arr, left, right) {
if (left >= right) {
return
}
// 先执行一次分区
let p = partition(arr, left, right)

// 然后排序分区后的左侧小区间
qsort(arr, left, p - 1)

// 最后排序分区后的右侧大区间
qsort(arr, p + 1, right)
}

测试一番

1
2
3
4
5
let arr = [34, 2, 45, 23, 12, 56, 90, 100, 58, 31]
quickSort(arr)

arr
// [2, 12, 23, 31, 34, 45, 56, 58, 90, 100]

仔细理解吧

算法复杂度

我们来看下快排的时间复杂度:O(nlog2(n))

相比较其它一些排序算法(冒泡排序、选择排序、插入排序等),他们的时间复杂度是 O(n*n)

更多前端面试题和算法题,请搜索微信小程序 前端面试精华
前端面试精华
前端面试精华

坚持原创技术分享,您的支持将鼓励我继续创作!