经典排序算法

排序是数据结构中非常基础的功底。比较排序有插入排序、希尔排序、选择排序、堆排序、冒泡排序、快速排序和归并排序;非比较排序有桶排序、基数排序和计数排序。本文用 C++ 实现各种排序算法,以及用 Leetcode 例子进行实践。

排序可以分成内部排序和外部排序,内部排序是在内存中排序,外部排序是通过磁盘等介质来排序。本文记录的排序都是内部排序。

插入排序

从左到右,依次选择一个数和之前的序列中得数字进行比较,找到合适的位置插入该数字,所以整个过程中有前后两组序列,前面的序列为有序,后面的序列为待排序的序列。

  1. 初始状态 a[0]a\left[0\right] 为有序序列,其余为待排序。
  2. 选出待排序中第一个数字 xx,在有序序列中找出 yy,使得 x<yx < y,则交换两者。
  3. 对待排序序列中每一个数都进行步骤 2。

注意这里的交换条件 x<yx < y,因为遇到相等数字是需要把 xx 插入到相等数字的后面。这样就保证了插入排序是稳定的。

稳定排序算法是指:在排序前 xi=xjx_i = x_j,且 xix_ixjx_j 之前,如果排序后仍然是 xix_ixjx_j 之前,那么该算法就是稳定的。

实现

1
2
3
4
5
6
7
8
9
void insert_sort(vector<int> &nums) {
for (int i = 1; i < nums.size(); ++i) {
for (int j = i - 1; j >= 0; --j) {
if (nums[j] > nums[j + 1]) {
swap(nums[j], nums[j + 1]);
}
}
}
}

时间复杂度

最好的情况,就是输入本身就是有序的,只需要 n1n-1 次比较,时间复杂度为 O(n)O\left(n\right)。最坏的情况,输入是逆序的,需要 n(n1)2\frac{n\left(n-1\right)}{2} 次比较,时间复杂度为 O(n2)O\left(n^2\right)

希尔排序

插入排序是一个一个进行比较,希尔排序将输入按照一定步长分成自序列进行插入排序。然后步长逐渐减小到 1,就是插入排序了,然后就完成了排序。

  1. 按照步长划分子序列。
  2. 对每个子序列进行插入排序。
  3. 步长减半,重复 1、2 直到步长等于 1。

实现

1
2
3
4
5
6
7
8
9
10
11
void shell_sort(vector<int> &nums) {
for (int gap = nums.size() / 2; gap > 0; gap /= 2) {
for (int i = gap; i < nums.size(); ++i) {
for (int j = i - gap; j >= 0; j -= gap) {
if (nums[j] > nums[j + gap]) {
swap(nums[j], nums[j + gap]);
}
}
}
}
}

时间复杂度

希尔排序的时间复杂度受到步长的影响。在元素基本有序的情况下,效率很高。但是希尔排序是不稳定排序。

步长序列 最坏情况的复杂度
n2i\frac{n}{2^i} O(n2)O\left(n^2\right)
2k12^k - 1 O(n32)O\left(n^{\frac{3}{2}}\right)
2i3j2^i3^j O(nlog2n)O\left(n\log^2n\right)

选择排序

在输入序列中,找出最大(小)的一个数与第 1 个数字交换,然后在剩下的数字中找出最大(小)的与第 2 个数字交换。

  1. 初始状态 a[0]a\left[0\right] 为有序序列,其余为待排序。
  2. 在待排序 a[i,,n1]a\left[i, \dots, n-1\right] 中找出最大的元素与 a[i]a\left[i\right] 交换。
  3. 重复步骤 2,直到 i=n1i = n-1

实现

1
2
3
4
5
6
7
8
9
10
11
void selection_sort(vector<int> &nums) {
for (int i = 0; i < nums.size(); ++i) {
int min_index = i;
for (int j = i + 1; j < nums.size(); ++j) {
if (nums[j] < nums[min_index]) {
min_index = j;
}
}
swap(nums[i], nums[min_index]);
}
}

时间复杂度

每次找最小(大)值都要比较 nin - i 次,这样的过程要执行 nn 次。所以时间复杂度是 O(n2)O\left(n^2\right)。选择排序是不稳定排序。

