Aloha
0%

Fundamental Sorting | 基本排序算法

Posted on Edited on In

写在前面

排序就是将给定数据按照一定的顺序（升序或降序）重新排列。 排序是许多算法的基础，可以让数据变得容易处理。
排序时，需要先确定排序的基准，即“排序键”；在选择排序算法时，时间复杂度、空间复杂度 和 稳定排序 都是重要的考量标准。 所谓稳定排序，即指在数据中含有键值相等的元素，其在排序完成后顺序不变。
时至今日，人们已经开发出了许多种排序方法，其机制个不相同。 我们要根据实际情况，选择适宜的排序方法：

  • 复杂度与稳定性
  • 除了原有数据外是否还需要额外的内存
  • 输入数据的特征可能会影响算法的效率

虽然各种编程语言的库中都有标准排序算法供我们使用，但是，算法乃是程序员的自我修养，而排序是算法的基础，深入理解其原理可以为我们将来实现其他功能提供思路与方法。

初等排序

插入排序

插入排序将待排序数据分为 已排序 和 未排序 部分，取出未排序部分的开头元素，将它的值储存在临时变量v里，然后将所有比v大的元素都后移一位，再将v插入到空位里。这就是插入排序了，很简单吧，我们直接上代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 插入排序算法
void insertsort(int n, int arr[]) {
	int v, j;
	for (int i = 1; i < n; i++) { // 假设设第一个[0]元素已经排好，从1开始循环
		v = arr[i]; // 以v作为比较基准，即未排序部分的开头元素值
		j = i - 1;
		// 进行移动，将所有大于v的元素后移一个单位
		while (j >= 0 && arr[j] > v) { // 注意循环条件
			arr[j + 1] = arr[j];
			j--;
		}
		// 最后将v插入在恰当位置，即所有小于等于v的元素之前
		arr[j + 1] = v; // 注意：寻找到插入位置后仍然会执行 j--
	}
}

分析插入排序的特征，我们可以发现，因为插入排序不会直接交换不相邻的元素，而是将所有比当前元素键值大的元素后移，因此，插入排序是稳定的。
再看看复杂度，在最极端的条件下，我们需要将 每个i循环 进行i次移动，总共需要1+2+……+N-1=(N^2 -N)次移动，当N很大时，我们可以忽略N的项而保留 N平方 的项，即插入排序的时间复杂度O(N*N)。但是如果是已经按照升序排列好的数组，我们只需要N次比较就可以完成排序。 由此可见，输入数据的特征可以明显影响排序的效率。亦可以看出，插入排序能够快速处理相对有序的数据，这一点很重要，在高等排序的 希尔排序 中会对这一特性进行扩展。

冒泡排序

冒泡排序实现简单，使用广泛。它的机制是依次比较相邻元素，将所有大小关系相反的数据交换：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void swap(int* p, int* q) {
	int tem = *p;
	*p = *q;
	*q = tem;
}
// 冒泡排序算法
int bubblesort(int n, int arr[]) {
	int times = 0;
	bool flag = 1;			   // 发挥外层变量i的作用
	for (int i = 0;flag;i++) { // 已经排序完成的前i个元素不需要再次进行比较
		flag = 0;			   // 每次需比较至i+1
		for (int j = n - 1;j >= i + 1;j--) { // 从数组末尾开始循环防止溢出
			if (arr[j] < arr[j - 1]) {
				swap(arr[j], arr[j - 1]);
				flag = 1;
				times++;
			}
		} // 当某一次循环中不发生交换时则证明已经排序完成
	}
	return times; // 返回交换次数
}

类似的，我们对冒泡排序算法进行分析，其在最坏的情况下需要（N^2 -N）次比较，即算法时间复杂度为O(N*N)。顺带一提，函数返回的交换次数也称为逆序数，反应了数据的混乱程度。

选择排序

同样的，选择排序也将数组分为 已排序 和 未排序 的部分。 找出未排序部分的最小(大)值的位置下标 min_j (max_j)，将min_j 位置的元素与未排序部分的开头元素交换，重复N-1次(N个元素，最多换N-1次)：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 选择排序算法
int selectionsort(int n, int arr[]) {
	int times, min_j;
	times = 0;
	for (int i = 0;i < n - 1;i++) { // i表示未排序部分的开头元素下标
		min_j = i; // min_j 表示每轮循环中 第i 到 第N-1 元素中 最小值的下标
		for (int j = i;j < n;j++) { // 更新最小值下标
			if (arr[min_j] > arr[j]) min_j = j;
		}
		swap(arr[i], arr[min_j]);
		if (i != min_j) times++; // 若最小值为arr[i]本身则无需交换
	}
	return times;
}

