排序的定义
排序就是重新排列表中的元素，使表中的元素满足按关键字有序的过程。
相关术语
- 稳定： 如果a原本在b的前面，而且a = b，排序之后a仍然在b的前面。
- 不稳定： 如果a原本在b的前面，而且a = b，排序之后a可能出现在b的后面。
- 时间复杂度： 一个算法执行所消耗的时间。
- 空间复杂度： 运行完一个程序所需内存的大小。
冒泡排序
基本思想： 对待排序列从前向后（从下标较小的元素开始）依次比较相邻元素的值，若为逆序（前面元素的值大于后面元素的值），则发生交换，使值较大的元素逐渐从前向后移，就像水底的气泡一样逐渐向上冒。第一趟冒泡的结果是将值最大的元素交换到待排序列的最后一个位置。下一趟冒泡时，前一趟确定最大元素不再参与比较，每趟冒泡的结果是把序列中值最大的元素放到序列的最终位置…这样最多有 n - 1 趟冒泡就能把所有元素排好序。
注： 如果某一趟排序过程中没有发生交换，则说明序列已经有序。
例： 原序列 array = { 9, 15, -1, 20, 9, 24, 3 }，使用冒泡排序完成对array数组由小到大的排序。
这里我们详细分析了前两趟的排序过程，后续每趟的分析过程以此类推…最终的分析结果如下。
代码实现
//冒泡排序
void BubbleSort(int array[], int n) { //array是待排序列数组，n是数组元素的个数
for (int i = 0; i < n - 1; i++) {
int flag = 0; //本趟冒泡是否发生交换的标志
for (int j = 0; j < n - i - 1; j++) {
if (array[j] > array[j + 1]) { //若为逆序（前面元素的值大于后面元素的值），则发生交换，置flag = 1
int temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
flag = 1;
}
}
if (flag == 0) { //若本趟遍历后没有发生交换，则说明序列已经有序
break;
}
}
}
简单选择排序
基本思想： 待排序列第 i 趟排序从 array[i - 1] ~ array[n - 1] 中选取值最小的元素，与 array[i - 1]交换，每一趟排序可以确定一个元素的最终位置，这样经过 n - 1 趟排序就可以让整个序列有序。
例： 原序列 array = { 18, -1, 9, 5, 21, 18, 14 }，使用简单选择排序完成对array 数组由小到大的排序。
代码实现
//简单选择排序
void SelectSort(int array[], int n) { //array是待排序列数组，n是数组元素的个数
for (int i = 0; i < n - 1; i++) {
int min = array[i]; //记录最小值
int minIndex = i; //记录最小值元素的位置
for (int j = i + 1; j < n; j++) {
if (array[j] < min) { //更新最小值和最小值元素的位置
min = array[j];
minIndex = j;
}
}
if (minIndex != i) { //交换（将最小值放入array[i]）
array[minIndex] = array[i];
array[i] = min;
}
}
}
直接插入排序
基本思想： 待排序列看作一个有序表和一个无序表，开始时有序表中只有一个元素，无序表中有 n - 1 个元素，排序过程中每次从无序表中取出第一个元素，将其与逆向遍历有序表的元素依次进行比较，把它插入到有序表中适当的位置，这样执行 n - 1 趟就能让整个序列有序。
例： 原序列 array = { 15, 1, 5, 26, -1, 17, 5 }，使用直接插入排序完成对array数组由小到大的排序。
代码实现
//直接插入排序
void InsertSort(int array[], int n) { //array是待排序列数组，n是数组元素的个数
for (int i = 1; i < n; i++) {
int insertVal = array[i]; //记录待插入元素
int index = i; //记录待插入位置
for (int j = i - 1; j >= 0; j--) { //从后向前查找待插入位置
if (insertVal < array[j]) {
array[j + 1] = array[j]; //向后移位（覆盖）
index = j; //更新待插入位置
}
}
if (index != i) {
array[index] = insertVal; //待插入元素放到最终位置
}
}
}
希尔排序
希尔排序是直接插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序。
基本思想： 待排序列按下标的一定增量分组，对每组使用直接插入排序，随着增量逐渐减小，整个序列的元素已呈“基本有序”，再对所有元素进行一次直接插入排序。
例： 原序列 array = { 23, 18, 29, 2, 7, 2, 13, -1 }，使用希尔排序完成对 array数组由小到大的排序。
代码实现
//希尔排序
void ShellSort(int array[], int n) { //array是待排序列数组，n是数组元素的个数
for (int gap = n / 2; gap > 0; gap /= 2) { //增量gap，进行分组
for (int i = gap; i < n; i++) { //从第gap个元素开始，逐个对其所在组进行直接插入排序
int insertVal = array[i]; //记录待插入元素
int index = i; //记录待插入位置
for (int j = i - gap; j >= 0; j -= gap) {
if (insertVal < array[j]) {
array[j + gap] = array[j];
index = j;
}
}
if (index != i) {
array[index] = insertVal; //待插入元素放到最终位置
}
}
}
}
快速排序
基本思想： 在待排序列中任取一个元素作为枢轴（或基准，通常取序列第一个元素），通过一趟排序将待排序序列划分为两部分，其中一部分所有元素都小于枢轴元素，另一部分元素都大于等于枢轴元素，再将枢轴元素放到最终位置。然后分别递归地对两部分元素重复上述过程，直到每部分内只有一个元素或空为止，就可以让整个序列有序。
例： 原序列 array = { 11, 34, 7, 23, -1, 30, 7, 16 }，使用快速排序完成对array数组由小到大的排序。
这里我们详细分析了第1趟的排序过程，后续每趟的分析过程以此类推…最终的分析结果如下。
代码实现
//快速排序
void QuickSort(int array[], int low, int high) { //array是待排序列数组，low是第一个元素的下标，high是最后一个元素的下标
if (low >= high) { //只有一个元素或区间不存在
return;
}
int left = low;
int right = high;
int pivot = array[left]; //第一个元素为枢轴
while (left < right) {
while (left < right && array[right] >= pivot) { //查找比枢轴小的元素
right--;
}
array[left] = array[right]; //将比枢轴小的元素移动到左端
while (left < right && array[left] < pivot) { //查找比枢轴大的元素
left++;
}
array[right] = array[left]; //将比枢轴大的元素移动到右端
}
array[left] = pivot; //将枢轴元素放到最终位置
QuickSort(array, low, left - 1); //对所有比枢轴小的元素进行递归排序
QuickSort(array, left + 1, high); //对所有比枢轴大的元素进行递归排序
}
归并排序
基本思想： 采用分治策略（分治法将一个大问题分成若干个小问题然后递归求解），将待排序列分为若干子序列，每个子序列都是有序的，再对子序列进行归并。”归并“是将两个或两个以上的有序表组合成一个新的有序表。
例： 原序列 array = { 25, 3, 17, 0, 11, 36, 17, -2 }，使用归并排序完成对array数组由小到大的排序。
这里我们详细分析了第7趟的排序过程，前面每趟的分析过程以此类推…最终的分析结果如下。
代码实现
//归并
void Merge(int array[], int low, int mid, int high) { //array是待排序列数组，low是第一个元素的下标，mid是中间元素的下标，high是最后一个元素的下标
int temp[high - low + 1]; //temp辅助数组
int i = low; //左侧子序列的初始索引
int j = mid + 1; //右侧子序列的初始索引
int k = 0; //temp数组的索引
while (i <= mid && j <= high) {
if (array[i] <= array[j]) { //左侧子序列的当前元素小于等于右侧子序列的当前元素
temp[k++] = array[i++]; //左侧子序列的当前元素加入temp数组
} else {
temp[k++] = array[j++]; //右侧子序列的当前元素加入temp数组
}
}
while (i <= mid) { //左侧子序列的剩余元素加入temp数组
temp[k++] = array[i++];
}
while (j <= high) { //右侧子序列的剩余元素加入temp数组
temp[k++] = array[j++];
}
k = 0;
for (int tempLeft = low; tempLeft <= high; tempLeft++) { //将temp数组的元素复制到原数组
array[tempLeft] = temp[k++];
}
}
//归并排序
void MergeSort(int array[], int low, int high) { //array是待排序列数组，low是第一个元素的下标，high是最后一个元素的下标
if (low >= high) { //只有一个元素或区间不存在
return;
}
int mid = (low + high) / 2; //中间索引（从中间划分为两个子序列
MergeSort(array, low, mid); //对左侧子序列进行递归排序
MergeSort(array, mid + 1, high); //对右侧子序列进行递归排序
Merge(array, low, mid, high); //归并
}
堆排序
基本思想： 待排序列构造成一个大顶堆（根 > 左、右），堆顶元素就是最大值，将其与末尾元素进行交换，然后将剩余 n - 1 个元素重新构建成一个堆，这样就会得到次最大值，如此反复执行，就可以使整个序列有序。
注： 顺序存储的“完全二叉树”，结点 i 的左子结点是 2i，右子结点是 2i + 1，父结点是 i / 2。
例： 原序列 array = { 16, 9, 23, -1, 28, 37, 1, 9 }，使用堆排序完成对array数组由小到大的排序。
这里我们详细分析了第1趟的排序过程，后续每趟的分析过程以此类推…最终的分析结果如下。
代码实现
//构建大顶堆
void AdjustHeap(int array[], int i, int n) { //array是待排序列数组，k是子树根结点的索引，n是数组元素的个数
int temp = array[i]; //保存子树根结点的值
for (int k = 2 * i + 1; k < n; k = 2 * k + 1) { //k = 2 * i + 1是 i 结点的左子结点
if (k + 1 < n && array[k] < array[k + 1]) { //左子结点的值小于右子结点的值
k++; //k指向右子结点
}
if (array[k] > temp) { //子结点的值大于父结点的值
array[i] = array[k]; //将较大值赋给根结点
i = k; //更新i的位置，继续循环比较
} else {
break;
}
}
array[i] = temp; //将temp的值放到最终位置
}
//堆排序
void HeapSort(int array[], int n) { //array是待排序列数组，n是数组元素的个数
for (int i = n / 2 - 1; i >= 0; i--) { //将待排序列构建成大顶堆
AdjustHeap(array, i, n);
}
for (int j = n - 1; j > 0; j--) {
int temp = array[j]; //堆顶元素与末尾元素交换，将最大元素“沉”到数组末尾
array[j] = array[0];
array[0] = temp;
AdjustHeap(array, 0, j); //剩余j个元素重新调整成大顶堆
}
}
基数排序
基本思想： 将整数按位数切割成不同的数字，然后按每个位数分别比较，使其放入对应的“桶”中，达到排序的作用。
注： 待排序数组最小值为负数，通过让各元素先减去最小值，使每个元素的值都大于等于0，然后再进行基数排序，最后一趟排序后再加上最小值，恢复数据。
例： 原序列 array = { 94, 205, 160, 3, 36, 239, -7, 160 }，使用基数排序完成对array数组由小到大的排序。
代码实现
//基数排序
void RadixSort(int array[], int n) { //array是待排序列数组，n是数组元素的个数
int bucket[10][n]; //二维数组表示10个桶，每个桶是1个一维数组
int num[10]; //记录每个桶放入元素的个数
int step = 10; //步长
int len = 1; //记录数组最大值的位数
int max = array[0]; //记录数组的最大值
int min = array[0]; //记录数组的最小值
for (int i = 1; i < n; i++) {
if (array[i] < min) { //得到数组的最小值
min = array[i];
}
}
if (min < 0) { //最小值为负数
for (int i = 0; i < n; i++) { //通过让各元素先减去最小值（最后一趟排序后再加上最小值，保持数据一致），使每个元素的值都大于等于0
array[i] -= min;
}
}
for (int i = 1; i < n; i++) {
if (array[i] > max) { //得到数组的最大值
max = array[i];
}
}
while (max / step != 0) { //得到最大值的位数
len++;
step *= 10;
}
for (int i = 0; i < 10; i++) { //初始化每个桶中元素的个数
num[i] = 0;
}
for (int i = 0, t = 1; i < len; i++, t *= 10) { //针对每个元素对应位进行排序（第1次是个位，第2次十位，第3次百位...）
int count = 0;
for (int j = 0; j < n; j++) {
int digit = array[j] / t % 10; //取出各元素对应位的值
bucket[digit][num[digit]++] = array[j]; //放入对应的桶中
}
for (int j = 0; j < 10; j++) { //遍历所有的桶
if (num[j] != 0) { //桶中有元素
for (int k = 0; k < num[j]; k++) { //将桶中的数据放入到原数组
if (i == len - 1 && min < 0) { //如果是最后一趟，且最小值小于0，需要给各元素加上最小值
array[count++] = bucket[j][k] + min;
} else {
array[count++] = bucket[j][k];
}
}
}
num[j] = 0; //重置每个桶中元素的个数
}
}
}
计数排序
基本思想： 统计待排序数组中各元素出现的次数，然后依次放入原数组，就能使序列有序。
例： 原序列 array = { 15, 13, 10, 12, 13, 14, 11, 10 }，使用计数排序完成对array数组由小到大的排序。
代码实现
//计数排序
void CountSort(int array[], int n) { //array是待排序列数组，n是数组元素的个数
int temp[n]; //辅助数组
int max = array[0]; //记录数组的最大值
int min = array[0]; //记录数组的最小值
for (int i = 1; i < n; i++) {
if (array[i] > max) { //得到数组的最大值
max = array[i];
}
if (array[i] < min) { //得到数组的最小值
min = array[i];
}
}
int len = max - min + 1; //计数数组的长度
int count[len]; //计数数组，统计待排序数组中各元素出现的次数
for (int i = 0; i < len; i++) { //初始化计数数组
count[i] = 0;
}
for (int i = 0; i < n; i++) { //减去min是为了让数据从count[0]位置开始存储（将待排序列数组元素映射到计数数组对应位置）
count[array[i] - min]++;
}
for (int i = 1; i < len; i++) { //计数数组转化为累计数组
count[i] = count[i] + count[i - 1];
}
for (int i = n - 1; i >= 0; i--) { //逆序遍历待排序数组
temp[--count[array[i] - min]] = array[i]; //将元素放到最终位置
}
for (int i = 0; i < n; i++) { //将temp数组的元素复制到原数组
array[i] = temp[i];
}
}
桶排序
基本思想： 待排序序列所有元素分配到桶里，再对每个桶中的元素进行排序，最后依次将每个桶中的元素按顺序放到原数组，就能得到一个有序的序列。
例： 原序列 array = { 5, 26, 17, 1, 21, -3, 17, 10 }，使用桶排序完成对array数组由小到大的排序。
代码实现
//桶排序
void BucketSort(int array[], int n) { //array是待排序列数组，n是数组元素的个数
int max = array[0]; //记录数组的最大值
int min = array[0]; //记录数组的最小值
for (int i = 1; i < n; i++) {
if (array[i] > max) { //得到数组的最大值
max = array[i];
}
if (array[i] < min) { //得到数组的最小值
min = array[i];
}
}
int len = (max - min) / n + 1; //桶的数量
int bucket[len][n]; //二维数组表示 num个桶，每个桶是1个一维数组
int num[len]; //记录每个桶放入元素的个数
for (int i = 0; i < len; i++) { //初始化每个桶中元素的个数
num[i] = 0;
}
for (int i = 0; i < n; i++) {
int digit = (array[i] - min) / n; //得到各元素对应桶的索引
bucket[digit][num[digit]++] = array[i]; //将元素放入对应的桶中
}
int count = 0;
for (int i = 0; i < len; i++) {
for (int j = 1; j < num[i]; j++) { //对每个桶内元素进行直接插入排序
int insertVal = bucket[i][j]; //记录待插入元素
int index = j; //记录待插入位置
for (int k = j - 1; k >= 0; k--) { //从后向前查找待插入位置
if (insertVal < bucket[i][k]) {
bucket[i][k + 1] = bucket[i][k]; //向后移位（覆盖）
index = k; //更新待插入位置
}
}
if (index != j) {
bucket[i][index] = insertVal; //待插入元素放到最终位置
}
}
for (int j = 0; j < num[i]; j++) { //将桶中的元素按顺序放入原数组
array[count++] = bucket[i][j];
}
}
}
总结
十大排序算法对比
注： n 为序列中元素的个数，k 为“桶”的个数。
应用
- 若 n 较小，可采用直接插入排序，但若记录本身信息量较大时，应选用简单选择排序。反之，若 n 较大，应选用快速排序，但若待排序列关键字“基本有序”时，可选用归并排序或堆排序。
- 当待排序列的关键字随机分布时，快速排序的平均时间最短，堆排序所需的辅助空间少于快速排序。若要求排序稳定，可选用归并排序。
- 快速排序和归并排序在 n 较小时性能不及直接插入排序，通常可以将它们和直接插入排序结合使用。如快速排序划分的子区间小于某值时，可调用直接插入排序。或对待排序列先逐段进行直接插入排序，然后再利用归并排序进行两两归并。
- 若 n 很大，待排序列关键字位数较少且可以分解时，采用基数排序较好。
综上所述，每种排序算法都有各自的优缺点，适合在不同的环境下使用，就其全面性而言，很难提出一种被认为是最好的算法。我们应根据具体的情况选择合适的排序算法，也可以将多种排序算法相互结合使用。