堆排序

以一维数组来存储堆,那么堆就对应了一个完全二叉树。以最大堆为例,堆的顶,也就是第一位总是堆中最大值。非叶子节点的值均不小于其左右孩子的值。将最大值移除后,需要调整堆,使得堆顶的值为堆中剩下值的最大值。

ii 节点 a[i]a\left[i\right] 的左孩子为 a[2i+1]a\left[2i+1\right]
ii 节点 a[i]a\left[i\right] 的右孩子为 a[2i+2]a\left[2i+2\right]
ii 节点 a[i]a\left[i\right] 的父亲为 a[i12]a\left[\left \lfloor \frac{i-1}{2}\right \rfloor \right]

调整堆

  1. 假设堆中还有 mm 个元素。将堆顶元素与堆中最后一个元素互换,然后剩下 m1m-1 个元素。
  2. 找出根节点左右孩子较大的一个。
  3. 与较大的孩子互换。
  4. 对被交换的孩子所在的子树进行 1、2、3 步骤,一直到叶子节点。

初始化堆

  1. nn 个节点的堆中最后一个非叶子节点为第 n2\frac{n}{2},下标为 n21\frac{n}{2} - 1
  2. 从最后一个非叶子节点往前逐步调整堆。
  3. 重复步骤 2 直到根节点。

实现

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
29
30
31
32
void heap_sort(vector<int> &nums) {
heap_build(nums);
int n = nums.size();
for (int i = n - 1; i > 0; --i) {
swap(nums[0], nums[i]);
heap_adjust(nums, 0, i - 1);
}
}

void heap_adjust(vector<int> &nums, int start, int end) {
int cur = start;
int child = 2 * start + 1;
while (child <= end) {
if (child + 1 < end && nums[child] < nums[child + 1]) {
++child;
}
if (nums[cur] < nums[child]) {
swap(nums[cur], nums[child]);
cur = child;
child = 2 * cur + 1;
} else {
break;
}
}
}

void heap_build(vector<int> &nums) {
int n = nums.size();
for (int i = n / 2 - 1; i >= 0; --i) {
heap_adjust(nums, i, n);
}
}

时间复杂度

调整一次堆需要 O(logn)O\left(\log n\right) 的时间,共需要调整 nn 次,所以总的时间复杂度为 O(nlogn)O\left(n\log n\right)。而且堆排序是不稳定排序。

冒泡排序

从左到右,两两相邻交换,把大的数往后挪,每次可以确保前 mm 个数中最大的移动到最右边。

  1. 从左开始比较相邻元素 xxyy,如果 x>yx > y 就交换两者,直到最后一个元素。
  2. 重复步骤 1,直到 nn 次最大元素都移动到最右边。

实现

1
2
3
4
5
6
7
8
9
10
void bubble_sort(vector<int> &nums) {
int n = nums.size();
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n - i - 1; ++j) {
if (nums[j] > nums[j + 1]) {
swap(nums[j], nums[j + 1]);
}
}
}
}

时间复杂度

共需要执行 nn 次冒泡,每次冒泡的比较次数为 nin-i,所以时间复杂度为 O(n2)O\left(n^2\right)。因为相邻元素相等时,我们没有进行交换,所以冒泡排序是稳定的。

快速排序

快速排序是采用分治思想的一个排序算法。选择一个基准数字,然后把比这个数小的移动到左边,把比这个数大的移动到右边。接下来对左右两边都进行相同的上述步骤,直到整个数组有序。

  1. 从最左边挖出基准数 a[i]a\left[i\right]
  2. 由右往左找出比它小的数字填进去,这时候产生新的坑 a[j]a\left[j\right]
  3. 由左往右找出比它大的数字填进去,产生新的坑。
  4. 重复步骤 2、3 直到 i=ji = j,然后把基准数填入即可。

实现

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
29
void quick_sort(vector<int> &nums) {
int n = nums.size();
quick_sort(nums, 0, n - 1);
}