要注意的是，选择排序会交换不相邻的元素，因此可能出现排序键值相等而元素顺序改变的情况，例如：数组{3H,5L,3D,1S}，在对 数字键值 执行选择排序后，会变成{1S,3D,3H,5L} （大家可以自行验证）。可见，选择排序是不稳定的。
再来看看复杂度，无论在什么情况下，选择排序都要进行（N^2-N）/2 次比较运算，复杂度与N*N成正比。

初等排序小结

综合来观察三种初等排序方法。冒泡排序从局部出发，逐项比较，减少逆序数；选择排序面向整体，逐个选择最小（大）值。虽然这二者思路大相径庭，但是我们可以看出，冒泡排序 和 选择排序 不依赖输入数据。而与之相对的，插入算法却很依赖数据，处理相对有序的数据有很高的效率。

高等排序

虽然初等排序在应对一般数据时已经有很好的效果，但是在非常庞大的数据面前便会失去效果。因此，我们就需要运用高等排序。 高等排序是通过运用 分治法与递归法，结合初等排序思路 进行优化而实现的高速算法。

希尔排序

上文提到过，插入排序 在针对相对有序的数据时具有非常高的效率。而 希尔排序就是针对这一特性而实现的高速算法。
希尔排序的思路是，重复进行以间隔为g的插入排序，g的值逐轮减小，最后再执行 间隔g=1 的一般插入排序。 为什么要进行这样的操作呢？
其实，每一轮以g为间隔时，其实都是把选出来的数据组成一个新的数组，这些数组的元素数目N’相对N来讲很小。第一轮时，g1约为数据量N的1/3~ 1/2 ，这些分割出来的数组只有2~3个元素，进行排序非常快捷。第二轮时，经过第一轮的处理，此时的数组相对原数组变得相对有序了一些（好吧，虽然只有一点点，(⊙o⊙)），此时，间隔g2减小，继续执行排序，这些小数组又变得有序了。 继续一轮轮的执行这些操作，间隔g逐渐减小；每一轮操作时，因为之前的插入排序，对数据整体来说，此时的数组已经变得相对有序了很多。所以此时在执行当前g的插入排序，效率比直接执行此gap的插入排序提高了非常多。
根据这个原理，最后在执行 g=1 的插入排序时，因为数据已经变得非常有序了，此时的排序效率非常高。
那么，由此可见，希尔排序的效率就跟Gap间隔数组的选择有很大的关系，根据数学原理，当递推关系式为：g(n+1) = 3*g(n)+1 时，希尔排序的复杂度基本稳定在O(N^1.25)。具体数学原理本文就不做讨论了（才不是因为论文太难看不懂呢😂）。但要注意的是，如果Gap间隔数组为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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <vector>
#define LEN 1000

void insertionsort(int arr[], int g);
void shellsort(int arr[]);

long long cnt;
int arr[LEN];
std::vector<int> Gap;

int main() {
	srand((unsigned)time(NULL));
	for (int i = 0;i < LEN;i++) {
		arr[i] = rand() % 10000 + 1;
	}
	for (int i = 0;i < LEN;i++) {
		printf("%6d", arr[i]);
		if ((i + 1) % 10 == 0) printf("\n");
	}
	printf("\n");
	shellsort(arr);
	for (int i = 0;i < LEN;i++) {
		printf("%6d", arr[i]);
		if ((i + 1) % 10 == 0) printf("\n");
	}
	printf("%lld", cnt);
	return 0;
}
// ShellSort算法核心
void insertionsort(int arr[], int g) { // 指定gap的插入排序
	for (int i = g;i < LEN;i++) {
		int v = arr[i];
		int j = i - g;
		while (j >= 0 && arr[j] > v) {
			arr[j + g] = arr[j];
			j -= g;
			cnt++;
		}
		arr[j + g] = v;
	}
}
void shellsort(int arr[]) {
	for (int h = 1;;) { // 递推公式生成Gap数组
		if (h > LEN) break;
		Gap.push_back(h);
		h = 3 * h + 1;
	}
	for (int i = Gap.size() - 1;i >= 0;i--) {
		insertionsort(arr, Gap[i]);
	}
}

归并排序

类似于希尔排序，归并排序也是从局部入手，将庞大复杂的数据向下逐层拆分成小的局部数组，再进行逐层向上的整合，从而实现高速的排序。我们直接上代码：

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
int L[MAX / 2 + 2];
int R[MAX / 2 + 2];
int cnt = 0;
// 归并排序算法核心
void merge(int A[], int n, int left, int mid, int right) {
	int n1 = mid - left;
	int n2 = right - mid;
	for (int i = 0;i < n1;i++) L[i] = A[left + i];
	for (int i = 0;i < n2;i++) R[i] = A[mid + i];
	L[n1] = R[n2] = SENTINAL;
	int i = 0, j = 0; // 注意合并方式！
	for (int k = left;k < right;k++) {
		cnt++;
		if (L[i] <= R[j]) A[k] = L[i++];
		else A[k] = R[j++];
	}
}
void mergeSort(int A[], int n, int left, int right) {
	// 分割至倒数第二层时 left=t, mid=t+1, right=t+2
	// 分割至最后一层，'局部数组'变成了单个元素
	// 最终形成'树'的结构
	// 此时 merge 的对象为两个单元素数组
	if (left + 1 < right) {
		int mid = (left + right) / 2;
		mergeSort(A, n, left, mid);
		mergeSort(A, n, mid, right);
		merge(A, n, left, mid, right);
	}
	return;
}

