排序概述
基本概念
排序：重新排列表中元素，使其按关键字递增或递减的过程，一般是递增的。排序算法是数据结构中最基础的算法之一。排序算法的稳定性：如果a=b且排序前a在b的前面，使用某一排序算法排序后a依然在b的前面，就称这个排序算法是稳定的。反之，则称该排序算法是不稳定的。注意，算法是否具有稳定性并不能衡量一个算法的优劣，它只是对一个算法的性质进行描述。
在排序过程中，根据待排元素是否基于比较进行排序，可将排序算法分为两类：比较类排序和非比较类排序。比较类排序：通过比较两个待排元素的关键字，从而确定两个待排元素的前后关系，然后通过移动两个待排元素以达到有序。比较类排序的时间复杂度不能突破O(nlogn)。非比较类排序：通过元素本身的数值和整个序列的数值范围来确定元素的位置，而不是通过比较元素关键字来确定元素位置，因此非比较类排序的时间复杂度一般为O(n)，突破了比较类排序的理论时间下限。
此外，根据待排元素是否都在内存中，可将排序算法分为两类：内部排序和外部排序。内部排序是指待排元素全部存放在内存中的排序。外部排序是指待排元素无法全部存放在内存中，排序过程中必须不断地在内、外存之间移动的排序。所有排序都可用于内部排序，而外部排序一般借助归并排序来实现。在实际开发中，外部排序使用较少。
排序分类
插入排序
算法简介
插入排序（直接插入排序）的基本思想在于，每次将一个待排元素按其关键字大小插入到已经排好序的子序列中，直到所有待排元素全部插入完成。比如，n个人按身高依次递增的顺序排队，第一个人不动。第二个人与第一个人比较，如果比第一个人矮就插到第一个人前面，反之则不动。依次类推，后面的人依次插入到前面已经排好队的队伍中，直到所有人都排好队为止。下面是插入排序的GIF动图演示：
代码实现
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
|
using System;
namespace Sort
{
class Client
{
// 插入排序
public static int[] InsertSort(int[] a)
{
int len = a.Length;
int preIndex, current;
for (int i = 1; i < len; i++)
{
preIndex = i - 1;
current = a[i];
while (preIndex >= 0 && current < a[preIndex])
{
a[preIndex + 1] = a[preIndex];
preIndex--;
}
a[preIndex + 1] = current;
}
return a;
}
public static void Main(string[] args)
{
int[] a = { 1, 5, 2, 6, 3, 8, 4, 0, 9, 7 };
int len = a.Length;
InsertSort(a);
for (int i = 0; i < len; i++)
{
Console.WriteLine(a[i]);
}
}
}
}
|
算法分析
插入排序的时间复杂度为O(n^2)，空间复杂度为O(1)。插入排序在实现上通常采用原地排序，即算法所需的辅助空间是常数级的。因为每次与前面的元素进行比较时，都需要反复把已经排好序的元素逐步向后挪位，为新元素提供插入的空间，因此只需要常数个辅助单元。
由于每次插入元素时总是从后向前先比较后移动，只有后一个元素关键字小于前一个元素关键字时才移动，等于或大于不移动，因此关键字相等的两个元素排序后相对位置不会发生变化，即插入排序是稳定的。插入排序对顺序存储和链式存储的线性表都适用，当线性表为链式存储时，可以从前往后查找对应位置的元素。注意：大部分排序算法都只适用于顺序存储的线性表！
算法优化
我们知道插入排序每次插入元素时，都是与前面已经排好序的元素依次逐个比较来找到插入位置，边比较边移动。当排序表为顺序存储的线性表时，前面已经排好序的元素可以视为一个有序的顺序表。这时我们可以通过折半查找来找到待排元素的插入位置，从而减少元素之间的比较次数，然后再统一移动插入位置之后的元素，这种排序称为折半插入排序。尽管折半插入排序减少了元素的比较次数，但元素的移动次数依然没有减少。所以时间复杂度仍为O(n^2)，空间复杂度也仍为O(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
27
28
29
30
31
32
33
34
|
// 折半插入排序
public static int[] BinaryInsertSort(int[] a)
{
int len = a.Length;
int current;
int low, mid, high;
for (int i = 1; i < len; i++)
{
current = a[i];
low = 0;
high = i - 1;
while (low <= high)
{
mid = low + (high - low) / 2;
// 根据算法的稳定性，所以等于时不移动元素
if (current >= a[mid])
{
low = mid + 1;
}
else
{
high = mid - 1;
}
}
// 必须从后往前挪动，如果从前往后挪就会覆盖前面的元素。
for (int j = i - 1; j > high; j--)
{
a[j + 1] = a[j];
}
// high+1就是元素的插入位置
a[high + 1] = current;
}
return a;
}
|
希尔排序
算法简介
希尔排序的基本思想是：将待排元素按照间隔di分割成di个组，然后对每个组分别进行直接插入排序，直到整个排序表“基本有序“时，再对整个排序表进行直接插入排序。这个间隔di称为增量，增量是逐渐减小的，因此希尔排序又称缩小增量排序。由于排序过程中需要多次按照增量di进行分割，一个好的增量序列很重要，但目前并没有严格意义上的好的增量序列。希尔提出了一个方法，d1 = n/2，di+1 = di/2取下整，最后一个增量d等于1。即最后一个增量为1时，就是对整个排序表进行直接插入排序。下面是希尔排序的GIF动图演示：
代码实现
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
|
// 希尔排序
public static int[] ShellSort(int[] a)
{
int len = a.Length;
int d = len / 2;
int current, loc;
// 每一个增量排一趟，直到最后一个增量等于1
while (d >= 1)
{
// 每一个增量di分割成di个组
for (int i = 0; i < d; i++)
{
// 对每一组进行直接插入排序
for (int j = i + d; j < len; j += d)
{
current = a[j];
// 组内待排元素插入位置loc
loc = j;
// 如果组内待排元素比前面的元素小，就把前面的元素向后移动d个单位。
while (loc - d >= i && current < a[loc - d])
{
a[loc] = a[loc - d];
loc = loc - d;
}
// 如果待排元素大于或等于组内前面的元素，前面的元素就不动，直接插入当前位置。
a[loc] = current;
}
}
// 每一趟排完后，就缩小增量继续排下一趟
d = d / 2;
}
return a;
}
|
算法分析
由于希尔排序的时间复杂度依赖于增量序列的函数，目前还没有严格意义上好的增量序列，因此直接分析希尔排序时间复杂度较为困难。当n在某个特定范围时，希尔排序的时间复杂度约为O(n^1.3)，最坏为O(n^2)。希尔排序的空间复杂度为O(1)。
由于关键字相同的两个元素可能被分割到不同的组，组内排序时元素顺序会发生变化，所以最终这两个元素的相对顺序可能会发生变化，因此希尔排序是不稳定的。由于希尔排序需要对元素进行分割，按增量di直接获取元素，因此希尔排序只适用于顺序存储的线性表。此外，希尔排序得到的序列是”基本有序“，不是严格意义上的有序，所以不能使用折半插入排序。
冒泡排序
算法简介
冒泡排序的基本思想是：假设有n个待排元素，从后往前（或从前往后）两两比较相邻元素的关键字，如果后一个元素大于前一个元素就交换它们的顺序，直到把所有待排元素都比较完。这样一趟排序称之为一趟冒泡，每趟冒泡都会把最小的元素交换到待排序列中的第一个位置。关键字小的元素就像气泡一样往上冒，关键字大的元素就相应地往下沉。下一趟冒泡时，前一趟冒泡确定的最小元素不参与比较，这样每一次冒泡时都有一个最小元素放到了排序表的最终位置，这样最多n-1趟冒泡就把所有元素排好序。下面是冒泡排序（从前往后）的GIF动图演示：
代码实现
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
|
// 冒泡排序
public static int[] BubbleSort(int[] a)
{
int len = a.Length;
int temp;
// 每趟冒泡是否发生元素交换的标志
bool flag;
// 每一趟冒泡确定一个最小元素的位置，n-1趟冒泡确定n-1个元素的位置，最后一个元素必定是最大的。
for (int i = 0; i < len - 1; i++)
{
flag = false;
// 从后往前冒泡，每一趟冒泡把最小的元素冒上去
// 如果序列前面的元素大多比较小，就从后往前冒泡，这样能减少冒泡的趟数。
// j > i 表示已经通过冒泡确定位置的最小元素不参与比较
for (int j = len - 1; j > i; j--)
{
if (a[j] < a[j - 1])
{
temp = a[j - 1];
a[j - 1] = a[j];
a[j] = temp;
flag = true;
}
}
// 从前往后冒泡，每一趟冒泡把最大的元素沉下去
// 如果序列前面的元素大多比较大，就从前往后冒泡，这样能减少冒泡的趟数。
//for (int j = 0; j < len - 1 - i; j++)
//{
// if (a[j] > a[j + 1])
// {
// temp = a[j];
// a[j] = a[j + 1];
// a[j + 1] = temp;
// flag = true;
// }
//}
// 如果这趟冒泡没有发生交换，说明所有元素已经排好序了，因为之前的元素就是最终有序序列的位置，从而减少冒泡的趟数
if (flag == false)
{
Console.WriteLine("只冒了{0}趟", i+1);
return a;
}
}
return a;
}
|
算法分析
当初始序列有序时，第一趟冒泡后flag没有变还是fasle，表示没有元素交换序列已经排好序了。这时只有一趟冒泡，所以总的比较次数为n-1次，总的移动次数为0，因此冒泡排序最好情况下时间复杂度为O(n)。但平均情况下的时间复杂度为O(n^2)。由于只使用了常数个辅助单元，所以冒泡排序的空间复杂度为O(1)。
由于只有a[j]<a[j-1]或a[j]>a[j+1]时，两个相邻元素才交换，大于或等于时不交换，所以冒泡排序是稳定的。注意：冒泡排序产生的有序子序列一定是全局有序的，每次冒泡都会把最小的元素（或最大元素）放在最终的位置。而插入排序产生的有序子序列只是局部有序的，因为其他的待排元素还没有比较完。
快速排序
算法简介
快速排序是对冒泡排序的一种改进，运用了分治法（”分而治之“，即把一个复杂问题分解为多个相互独立的子问题，子问题的解组合起来就是复杂问题的解）的策略。快速排序的基本思想是：在待排元素中选择一个元素pivot作为基准元素，通过一趟排序将待排序表划分为两个独立的部分，使得左边部分均小于pivot基准元素，右边部分均大于或等于pivot基准元素，这个过程称为一趟快速排序。
随后分别在两个独立的子序列中选择各自的pivot基准元素，然后划分子表并重复上述过程。直到每个部分内只有一个元素或为空为止，即所有元素都放在了最终位置上。快速排序并不产生有序子序列，但每一趟排序后会将一个pivot基准元素放在最终位置上。从上面的描述可以看出，快速排序的关键和性能主要在于子序列的划分。快速排序的划分方法有很多，一般以当前表中第一个元素为pivot基准元素进行划分。下面是快速排序的GIF动图演示：
代码实现
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
|
// 快速排序
public static int[] QuickSort(int[] a, int low, int high)
{
// low和high分别表示待排序列的第一个元素位置（下界）和最后一个元素位置（上界）
// 当low = high时，表示该序列中只有一个元素不需要划分。
// 当low > high时，表示该序列为空，也不需要划分。
// 因此，只有当low < high时，表示该序列中至少有两个元素需要进行划分。
if (low < high)
{
// 先划分子序列，然后再返回划分后该序列pivot基准元素的位置。
int pivotIndex = Partition(a, low, high);
// 对小于pivot基准元素的左边部分继续划分
QuickSort(a, low, pivotIndex - 1);
// 对大于pivot基准元素的右边部分继续划分
QuickSort(a, pivotIndex + 1, high);
}
return a;
}
// 划分函数
private static int Partition(int[] a, int low, int high)
{
// 默认以该序列的第一个元素为基准进行划分
int pivot = a[low];
// 如果low < high就继续寻找，直到low = high就停止寻找，这时的low位置就是新的基准位置。
while (low < high)
{
// 先从该序列的最后一个元素开始，依次寻找小于pivot元素的元素，如果大于或等于pivot元素，就继续向左寻找
while (low < high && a[high] >= pivot)
{
high--;
}
// 如果找到小于pivot元素的元素就退出本次寻找，将该元素移动到最左边
a[low] = a[high];
// 然后从该序列的第一个元素开始，依次寻找大于或等于pivot元素的元素，如果小于pivot元素，就继续向右寻找
while (low < high && a[low] <= pivot)
{
low++;
}
// 如果找到大于或等于pivot元素的元素就退出本次寻找，将该元素移动到刚才向左寻找时空出来的high位置上
a[high] = a[low];
}
// 把刚才基准元素的值赋给新的基准位置
a[low] = pivot;
return low;
}
|
算法分析
快速排序的时间复杂度主要与划分是否对称有关，而这又与具体使用的划分算法有关。当待排序表基本有序或逆序时为最坏情况，此时划分的两个子序列分别为0个元素和n-1个元素，每一层递归调用划分函数时也是如此。这时最坏情况下的时间复杂度为O(n^2)。而最好情况下，划分得到的两个子序列规模差不多，即两个子序列的元素都不超过n/2。这时快速排序的性能将大幅提升，时间复杂度为O(nlogn)。好在快速排序的平均时间复杂度与最好情况下的时间复杂度差不多，而不是接近最坏情况下的时间复杂度。快速排序是所有内部排序算法中平均性能最优的排序算法。
由于快速排序需要借助递归工作栈来存储每一层函数调用的返回点和局部变量，而递归工作栈的容量与递归调用的最大深度一致，最好情况下空间复杂度为O(logn)。由于最坏情况下需要n-1调用，所以最坏情况下的空间复杂度为O(n)。因此，平均情况下空间复杂度为O(logn)。
在快速排序中，如果右边部分存在两个关键字相同，且均小于pivot基准元素时，则交换到左边部分后，两个元素的相对位置会发生变化，因此快速排序是不稳定的。因为每次交换都是从两边向中间进行，右边的ab交换后就变成左边的ba。
算法优化
快速排序优化的关键在于划分方法的选择，其目的都是为了让每次划分后两个子序列的规模差不多。比如，可以从待排序列的首尾和中间各选取三个元素，然后选择这三个元素的中间值作为最终的pivot基准元素。或者随机选择一个元素作为基准元素，这样能保证在实际排序中最坏情况几乎不会发生。此外，还可以在递归划分的子序列较小时，不再继续递归调用快速排序，而是改用直接插入排序进行后续的排序工作。
选择排序
算法简介
选择排序（简单选择排序）的基本思想是：每一趟（第i趟）都在剩下的n-i+1个元素中找到关键字最小的元素，作为有序子序列的第i个元素，这样每一趟都可以确定一个元素的最终位置。直到n-1趟做完只剩下1个元素，肯定是最大的，就排好序了。下面是选择排序的GIF动图演示：
代码实现
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
|
// 选择排序
public static int[] SelectSort(int[] a)
{
int len = a.Length;
// 关键字最小的元素的位置
int min;
// n-1趟
for (int i = 0; i < len - 1; i++)
{
// min默认为剩下的待排序列中的第一个位置
min = i;
// 找到剩下n-i+1个元素中关键字最小的元素的位置
for (int j = i + 1; j < len; j++)
{
if (a[j] < a[min])
{
min = j;
}
}
Swap(a, i, min);
}
return a;
}
// 数组元素交换函数
public static void Swap(int[] a, int i, int j)
{
int temp;
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
|
算法分析
选择排序的时间复杂度为O(n^2)，空间复杂度为O(1)。选择排序的性能与初始序列的状态无关，它是不稳定的。
堆排序
算法简介
堆排序是一种树形选择排序，它的基本思想是：将n个待排元素构建成一个大根堆（如果一个完全二叉的每个孩子结点的值都不小于其双亲结点的值，则称该完全二叉树为大根堆。反之，每个孩子结点的值都不超过其双亲结点的值，就称该完全二叉树为小根堆。），而完全二叉树一般采用顺序存储的方式，即用一个数组来存储这大根堆。
然后利用数组下标和完全二叉树结点编号的关系，在当前待排元素中找到关键字最大的元素，将其删除并放在堆的尾部，最后将堆中元素顺序输出就得到了一个有序序列。在完全二叉树，结点编号从1开始，第i个结点的左孩子编号为2i，右孩子编号为2i+1。但在数组中元素下标从0开始，因此第i个结点的左孩子为2i+1，右孩子为2i+2。
对堆进行插入操作时，先将待插元素按完全二叉树的顺序放在堆的末尾，然后根据堆的规则进行向上调整。删除堆顶元素时，先将堆的最后一个元素与堆顶元素进行交换，此时由于堆的性质被破坏，需要对此时的堆顶元素进行向下调整。建堆方法可以是边插入元素边向上调整；也可以是先将所有元素顺序存储在数组中，然后统一对编号为(n-1)/2取下整至1的根节点进行向下调整，使其左右子树满足大根堆或小根堆的规则。如果破坏了子树中已经建好的堆，就继续调整，直到以该结点为根的子树构成堆为止。下面是堆排序的GIF动图演示：
代码实现
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
55
56
57
58
|
// 堆排序
// 由于数组元素从0开始，所以堆的最后一个元素位置len=数组Length-1。
// 且第i个结点的左孩子为2i+1，右孩子为2i+2，双亲结点(i-1)/2。
public static int[] HeapSort(int[] a, int len)
{
// 构建初始大根堆
BuildMaxHeap(a, len);
for (int i = len; i > 0; i--)
{
// 删除堆顶元素时，先将堆顶元素与最后一个元素进行交换，这样就会将序列中最大的元素放在序列的最后一个位置。
// 第二大放在倒数第二，依次类推，直到最后删除的堆顶元素就是最小的，放在第一个位置并完成排序。
Swap(a, i, 0);
// 每次交换后，都有一个当前最大元素被放在堆的末尾，即确定当前最大元素的位置。
// 交换后，堆的性质被破坏，需要从堆的根节点开始向下调整，最后一个元素已经确定位置就不再参与堆的调整。
SiftDown(a, 0, i - 1);
}
return a;
}
// 构建初始大根堆
private static void BuildMaxHeap(int[] a, int len)
{
// 从最后一个根节点开始，依次向下调整，直到以根节点的子树全部完成建堆。
for (int i = (len - 1) / 2; i >= 0; i--)
{
SiftDown(a, i, len);
}
}
// 向下调整函数，将根节点的值与左右子树中最大的值比较，如果大于它就直接退出循环，没有调整，其对应子树也不会变化。
private static void SiftDown(int[] a, int i, int len)
{
int temp = a[i];
int j;
// 如果左子树大于len，表示左子树不存在，则该结点为叶子结点没有子树，退出循环。
while (2 * i + 1 <= len)
{
j = 2 * i + 1;
// 如果右子树存在，就找出左右子树中最大的值与根节点的值进行比较
if (j + 1 <= len && a[j] < a[j + 1])
{
j++;
}
// 如果根节点的值大于子树中最大的值，则满足大根堆的性质，直接退出循环。
// 没有调整，其对应子树也不会变化，所以不用继续循环判断其子树是否需要调整。
if (temp >= a[j])
{
break;
}
// 如果根节点的值小于子树中最大的值，则不满足大根堆的性质，调整根节点的值。
a[i] = a[j];
// 结点的值发生变化，继续向下判断下一级子树是否需要调整，直到以该根节点的子树全部完成建堆。
i = j;
}
// 该根节点的子树全部完成建堆后，将最初的根节点值赋给现在。
a[i] = temp;
}
|
算法分析
堆排序过程中，建堆时间为O(n)，接着需要n-1趟交换和向下调整，每次调整的时间取决于完全二叉树的高度为O(logn)，因此堆排序的总时间复杂度为O(nlogn)。堆排序的空间复杂度为O(1)，它是不稳定的。
归并排序
算法简介
归并排序与上面的基于交换、选择等排序的思想不一样，“归并”的含义是将两个或两个以上的有序表合并成一个新的有序表。归并排序采用分治法的策略，它的基本思想是：将n个待排元素看成n个只含有一个元素的有序子序列，然后两两合并，得到n/2个长度为2或1的新的有序子序列；再两两合并，……，直到最终合并成一个长度为n的有序表，这种排序方法称为2-路归井排序。如果排序过程中每次都是多个子序列进行合并，就称为多路归并排序。
2-路归并排序的基本步骤为：
1、把一个序列分解成两个有序子序列。
2、从两个子序列的第一个元素开始，选取两个元素中最小的一个元素赋值给辅助数组，然后该元素就不再参与下一次比较。第二次又从两个子序列的剩下元素中选择各自的第一个元素进行比较并赋值给辅助数组。如此往复，直到其中一个子序列中的元素比较完。
3、将其中一个没有比较完的子序列的剩下元素全部依次赋值给辅助数组。由于两个子序列都是有序的，且比较小的元素已经赋值给辅助数组了，剩下的元素绝对比辅助数组中之前的元素大。所以这时的辅助数组就是一个新的有序序列了。
如果给定两个有序子序列[1, 2, 3]和[4, 5, 6]，按照上面的步骤：首先1和4比较1小，1赋值给辅助数组的第一个位置。接着2和4比较还是2小，2继续赋值给辅助数组。同理可得，3也赋值给辅助数组。这时第一个子序列已经比较完了，所以就直接把第二个子序列中剩下的4，5，6依次赋值给辅助数组。此时辅助数组为[1, 2, 3, 4, 5, 6]是两个子序列合并后的有序序列。
但通常给定的一个数组是乱序的，此时就要对数组进行分解，把n个元素的数组分解成n个只有一个元素的有序子序列。然后对每一对有序子序列进行归并排序，这样就形成了多个有两个或1个元素（当n为奇数时）的有序子序列，接着对上一轮的归并结果继续归并排序，……，直到最后归并成一个有序序列。从上面的归并过程看出，归并排序其实是一个递归排序的过程，每一次递归包括分解子序列和合并子序列。下面以序列{ 1, 5, 2, 6, 3, 8, 4, 0, 9, 7 }为例，演示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
55
56
57
58
59
60
61
|
// 归并排序
public static void MergeSort(int[] a, int low, int high)
{
// 只有序列中至少有2个元素时，即low < high时，才进行分解和合并（归并排序）。
if (low < high)
{
// 从序列的中间位置进行分解
int mid = low + (high - low) / 2;
// 对左边的子序列a[low...mid]继续进行分解
MergeSort(a, low, mid);
// 对右边的子序列a[mid+1...high]继续进行分解
MergeSort(a, mid + 1, high);
// 当两个子序列a[low...mid]和a[mid+1...high]内部有序时，合并这个两个子序列为一个有序序列
// 数组中的每个元素可以视为只有一个元素的有序子序列
Merge(a, low, mid, high);
}
}
// 合并两个子序列为一个有序序列
private static void Merge(int[] a, int low, int mid, int high)
{
// 获取两个子序列a[low...mid]和a[mid+1...high]的长度之和
int len = high - low + 1;
// 新建一个临时的辅助数组，用于存放合并后的有序序列
int[] temp = new int[len];
// 第一个子序列的开始位置
int i = low;
// 第二个子序列的开始位置
int j = mid + 1;
// 辅助数组temp的开始位置
int k = 0;
// 从两个子序列的第一个元素开始比较，选择一个最小的元素依次放在temp中
while (i <= mid && j <= high)
{
if (a[i] <= a[j])
{
// k++不管是等号左边还是右边，都是先赋值后k再加1
// 赋值后就指向下一个元素
temp[k++] = a[i++];
}
else
{
temp[k++] = a[j++];
}
}
// 如果第二个子序列比较完了，而第一个子序列还有元素没比较完，就第一个子序列把剩下的元素全部赋值给temp剩下的空间，
// 因为两个子序列中小的元素已经移动到temp数组中了，剩下的元素肯定比之前的元素大，所以就直接依次放在temp的后面位置。
while (i <= mid)
{
temp[k++] = a[i++];
}
// 和上面同理，但这两个while循环每次合并时只执行一个
while (j <= high)
{
temp[k++] = a[j++];
}
// 把合并后的子序列temp再赋值给原先数组a的对应位置，准备下一次合并
Array.Copy(temp, 0, a, low, len);
}
|
算法分析
从示例的归并排序过程可以看出，归并排序的趟数为递归二叉树的深度log2n（取上整），而每一趟归并排序的时间复杂度为O(n)，因此归并排序的时间复杂度为O(nlogn)。归并排序在Merge函数合并子序列过程中，总共需要n个内存单元的辅助数组存放有序序列。由于归并排序是一个递归排序的过程，因此需要借助递归工作栈，栈的容量为递归二叉树的深度log2n（取上整）。因此归并排序的空间复杂度为O(n+logn)。此外，在Merge函数合并子序列时不会改变关键字相同元素的相对位置，因此归并排序是稳定的。
算法优化
在实际开发中，从单个待排元素开始两两归并的效率太低，通常和直接插入排序一起使用。即在分解得到的子序列比较小时，不再进行归并排序，而是使用直接插入排序得到有序子序列，然后再两两归并。直接插入排序是稳定的，因此优化后的归并排序仍是稳定的。优化后的归并排序的代码如下：
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
|
// 优化后的归并排序
public static void MergeSort(int[] a, int low, int high)
{
// 只有当序列中至少有5个元素时，才进行分解和合并（归并排序）。
if (high - low >= 5)
{
int mid = low + (high - low) / 2;
// MergeSort函数不变
MergeSort(a, low, mid);
MergeSort(a, mid + 1, high);
Merge(a, low, mid, high);
}
// 当分解得到的子序列个数小于5时，不再进行归并排序，直接采用直接插入排序。
if (high - low > 0 && high - low < 5)
{
InsertSort(a, low, high);
}
}
// 直接插入排序函数重载
public static void InsertSort(int[] a, int low, int high)
{
int len = a.Length;
int preIndex, current;
for (int i = low + 1; i <= high; i++)
{
preIndex = i - 1;
current = a[i];
while (preIndex >= 0 && current < a[preIndex])
{
a[preIndex + 1] = a[preIndex];
preIndex--;
}
a[preIndex + 1] = current;
}
}
|
计数排序
算法简介
计数排序一般用于n个0到k的整数序列的排序，需要借助一个长度为k+1的辅助数组c，其中c[i]表示待排序表a中值为i的元素出现的次数，然后根据辅助数组c来确定待排序表a中元素的位置。计数排序是一种稳定的线性时间排序算法，时间复杂度为O(n+k)，空间复杂度也是O(n+k)。计数排序不是基于比较的排序，其排序速度快于任何比较排序算法。
以待排序列{1, 4, 0, 9}为例，计数排序的过程为：
1、遍历待排序列得到该序列的最小值0和最大值9，计算最大值9和最小值0之间的范围长度max-min+1=10。
2、创建一个长度为10的辅助数组c，数组c的下标从0开始到9分别对应待排序表中的元素，下标对应的值为该元素在待排序列中出现的次数。如果下标没有对应元素即该元素出现次数为0，则数组c中对应下标的值为0。在示例序列中，c[0]=0，c[1]=1，c[2]=0，……，依次类推，直到把所有待排元素出现的次数确定完。
3、更新数组c下标的值为输出元素做准备，数组c中每一个下标元素出现的次数，为之前所有元素出现的次数再加上自己的次数。即c[0]=0, c[1]=1，c[2]=1，……
4、为了保证待排序列中关键字相同元素的相对位置不变，即保证计数排序的稳定性，反向输出待排序表a中的元素，并新建一个临时数组b来存放a中的元素。每输出一个元素a[i]对应的c[i]次数就要减1，为下一次输出相同元素做准备。输出过程为：{9}，{0, 9}，{0, 4, 9}，{0, 1, 4, 9}，至此计数排序完成。下面是计数排序的GIF演示：
代码实现
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
55
56
57
|
// 计数排序
public static int[] CountSort(int[] a)
{
// 将数组长度用变量存储，避免在for循环中频繁获取数组长度降低性能。
int len = a.Length;
// 获取数组a的最小值与最大值
GetMaxMin(a, out int min, out int max);
// 获取数组a的数值范围的长度
int k = max - min + 1;
// 创建一个辅助数组c用于存放a中每个元素出现的次数，c[i]的值为a[i]出现的次数。
int[] c = new int[k];
// 创建一个临时数组b用于存储c数组反向输出的元素
int[] b = new int[len];
// 遍历a数组获取a[i]出现的次数，并赋值给对应的c[a[i]]
for (int i = 0; i < len; i++)
{
c[a[i]]++;
}
// 更新c数组中的次数为元素输出做准备，因此c[i]中值为之前所有的次数之和
for (int i = 1; i < k; i++)
{
c[i] += c[i - 1];
}
// 由于必须保证数组元素的相对位置不变，因此必须反向输出，后出现的元素对应的下标必须在b数组的后面。
// 由于次数是从开始，而数组下标从0开始，所以b数组存放时c[i]-1。
// 而下面的c[i]--是指c中当前元素输出后，次数减1并指向下一个相同的元素。
for (int i = len - 1; i >= 0; i--)
{
b[c[a[i]] - 1] = a[i];
c[a[i]]--;
}
return b;
}
// 获取数组的最小值和最大值
private static void GetMaxMin(int[] a, out int min, out int max)
{
int len = a.Length;
min = a[0];
max = a[0];
for (int i = 0; i < len; i++)
{
if (a[i] < min)
{
min = a[i];
}
if (a[i] > max)
{
max = a[i];
}
}
}
|
算法分析
计数排序突破了基于比较排序算法O(nlogn)的时间复杂度，它的时间复杂度为O(n+k)。因为计数排序直接通过数组下标来确定元素之间的位置，不要比较操作。但计数排序也有相应的不足，计数排序只能适用于序列的数值范围跨度不能太大的整数序列。如果不是整数就无法通过数组下标确定元素的位置，比如实数1.0和2.0之间有无数个数，只能通过限制小数的精度来解决部分问题。
其次，如果待排序列分布不均匀，序列的最大值与最小值之间跨度太大，就会使辅助数组浪费大量的内存空间。比如，对序列{1, 3, 5, 1000}进行计数排序，k为999，辅助数组需要申请k+1为1000个内存单元，但实际只用得到4个内存单元，所以造成了大量的内存空间的浪费。
算法优化
对于不是从0开始的整数序列，比如序列{91, 99, 93, 94, 90, 96}，就需要把每个元素转换成从0开始的元素才能与数组下标对应，即将每个元素都减去最小值90。下面是优化过的计数排序代码：
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
|
// 优化后的计数排序
public static int[] CountSort2(int[] a)
{
int len = a.Length;
GetMaxMin(a, out int min, out int max);
int k = max - min + 1;
int[] c = new int[k];
int[] b = new int[len];
for (int i = 0; i < len; i++)
{
c[a[i] - min]++;
}
for (int i = 1; i < k; i++)
{
c[i] += c[i - 1];
}
for (int i = len - 1; i >= 0; i--)
{
b[c[a[i] - min] - 1] = a[i];
c[a[i] - min]--;
}
// 还可以直接输出数组c，c数组下标i就是数组a的值，只有出现过的i才是数组a的元素。
//for (int i = 0, j = 0; i < k; i++)
//{
// while (c[i] > 0)
// {
// a[j++] = i;
// c[i]--;
// }
//}
return b;
}
|
桶排序
算法简介
桶排序是计数排序的升级版，只不过计数排序是通过辅助数组的下标确定元素位于哪个桶，而桶排序是通过元素的数值确定位于哪个桶，每个桶可以有多个不同的元素。桶排序的基本思想是：根据待排序列的数值范围（最大值和最小值之差）和每个桶的容量capacity，创建(max-min)/capacity+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
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
55
56
57
58
59
|
// 桶排序
public static int[] BucketSort(int[] a, int capacity)
{
// 参数capacity为每个桶的容量，即每个桶的元素个数。
int len = a.Length;
// 每个桶的索引
int index = 0;
// 获取数组a的最小值和最大值
GetMaxMin(a, out int min, out int max);
// 根据桶的容量和数组a的数值范围，确定桶的个数。
int bucketNum = (max - min) / capacity + 1;
// 创建一个桶数组，每个桶是一个List<int>，用于存放桶中的元素。
List<int>[] bucketList = new List<int>[bucketNum];
// 初始化每个桶对应的List<int>
for (int i = 0; i < bucketNum; i++)
{
bucketList[i] = new List<int>();
}
// 根据数组a中元素的值，计算元素位于哪个桶，再将该元素放进桶中，这样可以保证桶间有序。
for (int i = 0; i < len; i++)
{
index = (a[i] - min) / capacity;
bucketList[index].Add(a[i]);
}
// 桶间有序，但桶内无序，所以再在桶内进行直接插入排序。
for (int i = 0, j = 0; i < bucketNum; i++)
{
// 桶内直接插入排序
InsertSort(bucketList[i]);
// 只要每个桶内有序，再加上桶间有序，则整个序列就有序，所以直接依次将每个桶内的元素赋值给数组a。
foreach (int k in bucketList[i])
{
a[j++] = k;
}
}
return a;
}
// 直接插入排序函数重载
public static void InsertSort(List<int> a)
{
int len = a.Count;
int preIndex, current;
for (int i = 1; i < len; i++)
{
preIndex = i - 1;
current = a[i];
while (preIndex >= 0 && current < a[preIndex])
{
a[preIndex + 1] = a[preIndex];
preIndex--;
}
a[preIndex + 1] = current;
}
}
|
算法分析
桶排序最好情况下时间复杂度为O(n)，桶排序不受基于比较的排序算法O(nlogn)的时间复杂度限制，它的性能与桶的容量有关。如果桶容量过大，桶内排序时间就要增大，进而影响桶排序的性能。反之，桶容量过小，桶内排序的时间虽然减少了，但是桶的数量增多，浪费内存空间，桶间操作的时间也会增大。
基数排序
算法简介
基数排序结合了计数排序和桶排序的特点，也是基于非比较的排序算法。基数排序基于多关键字排序思想（即排序的依据不止一个），比如一个整数可以分别按照个位、十位和百位等的大小来排序。基数排序的基本思想是：从低位（个位）开始，依次提取待排序列的个位上的数字，然后按照低位数字的大小对待排序列进行排序。接着，在低位排序的基础上，依次提取待排序列的十位上的数字，然后再按照十位数字的大小对待排序列进行排序。如此反复，直到按最高位（序列最大值的最高位，没有的用0补上）大小的排序完成，至此，基数排序完成。
由于整数也可以表示字符串（如名字和日期），因此基数排序不仅仅用于整数排序。基数排序分为最高位优先（MSD）和最低位优先（LSD），对于整数排序而言采用最低位优先。从上面的过程看到，基数排序中后一位的排序结果会影响前一位的排序结果。如果按最高位优先对整数进行排序，按十位排序的结果会影响按百位排序的结果，但是十位上数字大的数不一定大，有可能百位上的数字小。反之百位数字（最高位为百位时）大的数肯定大。
基数排序中对每一个关键字位对应的数字序列可以采用计数排序，只不过数组下标对应的是关键字位上的数字，但是每一轮计数排序反向输出的数据元素是关键字位对应的整个整数。我们把每个整数按关键字位分配时称为“分配”操作，每一轮计数排序反向输出时称为“收集”操作，“收集”后的序列用于下一个关键字位的“分配”和“收集”。有多少个关键字位就需要多少次的“分配”和“收集”。下面是基数排序的GIF动图演示：
代码实现
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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
|
// 基数排序
public static int[] RadixSort(int[] a)
{
int len = a.Length;
// 获取数组中元素的最大位数
int d = MaxBit(a, len);
// 用于每轮计数排序反向输出时，存储a元素的临时数组
int[] b = new int[len];
// 用于每轮计数排序的辅助数组，即下标从0到9的10个桶，存储每个关键字位数字出现的次数。
int[] c = new int[10];
int i, j, k;
// 基数，即每个关键字位的权重
int radix = 1;
// 基数排序需要d趟，从最低位开始依次对每个关键字位进行“分配”和“收集”工作。
for (i = 0; i < d; i++)
{
// 每趟计数排序前，先将辅助数组中每个桶的元素清0
for (j = 0; j < 10; j++)
{
c[j] = 0;
}
// 计算该关键字位上每个数字出现的次数，这称为“分配”操作。
for (j = 0; j < len; j++)
{
// 没有这个关键字位的用0补上，即对应的k为0
k = (a[j] / radix) % 10;
c[k]++;
}
// 更新辅助数组元素出现的次数，为反向输出做准备
for (j = 1; j < 10; j++)
{
c[j] += c[j - 1];
}
// 与计数排序不同的是，这里反向输出的不是单个关键字位，而是单个关键字位对应的整数，这称为“收集”操作。
for (j = len - 1; j >= 0; j--)
{
k = (a[j] / radix) % 10;
b[c[k] - 1] = a[j];
c[k]--;
}
// 收集完成，将按该关键字位排序的结果覆盖原始数组，并用于按下一个关键字位排序的起始数组。
for (j = 0; j < len; j++)
{
a[j] = b[j];
}
// 按该关键字位排序完成，更新radix，准备下一趟的基数排序。
radix *= 10;
}
return a;
}
// 求数组的最大位数
private static int MaxBit(int[] a, int len)
{
int max = a[0];
// 最大位数
int d = 1;
int p = 10;
for (int i = 0; i < len; i++)
{
if (a[i] > max)
{
max = a[i];
}
}
while (max >= p)
{
max /= 10;
d++;
}
return d;
}
|
算法分析
基数排序的时间复杂度为(n*d)，d是待排序列的最大位数。d一般为常数且远小于n，所以基数排序的时间复杂度一般为O(n)。基数排序一般要快过基于比较的排序算法，比如快速排序。基数排序的空间复杂度为O(n+k)，k为桶的数量（组成这些数字的底数个数一般取10），而k一般也远小于n，所以基数排序的空间复杂度一般也为O(n)。由于基数排序每一趟都采用了计数排序，计数排序是稳定的，因此基数排序也是稳定的。
排序总结
上图中标红的排序算法均为实际开发中常用的重要算法，包括直接插入排序、快速排序、堆排序和归并排序。此外，可以用**“快些选堆”**来记住四个不稳定的排序算法，“些”表示希尔排序。从上图看出，基于比较的排序算法时间复杂度最小为O(nlogn)。因为，每次比较两个关键字的大小后，只会出现两种可能的结果<和>=，可以用一棵高度约为logn的二叉树来表示这个判定过程，因此比较类排序算法时间复杂度至少为O(nlogn)。
当数据量较小（n<50）时，可采用直接插入排序或简单选择排序算法。但由于直接插入排序的元素移动次数比简单选择排序多，因此当待排元素本身的信息量比较大时，采用简单选择排序较好。因为元素本身信息量较大时，频繁的移动会影响排序性能。
当待排序列基本有序时，可采用直接插入排序或冒泡排序。但使用冒泡排序时，要设置一个交换Flag。如果当前这一趟只有比较而没有交换，则表明待排序列已经有序，直接跳出循环结束排序。
当数据量较大时，则应该采用平均时间复杂度为O(nlogn)的算法：快速排序、堆排序和归并排序。如果不要求排序的稳定性，优先选择快速排序。快速排序是所有内部排序算法中平均性能最优的排序算法。尽管快速排序最坏情况下时间复杂度为O(n^2)，而堆排序最好、平均和最坏情况下时间复杂度都为O(nlogn)，且空间复杂度还是O(1)，但实际运用中快速排序的性能优于堆排序。
因为计算机读取数据时，会先将内存中相邻的数据读取一部分到Cache中，下次访问相邻元素时直接从Cache中读取，速度比直接从内存中读取更快。当Cache满了，又重新从内存中读取一部分数据覆盖之前的Cache数据。而堆排序中比较的两个元素往往间隔很大不相邻，这会导致之前从Cache读取中的数据已经被覆盖，又要重新从内存中读取之前的数据进行比较。所以堆排序读取a[i]元素实际所花的时间要比快速排序多，因此快速排序的实际性能更优。但如果对内存空间要求较高，可以采用堆排序，毕竟在时间复杂度为O(nlogn)的情况下空间复杂度仅为O(1)。
如果要求排序的稳定性且时间复杂度为O(nlogn)，可以采用归并排序。但在实际开发中，从单个待排元素开始两两归并的效率太低，通常和直接插入排序一起使用。即在分解得到的子序列比较小时，不再进行归并排序，而是使用直接插入排序得到有序子序列，然后再两两归并。直接插入排序是稳定的，因此优化后的归并排序仍是稳定的。
部分内容和GIF参考自[十大经典排序算法（动图演示）