排序算法总结
这里总结如下算法：
- 基于比较的排序算法： 冒泡排序 选择排序 插入排序 归并排序 快速排序
- 不基于比较的排序算法： 计数排序 基数排序
# 写在前面
这次的算法实现全都使用 C 语言，并不是说 C 有多好，只是因为 C 比较接近底层，掌握 C 的写法后，其他语言的写法也很好实现，其次，也是因为现在很多算法的讲解也使用 C。
然后，本文的算法实现可能还不够完美，虽然都经过了测试用例，但难免还有些疏忽，如有错误或是有更好的意见，欢迎提出。
# 基于比较的排序算法 - O (N^2)
# 冒泡排序
# 核心原理
从左到右，依次将较大的元素交换到后面，那么一次一次排序后，最大的元素就在数组末尾，然后不断重复。
给定一个 N 个元素的数组，冒泡法排序将：
- 如果元素大小关系不正确，交换这两个数（在本例中为 a> b）
- 比较一对相邻元素（a，b）
- 重复步骤 1 和 2，直到我们到达数组的末尾（最后一对是第（N-2）和（N-1）项，因为我们的数组从零开始）
- 到目前为止，最大的元素将在最后的位置。 然后我们将 N 减少 1，并重复步骤 1，直到 N = 1。
(引用 VisuAlgo)
可视化见 VisuAlgo
# 算法实现
#define BOOL size_t
#define FALSE 0
#define TRUE 1
// 原地排序
void bubbleSort(int *arr, int len)
{
BOOL exchanged = FALSE;
int last = len; //last 随着冒泡次数而减小
do
{
for (int i = 0; i < last; i++)
{
if (arr[i] > arr[i + 1])
{
// 交换前后项
//int 整数型可以使用这种算法，不使用中间变量
arr[i] ^= arr[i + 1];
arr[i + 1] ^= arr[i];
arr[i] ^= arr[i + 1];
// 交换过了
exchanged = TRUE;
}
}
last--;// 当 last 减到 0 时，说明已经遍历结束，结束排序
} while (exchanged && last > 0); // 如果一次冒泡后没有发生交换，说明数组已经有序，结束排序
}# 选择排序
# 核心原理
从左到右，选择未被排序的数里最小的那个，与数组第一个数交换，然后第二个… 不断重复。
给定 N 个项目和 L = 0 的数组，选择排序将：
- 在 [L … N-1] 范围内找出最小项目 X 的位置
- 用第 L 项交换 X
- 将下限 L 增加 1 并重复步骤 1 直到 L = N-2。
(引用 VisuAlgo)
可视化见 VisuAlgo
# 算法实现
// 原地排序
void selectSort(int *arr, int len)
{
for (int i = 0; i < len; i++)
{
// 找出未被排序的数里最小的那个
int min = arr[i];
int minIdx = i;
for (int j = i; j < len; j++)
{
if (min > arr[j])
{
min = arr[j];
minIdx = j;
}
}
// 交换
arr[minIdx] = arr[i];
arr[i] = min;
}
}# 插入排序
# 核心原理
将未排序的数依次插入到排序好的数中
插入排序类似于大多数人安排扑克牌的方式。
- 从你手中的一张牌开始
- 选择下一张卡并将其插入到正确的排序顺序中
- 对所有的卡重复上一步。
(引自 VisuAlgo)
可视化见 VisuAlgo
# 算法实现
// 原地排序
void insertSort(int *arr, int len)
{
for (int i = 1; i < len; i++) // 这里默认第一个数就是排好序的，所以索引从第二个数开始
{
// 将未排序的数插入到排序好的数中
for (int j = 0; j < i; j++)
{
if (arr[i] < arr[j]) // 插入
{
// 先缓存要插入的数，因为后面要移动前面的数列，会覆盖它
int n = arr[i];
// 移动数列
for (int k = i; k > j; k--)
arr[k] = arr[k - 1];
// 放入正确的位置
arr[j] = n;
}
}
}
}# 优点 & 缺点
# 优点
这几个排序算法比较简单，容易想到，也比较容易理解算法原理。
# 缺点
在数据量变大时，运行效率会非常低，不是很实用。
# 基于比较的排序算法 - O (N log N)
# 归并排序
# 核心原理
将待排序的数组一分为二，分别对左右数组排序，排序时再一分为二，直到分成单个元素，排序完成后再依次合并。
给定一个 N 个项目的数组，归并排序将：
- 将每对单个元素（默认情况下，已排序）归并为 2 个元素的有序数组
- 将 2 个元素的每对有序数组归并成 4 个元素的有序数组，重复这个过程…
- 最后一步：归并 2 个 N / 2 元素的排序数组（为了简化讨论，我们假设 N 是偶数）以获得完全排序的 N 个元素数组。
(引自 VisuAlgo)
可视化见 VisuAlgo
# 算法实现
注：需要 O (n) 的额外空间
// 借助临时数组进行排序
void merge(int *arr, int low, int mid, int high) // 归并排序子函数
{
int N = high - low + 1; // 要排序的数字个数
int *b = (int *)malloc(N * sizeof(int)); // 创建一个新的数组用来排序
int lIdx = low, rIdx = mid + 1, bIdx = 0; //lIdx-> 左边数组索引，rIdx-> 右边数组索引，bIdx-> 数组 b 的索引
// 因为在 low~mid 和 mid+1~high 之间的数都是有序的（从小到大的），所以可以这样
while (lIdx <= mid && rIdx <= high)
{
if (arr[lIdx] < arr[rIdx])
{
b[bIdx] = arr[lIdx];
lIdx++;
}
else
{
b[bIdx] = arr[rIdx];
rIdx++;
}
bIdx++;
}
// 可能左数组或右数组还有剩余项
// 比如：左数组所有数都小于右数组数的情况下
while (lIdx <= mid)
b[bIdx++] = arr[lIdx++];
while (rIdx <= high)
b[bIdx++] = arr[rIdx++];
// 现在数组 b 中是已经排好序的数，再给它们复制回 arr 中
for (int i = 0, j = low; i < N; i++, j++)
{
arr[j] = b[i];
}
free(b);
}
void mergeSort(int *arr, int low, int high) // 归并排序
{
if (low < high)
{
// 将待排序的数组一分为二，递归
int mid = (low + high) / 2;
mergeSort(arr, low, mid);
mergeSort(arr, mid + 1, high); // 注：这里的 mid+1 只要和 merge 子函数里 rIdx 的值保持相同就行
// 归并
merge(arr, low, mid, high); //mid 从这里传入，在 merge 子函数中 rIdx=mid+1
}
}在此基础上还可以加以改进，使得归并排序在原地排序（不借用中间数组），降低空间复杂度，但是似乎会提升时间复杂度O(N log^2 N)-wikipedia。
# 快速排序 - O (N^2)/O (N log N)
# 核心原理
- 经典的快速排序 - O (N^2)/O (N log N)：在一开始先选择第一个数作为枢轴点 p，遍历剩余数，把所有小于 p 的数放在左边，所有大于 p 的数放在右边，然后把 p 放在中间；然后对左边的数组和右边的数组再分别重复上面的步骤。（不稳定）
- 随机快速排序 - O (N log N)：在经典快速排序的基础上，每次随机选择枢轴点 p。（比较稳定）
划分步骤：
- 选择一个项目 p（称为枢轴点）
- 然后将 a [i…j] 的项目分为三部分：a [i…m-1]，a [m] 和 a [m + 1…j]。 a [i…m-1]（可能为空）包含小于 p 的项目。 a [m] 是枢轴点 p，例如：指数 m 是已排序数组 a 的排序顺序中 p 的正确位置。 a [m + 1…j]（可能为空）包含大于或等于 p 的项目。
- 然后，递归地对这两部分进行排序。
可视化见 VisuAlgo
# 算法实现
// 原地排序
int partition(int *arr, int low, int high) // 快速排序子函数 - 划分
{
int p = arr[low]; // 选取第一个数作为枢轴点
int m = low; // 分界点，因为左右区域一开始都是空的，所以 m 要在 0 的位置
for (int i = low + 1; i <= high; i++)
{
// 如果 arr [i]>=p，什么都不用做，继续下一次循环即可 (i++)
if (arr[i] < p)
{
// 这里的算法详见 https://visualgo.net/zh/sorting?slide=12-6
m++;
// 交换 arr [m] 和 arr [i]
int tmp = arr[m];
arr[m] = arr[i];
arr[i] = tmp;
// 进入下一次循环 i++
}
}
// 交换枢轴点和分界点
arr[low] = arr[m];
arr[m] = p;
// 返回枢轴点所在位置
return m;
}
void quickSort(int *arr, int low, int high)// 快速排序
{
if (low < high) // 如果 low>high，说明已经划分为单个
{
// 先划分为左右两个区域
int m = partition(arr, low, high);
// 再递归对左右两个区域排序
// 注：m 所在位置已经在正确的位置了，所以不需要包括进去
quickSort(arr, low, m - 1);
quickSort(arr, m + 1, high);
}
}上面是经典快速排序，使用随机快速排序只需要让 p 随机选取即可。
int partition(int *arr, int low, int high) // 快速排序子函数 - 划分
{
int pIdx = (rand() % (high - low + 1)) + low; // 随机选取 [low,high]
// 交换 arr [pIdx] 和 arr [low]
int p = arr[pIdx];
arr[pIdx] = arr[low];
arr[low] = p;
int m = low; // 分界点，因为左右区域一开始都是空的，所以 m 要在 0 的位置
for (int i = low + 1; i <= high; i++)
{
// 如果 arr [i]>=p，什么都不用做，继续下一次循环即可 (i++)
if (arr[i] < p)
{
// 这里的算法详见 https://visualgo.net/zh/sorting?slide=12-6
m++;
// 交换 arr [m] 和 arr [i]
int tmp = arr[m];
arr[m] = arr[i];
arr[i] = tmp;
// 进入下一次循环 i++
}
}
// 交换枢轴点和分界点
arr[low] = arr[m];
arr[m] = p;
// 返回枢轴点所在位置
return m;
}
void quickSort(int *arr, int low, int high) // 随机快速排序
{
srand((unsigned)time(NULL));
if (low < high) // 如果 low>high，说明已经划分为单个
{
// 先划分为左右两个区域
int m = partition(arr, low, high);
// 再递归对左右两个区域排序
// 注：m 所在位置已经在正确的位置了，所以不需要包括进去
quickSort(arr, low, m - 1);
quickSort(arr, m + 1, high);
}
}# 优点 & 缺点
# 优点
在基于比较的排序算法中已经是最快的了（当然还可以针对不同的数据继续优化），比较实用，在数据量大的情况下表现也不错，可能是现在使用最多的排序算法。
# 缺点
归并排序需要额外的空间，快速排序不是稳定的排序（即它会交换同样大小的数字的顺序）。
# 不基于比较的排序算法
# 计数排序 - O (n+k)
# 核心原理
针对小范围的自然数，统计每个数字出现的次数，然后按照从小到大依次输出。
如果要排序的项目是小范围的整数，我们可以计算每个整数（在这个小范围内）的出现频率，然后通过循环该小范围来按排序顺序输出项目。 (引自 VisuAlgo)
# 算法实现
注：需要 O (n+k) 的额外空间
// 借助临时数组排序
void countSort(int *arr, int len, int maxNum) // 计数排序
{
int *con = (int *)calloc(maxNum + 1, sizeof(int));
for (int i = 0; i < len; i++)
{
con[arr[i]]++; // 统计每个数字出现次数
}
for (int i = 0, idx = 0; i <= maxNum; i++)
{
while (con[i]-- > 0)
{
arr[idx++] = i; // 复制回去
}
}
free(con);
}# 基数排序 - O (kN)
# 核心原理
针对范围大但数位小的自然数，创建 10 个桶 (0-9)，按照指定数位，依次放入对应桶中，再放入顺序取出，对每个数位从低到高重复操作。
如果要排序的项目是大范围但小数位的整数，我们可以将计数排序（Counting Sort）思想与基数排序（Radix Sort）结合起来，以实现线性时间复杂度。 在基数排序中，我们将每个项目排序为一个 w 数字串（如果需要，我们填充小于 w 数字的前几个零的整数）。 对于最低有效位（最右边）到最高有效位（最左边），我们通过 N 个项目并将它们按照活动数字放到 10 个队列中（每个数字 [0…9] 一个），就好像 一个修改的计数排序，因为这保留了稳定性。 然后我们再次重新连接组，以便进行后续迭代。 (引自 VisuAlgo)
# 算法实现
注：需要 O (N+k) 的额外空间
void radixSort(int *arr, int len) // 基数排序
{
int N = len / 10; // 桶初始化可以装下的元素数 & 后续每次增加量
int count[10] = {0}; // 每个桶当前装载的元素数量
int maxCount[10] = {len}; // 每个桶当前能装下的最大元素数量，0 桶设置为 len，原因见下面
// 初始化桶
int **con = (int **)malloc(10 * sizeof(int *));
// 最后遍历完所有数位后，所有的数都会过一遍 0 桶，所以一开始就设置为 len 的长度
con[0] = (int *)malloc(len * sizeof(int));
for (int i = 1; i < 10; i++)
{
con[i] = (int *)malloc(N * sizeof(int));
maxCount[i] = N;
}
// 遍历每个数位
BOOL ended = FALSE;
for (int Bit = 10; Bit <= INT_MAX && !ended; Bit *= 10)
{
ended = TRUE;
for (int i = 0; i < len; i++)
{
// 提取当前数位，并将该数放入桶中
int radix = arr[i] % Bit / (Bit / 10); // 当前数位
if (count[radix] >= maxCount[radix])
{
// 桶满了，重新分配内存空间
maxCount[radix] *= 2;
con[radix] = (int *)realloc(con[radix], maxCount[radix] * sizeof(int *));
if (con[radix] == NULL)
{
// 内存分配失败
exit(0);
}
}
con[radix][count[radix]] = arr[i];
count[radix]++;
}
for (int i = 1; i < 10; i++)
{
// 判断是否已经遍历结束
if (count[i] > 0)
{
ended = FALSE;
break;
}
}
for (int i = 0, aIdx = 0; i < 10; i++)
{
// 把桶中的元素按照放入顺序放回数组
for (int cIdx = 0; cIdx < count[i]; cIdx++)
{
arr[aIdx++] = con[i][cIdx];
}
count[i] = 0;
}
}
for (int i = 0; i < 10; i++)
{
free(con[i]);
}
free(con);
}# 优点 & 缺点
# 优点
基于比较的算法有 O (N log N) 的时间复杂度下限，而这些不基于比较的排序可以突破这个下限，使时间复杂度降到线性，针对于特定的数据是最优解。
# 缺点
对数据类型的要求比较苛刻，只在一些特定的数据集时有效。
参考文章: VisuAlgo - 排序 Wikipedia - 排序算法
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2021-05-072，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录