void quick_sort(vector<int> &nums, int start, int end) {
if (start < end) {
int l = start;
int r = end;
int flag = nums[l];
while (l < r) {
while (l < r && nums[r] >= flag) {
--r;
}
if (l < r) {
nums[l++] = nums[r];
}
while (l < r && nums[l] <= flag) {
++l;
}
if (l < r) {
nums[r--] = nums[l];
}
}
nums[l] = flag;
quick_sort(nums, start, l - 1);
quick_sort(nums, l + 1, end);
}
}

时间复杂度

快速排序当你每次选中的正好是中位数时,时间复杂度才是 O(nlogn)O\left(n\log n\right),当每次选中的是最大值或者最小值时,快速排序就退化成冒泡排序了。

C(n)=n1+1ni=0n1(C(i)+C(ni1))=2nlnn=1.39nlog2n\begin{aligned} C\left(n\right) &= n - 1 + \frac{1}{n}\sum_{i=0}^{n-1}\left(C\left(i\right) + C\left(n-i-1\right)\right) \\ &= 2n\ln n = 1.39n\log _2 n \end{aligned}

考虑到相同的元素可能经由中转来交换顺序,快速排序也是不稳定排序。

归并排序

将两个或者两个以上的有序序列合并成一个新的有序序列。归并排序采用了分治的思想,将原始序列不断分成小序列,然后将小序列排序好,再把它们合并起来。

  1. 将原始数组分成 nn 个单位 1 的序列,然后两两合并成单位 2 的序列。
  2. 按照 2 的倍数进行比较合并,直到整个序列有序。

实现

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
29
30
31
32
33
34
35
36
37
38
void merge_sort(vector<int> &nums) {
int n = nums.size();
vector<int> tmp(n);
merge_sort(nums, 0, n - 1, tmp);
}

void merge_sort(vector<int> &nums, int start, int end, vector<int> &tmp) {
if (start < end) {
int middle = (start + end) / 2;
merge_sort(nums, start, middle, tmp);
merge_sort(nums, middle + 1, end, tmp);
merge_array(nums, start, middle, end, tmp);
}
}

void merge_array(vector<int> &nums, int start, int middle, int end, vector<int> &tmp) {
int s1 = start;
int e1 = middle;
int s2 = middle + 1;
int e2 = end;
int i = 0;
while (s1 <= e1 && s2 <= e2) {
if (nums[s1] < nums[s2]) {
tmp[i++] = nums[s1++];
} else {
tmp[i++] = nums[s2++];
}
}
while (s1 <= e1) {
tmp[i++] = nums[s1++];
}
while (s2 <= e2) {
tmp[i++] = nums[s2++];
}
for (int j = 0; j < i; ++j) {
nums[start + j] = tmp[j];
}
}

时间复杂度

循环执行了 logn\log n 次,每次循环处理的元素为 nn,所以时间复杂度为 nlognn\log n

桶排序

将序列分到有线数量的桶中,然后每个桶分别排序(别的排序算法或者递归继续桶排序)。

  1. 先扫描一遍求出最大值 max 和最小值 min,设桶的个数为 k,那么把区间 [min, max] 均匀划分成 k 个区间,每个区间就是一个桶。
  2. 对桶内每个元素进行排序。
  3. 将桶中元素合并成总的有序序列。

实现

First Missing Positive

Given an unsorted integer array, find the first missing positive integer. For example, Given [1,2,0] return 3,and [3,4,-1,1] return 2. Your algorithm should run in O(n)O\left(n\right) time and uses constant space.

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
class Solution {
public:
int firstMissingPositive(vector<int> &nums) {
bucket_sort(nums);
int n = nums.size();
for (int i = 0; i < n; ++i) {
if (nums[i] != i + 1) {
return i + 1;
}
}
return n + 1;
}

private:
void bucket_sort(vector<int> &nums) {
const int n = nums.size();
for (int i = 0; i < n; ++i) {
while (nums[i] != i + 1) {
if (nums[i] < 1 || nums[i] > n || nums[i] == nums[nums[i] - 1]) {
break;
} else {
swap(nums[i], nums[nums[i] - 1]);
}
}
}
}
};

这个题目的本质是桶排序,其实从这个题目中可以窥探到桶排序的一个重要应用场景: Bitmap

