排序方法简介 | BarryZed的个人博客

type

status

date

slug

summary

稳定排序(Stable Sort)

插入排序(Insertion Sort)

一句话解释：抓扑克牌。将原序列看为两部分，已排序区和未排序区，每次从未排序区取一个元素，插进已排序区的正确位置。

例子

[8, 5, 3, 7, 6] ，升序排列

将第0个位置的元素（8）视作已排序

[8 | 5, 3, 7, 6]

取未排序区的一个元素（5）插入排序区

比 8 小 → 插到 8 之前

[5, 8 | 3, 7, 6]

取未排序区的一个元素（3）插入排序区

比 8 小 → 插到 8 之前
比 5 小 → 插到 5 之前

[3, 5, 8 | 7, 6]

…以此类推，直到未排序区长度 = 0

特点：

原地排序
时间复杂度

平均状况 O(n²)
最好情况（已排序） O(n)
最坏情况（逆序） O(n²)

不稳定排序(Unstable Sort)

选择排序(Selection Sort)

一句话解释：每一趟从未排序部分中选出最小（或最大）元素，放到它“应该在的位置上”。 该放的位置可以简单理解成已排序的部分的最后一个。

例子

[ 5, 3, 4, 1, 2 ] ，升序排列

先找到最小值 1 ，放到第0个位置

[ 1 | 3, 4, 5, 2 ]

在 | 右面的找到最小的 2 ，放到第1个位置

[ 1, 2 | 4, 5, 3 ]

…以此类推，直到剩余序列长度 = 0

特点：

比较次数固定

无论原序列是什么样子，比较次数恒为 n(n-1)/2
时间复杂度恒为O(n²)

每次最多交换1次

快速排序(Quick Sort)

一句话解释：选择一个基准，把比它小的放到它左边，比它大的放到它右边；然后开始递归，直到每个子序列长度长度小于等于1。

例子

[ 5, 3, 8, 4, 2, 7, 1 ] ，升序排列

选择基准 5 ，比5小的去左边，比5大的去右边（一般如果有相同元素会特别写相同元素怎么处理，这里先不考虑相同元素）

[ 3, 4, 2, 1 | 5 | 8, 7 ] = 现在有两个序列 [ 3, 4, 2, 1 ] 和 [ 8, 7 ]

左侧序列选则基准为 3

左侧序列变为： [ 2, 1 | 3 | 4 ]

…递归直到所有子序列长度小于等于1

特点：

“快”

每次分区都会近似折半
平均时间复杂度 O(nlogn)
最坏时间复杂度 O(n²)

原地排序

需要的额外空间小

希尔排序(Shell Sort)

一句话解释：“分组插入排序”的升级版，通过先让相隔一定间距(gap)的元素进行插入排序，逐渐缩小间距，最后整体插入排序。 相隔一定间距(gap)的元素进行插入排序：可以简单理解为将间隔为gap的元素取出形成一个新序列，对新序列进行插入排序，然后将排好序的新序列按顺序插回原序列的空位中。

在插入排序中，gap永远为1

例子

[8, 9, 1, 7, 2, 3, 5, 4, 6, 0] ，升序排列

gap = 5 → 分组

下标 % 5 相同的归一组：

组 1：8,3

处理 8 → 已排序，保持原位

处理 3 → 插入已排序部分：

3 < 8 → 交换

组内排序结果：

[3, 9, 1, 7, 2, 8, 5, 4, 6, 0]

组 2：9,5

处理 9 → 已排序

处理 5 → 插入已排序部分：

5 < 9 → 交换

组内排序结果：

[3, 5, 1, 7, 2, 8, 9, 4, 6, 0]

组 3：1,4

处理 1 → 已排序

处理 4 → 插入已排序部分：

4 > 1 → 插入在 1 后

组内排序结果：

[3, 5, 1, 7, 2, 8, 9, 4, 6, 0]

组4：7,6

处理 7 → 已排序

处理 6 → 插入已排序部分：

6 < 7 → 交换

组内排序结果：

[3, 5, 1, 6, 2, 8, 9, 4, 7, 0]

组 5：2,0

处理 2 → 已排序

处理 0 → 插入已排序部分：

0 < 2 → 交换

组内排序结果：

[3, 5, 1, 6, 0, 8, 9, 4, 7, 2]

gap = 5结束，gap = 2 → 分组

下标 % 2 相同的归一组：

组 1：3,1,0,9,7

处理 3 → 已排序

处理 1 → 插入已排序部分：

1 < 3 → 交换

组内状态：1,3

处理 0 → 插入已排序部分：

0 < 1 → 交换

组内状态：0,1,3

处理 9 → 插入已排序部分：

9 > 3 → 插入在 3 后

组内状态：0,1,3,9

处理 7 → 插入已排序部分：

7 < 9 → 移动 9
7 > 3 → 插入在 3 后

组内状态：0,1,3,7,9

数组对应位置（下标 0,2,4,6,8）：

[0, 5, 1, 6, 3, 8, 7, 4, 9, 2]

组 2：5,6,8,4,2

处理 5 → 已排序

处理 6 → 插入已排序部分：

6 > 5 → 插入后不动

组内状态：5,6

处理 8 → 插入已排序部分：

8 > 6 → 插入后不动

组内状态：5,6,8

处理 4 → 插入已排序部分：

4 < 8 → 移动 8
4 < 6 → 移动 6
4 < 5 → 移动 5
插入 4

组内状态：4,5,6,8

处理 2 → 插入已排序部分：

2 < 8 → 移动 8
2 < 6 → 移动 6
2 < 5 → 移动 5
2 < 4 → 移动 4
插入 2

组内状态：2,4,5,6,8

数组对应位置（下标 1,3,5,7,9）：

[0,2,1,4,3,5,7,6,9,8]

gap = 2结束，gap = 1 ，相当于进行插入排序

特点：

插入排序需要多次移动数组中大量元素的位置，希尔排序可大量减少移动次数。
原地排序
时间复杂度：

平均 O(n^1.3 ~ n^1.5)
最好 O(n)
最坏 ≈ O(n²)