归并排序的核心是merge函数，逐层分割后的局部数组在merge函数的整合下，每一层的复杂度是O(n_left+n_right)，于是整个算法的复杂度为O(N*logN)。
我们容易看出，只要元素出现在其键值相等的其他元素之前，其在分割与整合后就一定在其他元素之前，所以归并排序是稳定的。
但要注意的是，虽然归并排序稳定高效，但是它却需要额外的内存来储存分割出来的临时数组，占据额外的空间。

快速排序

快速排序可以说是运用最为广泛的排序算法了，它稳定高效，C++的STL库函数sort( ) 就是基于快速排序的函数。 快速排序基于递归法，在分割的同时对数据进行排序与调换：

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
// 快速排序算法
void quicksort(int left, int right) {

	int i, j, t, temp;

	if (left > right) return;

	temp = randarr[left];
	i = left;  j = right;
	while (i != j) {

		while (randarr[j] >= temp && i < j) j--; // i循环

		while (randarr[i] <= temp && i < j) i++; // j循环

		if (i < j) {
			t = randarr[i];
			randarr[i] = randarr[j];
			randarr[j] = t;
		}

	}
	randarr[left] = randarr[i];
	randarr[i] = temp;

	quicksort(left, i - 1);  //左递归
	quicksort(i + 1, right); //右递归

	return;
}

主函数调用时需要传递初始参数，即 quicksort(0,n-1)。 观察上述代码，i、j 即为所谓的标兵节点。第一轮调用时，i从0，j从n-1开始，选择 arr[0] 为比较基准，储存在temp中。i和j while循环中，i寻找比temp大的节点，j寻找比temp小的节点；i、j 不可错位(设置适宜的循环条件)。i和j 循环结束时，如果是因为i==j，则结束外层循环，进入下一步；而如果是因为找到了目标节点，则两个值互换，继续执行代码； 无论如何，只要外层while循环结束，i和j 相遇在同一节点，再将arr[left]的值换到i位置，此时 i(j) 之前的元素都小于等于temp，之后的元素都大于等于temp。 进行递归调用quicksort(left, i - 1); //左递归 quicksort(i + 1, right); //右递归，即将左右分别再次执行一次上述操作，直到left=right(局部数组为单个元素)返回，此时，排序就完成了。
上述的只是快速排序基准选择的一个方式，还有很多根据实际情况的方式，但思路大体一致，本文不再赘述。

计数排序

计数排序相对简单，它善于处理元素为正整数的情况，具有极高的效率，但是其元素的最大值具有限制，否则会导致栈溢出：

1
2
3
4
5
6
7
8
9
10
11
12
void CountingSort(int n) {
	for (int i = 1;i <= n;i++) {
		C[A[i]]++; // A 中每个元素出现次数
	} 
	for (int j = 0;j <= MAX;j++) {
		C[j] = C[j] + C[j - 1]; // 注意，因为A[i] 可能等于0 C的下标从0开始
	} // 算法核心，通过逐项求和 C[X]表示还有多少小于等于X的项，即该放到第几位
	for (int i = 1;i <= n;i++) {
		B[C[A[i]]] = A[i];
		C[A[i]]--; // 自减保证值相同项的放置
	}
}

为了表达方便，A下标从0开始。
第一个for循环结束，C[k] 的值即为A中值为k的元素出现的次数。再把C逐项累加，那么此时C[k]的值就表示A值为k的元素放置于排序完成数组B中的位置，也表示A中包含几个小于等于K的元素。计数排序能在O(N+Max)的线性时间完成排序，效率可以说非常高了。

打个总结

以上就是常见的排序算法了，其实不难看出，没有最好的排序算法，只有最适宜的排序方法，我们要根据实际情况来选择使用算法。对其他算法也是一样，我们要因地制宜，在不同情形下选择最优解；有些时候可能没有现成的方法让我们直接使用，这时候就需要分析问题，解决问题的能力，站在前人们的肩膀上，用这些思路创新开发出合适的方法。
笔者虽然仔细核对过文中附如的代码，但是难免疏漏，有问题或建议欢迎留言，谢谢。