时间复杂度

假设数据是均匀分布的,那么每个桶的元素是 nk\frac{n}{k} 个,假如用快速排序对桶内元素进行排序,那么每次时间复杂度为 O(nklog(nk))O\left( \frac{n}{k} \log \left( \frac{n}{k} \right)\right)。总的时间复杂度为:

O(n)+O(m)O(nklog(nk))=O(n+nlog(nk))=O(n+nlognnlogk)O\left(n\right) + O\left(m\right)O\left( \frac{n}{k} \log \left( \frac{n}{k} \right)\right) = O\left(n+n\log \left(\frac{n}{k}\right)\right) = O\left(n+n\log n - n\log k\right)

所以 k 越接近 n 时,桶排序的时间复杂度越接近 O(n)O\left(n\right)。桶越多,时间效率越高,空间越大。

基数排序

基数排序如其名,用基底进行排序。

  1. 将待排序的整数(必须非负整数)统一为位数相同的整数,位数少的前面补零。所以前提要找到最大值,得到最长位数,然后设 k 进制下最长的位数为 d。
  2. 从最低位开始,依次往高位进行稳定排序

实现

Maximum Gap

Given an unsorted array, find the maximum difference between the successive elements in its sorted form. Try to solve it in linear time/space. Return 0 if the array contains less than 2 elements. You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution {
public:
int maximumGap(vector<int> &nums) {
if (nums.size() < 2) return 0;
radix_sort(nums);

int max_diff = INT_MIN;
for (int i = 1; i < nums.size(); ++i) {
max_diff = max(max_diff, nums[i] - nums[i - 1]);
}
return max_diff;
}

private:
void radix_sort(vector<int> &nums) {
auto itrs = minmax_element(nums.begin(), nums.end());
auto minElem = *(itrs.first);
auto maxElem = *(itrs.second);
const int d = to_string(maxElem - minElem).length();
vector<vector<int>> buckets(10, vector<int>());
for (int i = 0; i < d; ++i) {
for (auto &it: nums) {
const int index = getDigit(it - minElem, i);
buckets[index].push_back(it);
}
int k = 0;
for (auto &bucket: buckets) {
for (auto &it: bucket) {
nums[k++] = it;
}
bucket.clear();
}
}
for (auto &it: nums) {
cout << it << endl;
}
}

int getDigit(int n, const int i) {
for (int j = 0; j < i; ++j) {
n /= 10;
}
return n % 10;
}
};

其实这个题目用桶排序或者计数排序都可以 AC。

时间复杂度

当使用二进制时,k 最小,位数 d 最大。时间复杂度 O(nd)O\left(nd\right) 增大,空间复杂度 O(n+k)O\left(n+k\right) 减小。当用最大值作为基数时,k 最大,d=1 最小,时间复杂度变小,空间复杂度急剧增大,此时基数排序就退化成了计数排序。

计数排序

计数排序其实是一种特殊的桶排序,当桶的个数最大的时候就是计数排序。开辟一个长度为 max-min+1 的数组。

  1. 把当前值减去 min 作为下标,改下标对应的计数器加 1。
  2. 扫描一边,把各个值收集起来。

实现

H-Index

Given an array of citations (each citation is a non-negative integer) of a researcher, write a function to compute the researcher’s h-index. According to the definition of h-index on Wikipedia: “A scientist has index h if h of his/her N papers have at least h citations each, and the other N − h papers have no more than h citations each.” For example, given citations = [3, 0, 6, 1, 5], which means the researcher has 5 papers in total and each of them had received 3, 0, 6, 1, 5 citations respectively. Since the researcher has 3 papers with at least 3 citations each and the remaining two with no more than 3 citations each, his h-index is 3.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int hIndex(vector<int> &citations) {
int n = citations.size();
vector<int> histogram(n + 1);
for (auto &it: citations) {
++histogram[it > n ? n : it];
}
int sum = 0;
for (int i = n; i >= 0; --i) {
sum += histogram[i];
if (sum >= i) {
return i;
}
}
return n;
}

时间复杂度

参考桶排序的时间复杂度分析,计数排序的时间复杂度为 O(n)O\left(n\right)