logo

排序算法之冒泡排序,快速排序

冒泡排序(Bubble Sort)

冒泡排序的思路是每次遍历比较找出最大(小)的值并排在最后(前)。

步骤(升序)

  1. 所有元素视为未排序序列
  2. 从未排序序列的第一个元素开始,对每一对未排序序列的相邻元素做比较,如果之前的元素大于之后的元素则交换两个元素。一轮比较完后,未排序序列的最后的元素视为已排序序列的元素。
  3. 重复步骤二直到剩下最后一个未排序元素,结束排序。

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
function bubbleSort(arr) {
let len = arr.length;
for (let i = len - 1; i > 0; i--) {
for (let j = 0; j <= i; j++) {
if (arr[j] > arr[j + 1]) {
let temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
return arr;
}

分析

排序方式为 In-Place(原地)排序,因此空间复杂度为 $O(1)$

  • 最佳情况:序列升序,长度为 $n$ 的序列比较 $\sum_{i=1}^{n-1}{i}\Longrightarrow\frac{n(n-1)}{2}$ 次,交换 $0$ 次,时间复杂度为 $O(n^2)$
  • 最差情况:序列倒序,长度为 $n$ 的序列比较 $\sum_{i=1}^{n-1}{i}\Longrightarrow\frac{n(n-1)}{2}$ 次,交换$\sum_{i=1}^{n-1}{i}\Longrightarrow\frac{n(n-1)}{2}$次,时间复杂度为$O(n^2)$

平均时间复杂度为$O(n^2)$,相等元素排序位置固定,稳定排序。
对于已排序序列冒泡排序时间复杂度也为$O(n^2)$,而插入排序只需要$O(n)$,因此虽然两个算法平均时间复杂度相同,插入排序算法也是优于冒泡排序算法

优化

设置是否发生交换,最后交换位置的 flag

外层循环优化,交换 flag 默认为 false,如果在一趟排序中未发生交换则表示序列有序,停止排序,使得最佳算法复杂度为$O(n)$。
内层循环优化,记录最后交换发生的位置,表示该位置之后的元素均为有序且无需比较,内存循环只需要比较到最后交换位置即可。
虽然这种算法优化了序列有序或者部分有序的处理情况,但是序列完全随机情况下,由于对 flag 的处理会增加额外的性能损耗导致性能不如优化之前。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
function bubbleSortWithFlag(arr) {
let len = arr.length;
/* 外层循环,此轮遍历是否发生交换 */
let isExchange = false;
/* 内层循环,记录最后一次交换的位置 */
let lastExchangePos = len - 1;
let k = len - 1;
for (let i = len - 1; i > 0; i--) {
for (let j = 0; j <= k; j++) {
if (arr[j] > arr[j + 1]) {
let temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
isExchange = true;
lastExchangePos = j;
}
}
k = lastExchangePos;
if (!isExchange) {
break;
}
}
return arr;
}

快速排序(Quick Sort)

快速排序采用分而治之的策略,减少比较次数,是对于大的、随机数列表是最快的已知排序方法。

步骤(Out-Place,升序)

  1. 选择第一个元素为基准值
  2. 大于基准值的放在一个数组 1,小于基准值的放在一个数组 2
  3. 递归对每个数组 1,数组 2 执行步骤 1,2,直到所有数组长度为 1,递归向上连接所有数组返回结果

实现(Out-Place)

1
2
3
4
5
6
7
8
9
10
11
12
13
function quickSort(arr) {
let len = arr.length;
if (len <= 1) {
return arr;
}
let pivot = arr[0],
left = [],
right = [];
for (let i = 1; i < len; i++) {
arr[i] >= pivot ? right.push(arr[i]) : left.push(arr[i]);
}
return [...quickSort(left), pivot, ...quickSort(right)];
}

分析

排序方式为 Out-Place 排序,因此空间复杂度为 $O(n)$

  • 最佳情况:每次基准值为数组中位数,每次都均匀分组,调用深度 $O(\log{n})$, 此时时间复杂度限制在$O(nlog{n})$以下
  • 最差情况:待排序序列为正序或者逆序,每次分组都为一个空数组一个全部数组,此时调用深度为$O(n-1)$,此时关键比较语句执行$\sum_{i=1}^{n-1}{i}\Longrightarrow\frac{n(n-1)}{2}$次,
    时间复杂度为$O(n^2)$

平均时间复杂度为$O(n\log{n})$,相等元素排序位置不固定,不稳定排序。
快速排序有更高的空间复杂度,更低的时间复杂度,适合大量随机元素排序,不适合大致有序的序列排序。

优化

优化空间复杂度,采用原地排序的方式。

快速排序

步骤(In-Place,升序)

  1. 选择第最后一个元素为基准值
  2. 将元素通过交换分为小于基准值的小数区域,以及大于基准值的大数区域,将基准值与第一个大数区域第一个值交换。
  3. 对小区域以及基准值与大数区域组成的区域执行步骤 1~2,直到所有排序区域值只有 1 个。

实现

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
function quickSortInPlace(arr, start, end) {
if (start < end) {
/* 基准值 */
let pivot = arr[end - 1];
/* 标记位置,确保左边的数都小于基准值 */
let exchangePos = start;
/* 遍历从start到end-2的元素,依次与基准值比较 */
for (let i = start; i < end - 1; i++) {
/* 小于基准值与exchangePos位置元素交换,
exchangPos向后移动一位,
这样exchangPos左边的值都小于基准值 */
if (arr[i] < pivot) {
let temp = arr[i];
arr[i] = arr[exchangePos];
arr[exchangePos] = temp;
exchangePos++;
}
}
/* 最后exchangPos位置的元素一定大于基准值,交换exchangPos元素与基准值 */
arr[end - 1] = arr[exchangePos];
arr[exchangePos] = pivot;
/* 分别对基准值两边的元素进行递归排序,不包括基准值 */
quickSortInPlace(arr, exchangePos + 1, end);
quickSortInPlace(arr, start, exchangePos);
}
}

分析

排序方式为 In-Place 排序,这个版本主要优化了空间复杂度。
采用二分递归排序,最坏情况下数组倒序/正序此时$n$次递归调用,空间复杂度为$O(n)$,平均空间复杂度为 $O(\log{n})$

总结

Chorme72 性能测试

10000 个数测试代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function test(time) {
let tempTime = time;
let result = [];
while (time > 0) {
var n = 10000;
var arr = Array.from({
length: n
}).map(() => Math.round(Math.random() * n));

var start, end;
start = performance.now();

/* arr = quickSort(arr) */
/* quickSortInPlace(arr,0,arr.length) */
SortMethod();

end = performance.now();
result.push(end - start);
time--;
}
return result.reduce((a, b) => a + b) / tempTime;
}
test(10);
排序方法10 次平均时间(ms)
冒泡排序220.959ms
冒泡排序优化240.029ms
快速排序(out-place)3.680ms
快速排序(in-place)1.721ms

快速排序性能远远优于冒泡排序。

综合比较

排序方法平均时间复杂度最佳时间复杂度最差时间复杂度空间复杂度稳定性排序方式
冒泡排序$O(n^2)$$O(n^2)$$O(n^2)$$O(1)$稳定In-Place
冒泡排序优化$O(n^2)$$O(n)$$O(n^2)$$O(1)$稳定In-Place
快速排序(out-place)$O(n\log{n})$$O(n\log{n})$$O(n^2)$$O(n)$不稳定Out-Place
快速排序(in-place)$O(n\log{n})$$O(n\log{n})$$O(n^2)$$O(\log{n})$不稳定In-Place

参考链接