最近更新于 2023-02-07 20:03
大纲
\begin{cases}
插入排序
\begin{cases}
直接插入排序 \\
折半插入排序 \\
希尔排序
\end{cases}
\\
交换排序
\begin{cases}
冒泡排序 \\
快速排序
\end{cases}
\\
选择排序
\begin{cases}
简单选择排序 \\
堆排序
\end{cases}
\\
归并排序 \\
基数排序
\end{cases}环境
平台工具集：Visual Studio 2022 v143
C 语言标准：C17
字符集：Unicode
注
默认升序
插入排序
直接插入排序
以 6 3 9 7 5 为例，将其分为有序数组和无序数组，初始有序数组成员为原数组第一个元素
6 | 3 9 7 5
第一轮：将无序数组第一个成员 3 提出来，并和有序数组最后一个成员 6 比较，3 小于 6，则有序数组最后一个成员往后移动一位
□ 6 | 9 7 5 (3)
有序数组已到头，则将提出来的 3 插入到空位
3 6 | 9 7 5
第二轮：将无序数组第一个成员 9 提出来，将其和有序数组最后一个元素 6 比较，9 大于 6 无序移动，则不移动
3 6 9 | 7 5
第三轮：将无序数组第一个元素 7 提出来，将其和有序数组最后一个元素 9 比较， 7 小于 9，将 7 往后移动一位
3 6 □ 9 | 5 (7)
再将 7 和有序数组倒数第二个元素 6 比较，7 大于 6，则不移动，并将提出来的 7 插入空位
3 6 7 9 | 5
第四轮：将无序数组第一个元素 5 提出来和有序数组最后一个元素 9 比较，5 小于 9，9 后移一位
3 6 7 □ 9 (5)
再将 5 和有序数组倒数第二个元素 7 比较，5 小于 7，7 后移一位
3 6 □ 7 9 (5)
再将 5 和有序数组倒数第三个元素 6 比较，5 小于 6，6 后移一位
3 □ 6 7 9 (5)
再将 5 和有序数组倒数第四个元素比较，5 大于 3，不移动，将提出来的 5 插入空位
3 5 6 7 9
直接插入法属于稳定的排序算法。时间复杂度为 O(n^2)。适用于待排序元素较少且元素基本有序的情况。
void sort(int array[], int n)
{
for (int j, i = 1; i < n; ++i)
{
int tmp = array[i];
for (j = i - 1; j >= 0 && tmp < array[j]; --j)
{
array[j + 1] = array[j];
}
array[j + 1] = tmp;
}
}
折半插入排序
折半插入排序是直接插入排序的改进算法，大体类似，都是先分一个有序数组出来，再挨个把无序数组元素插入有序数组的适当位置。只是插入位置的查找方法不同，直接插入排序是挨个从有序数组的尾巴向开头比较，而折半插入排序使用折半查找算法，在查找部分的时间复杂度由 O(n) 降到 O(nlog_2n)，但是移动元素的时间复杂度依然没有改变，总体时间复杂度还是 O(n^2)。
折半插入排序也是稳定的排序算法。
适用于待排序元素较少且元素基本有序的情况。
void sort(int array[], int n)
{
int low, high;
for (int i = 1; i < n; ++i)
{
int tmp = array[i];
for (low = 0, high = i - 1; high >= low;)
{
int mid = (low + high) / 2;
if (tmp < array[mid])
{
high = mid - 1;
}
else
{
low = mid + 1;
}
}
for (int j = i - 1; j >= low; --j)
{
array[j + 1] = array[j];
}
array[low] = tmp;
}
}希尔排序
希尔排序是基于直接插入改进的，将待排序元素按照一定增量分为多个子序列（一般首次增量取总数一半），例如待排序的元素为 9 8 7 6 5 ，共 5 个，增量取 5 / 2 = 2
则先比较下标为 2 和 2-1=0 的两个数，提出 7，和 9 比较，9 大于 7，则 9 移动到 7 的位置，到头了，将提出的 7 插入 9 的位置，得到 7 8 9 6 5
接下来比较 3 和 3 – 1 = 1 …….
……
上面其实就是对每个子序列分别使用直接插入排序
增量下一次取上一次增量的一半 2 / 2 = 1，增量为 1 后，跑完这一轮就代表排序完成。
希尔排序是一种不稳定的排序算法。由于增量的选择是随机的，因此时间复杂度的计算就十分复杂，只是在一定的范围内，但是希尔排序也是第一个时间复杂度突破 O(n^2) 的排序算法
希尔排序主要用在数据量在 5000 以内，且对速度要求不高的场合。
void insert_sort(int array[], int n, int delta)
{
for (int i = delta; i < n; ++i)
{
if (array[i] < array[i - delta])
{
int k, tmp = array[i];
for (k = i - delta; k >= 0 && tmp < array[k]; k -= delta)
{
array[k + delta] = array[k];
}
array[k + delta] = tmp;
printArray(array, 9);
}
}
}
void sort(int array[], int n)
{
for (int delta = n / 2; delta >= 1; delta /= 2)
{
insert_sort(array, n, delta);
}
}以 9 8 7 6 5 4 3 2 1 为例，共 n = 9，初始 delta = n / 2 = 4
| [0] | [1] | [2] | [3] | [4] | [5] | [6] | [7] | [8] | delta | i | k |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 4 | 4 | 0 |
| 5 | 8 | 7 | 6 | 9 | 4 | 3 | 2 | 1 | 5 | 1 | |
| 5 | 4 | 7 | 6 | 9 | 8 | 3 | 2 | 1 | 6 | 2 | |
| 5 | 4 | 3 | 6 | 9 | 8 | 7 | 2 | 1 | 7 | 3 | |
| 5 | 4 | 3 | 2 | 9 | 8 | 7 | 6 | 1 | 8 | 4 | |
| 5 | 4 | 3 | 2 | 8 | 7 | 6 | 9 | 0 | |||
| 1 | 4 | 3 | 2 | 5 | 8 | 7 | 6 | 9 | 2 | 2 | 0 |
| 3 | 1 | ||||||||||
| 1 | 2 | 3 | 4 | 5 | 8 | 7 | 6 | 9 | 4 | 2 | |
| 0 | |||||||||||
| 5 | 3 | ||||||||||
| 1 | |||||||||||
| 6 | 4 | ||||||||||
| 6 | 2 | ||||||||||
| 6 | 0 | ||||||||||
| 7 | 5 | ||||||||||
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |||
| … | … | … | … | … | … | … | … | … | … | … | … |
交换排序
冒泡排序
冒泡排序思路非常简单，第一轮将第一个和第二个比较，前者大，两个就交换位置，然后比较第二个和第三个，第三个和第四个……倒数第二个和最后一个，一轮完毕最大的数就在最后一个
第二轮，还是一样，第一个和第二个比较….倒数第三个和倒数第二个比较，此轮完毕，倒数第二大的数就在倒数第二个位置
第三轮,……倒数第四个和倒数第三个比较，此轮完毕，倒数第三大的数就在倒数第三个位置
……
冒泡排序是一种稳定的排序方法。时间复杂度为 O(n^2)，适用于待排序元素较少，且对时间要求不高的场合。
void sort(int array[], int n)
{
for (int i = 1; i < n; ++i)
{
for (int j = 0; j < n - i; ++j)
{
if (array[j] > array[j + 1])
{
int tmp = array[j + 1];
array[j + 1] = array[j];
array[j] = tmp;
}
}
}
}快速排序 –
选择排序
简单选择排序
简单选择排序的思想感觉和冒泡排序比较相似。
简单选择排序，每一轮找出未排序部分的最小值的下标，然后将这个最小值和当前轮次对应下标的数交换。比如第一轮找出的最小值和下标 0 交换，第二轮从下标 1 开始找最小值记录其下标，然后将最小值和下标 1 的数交换，第三轮从下标 2 开始找最小值，接着和下标 2 的数交换……
相比于冒泡排序，并不需要每次都去交换，只需要记录其下标，直到本轮找到最小值，最后才交换，性能会好一点
时间复杂度为 O(n^2)，适用于数据量小对事件要求不高的场合。
void sort(int array[], int n)
{
for (int i = 0; i < n - 1; ++i)
{
int minIdx = i;
for (int j = i + 1; j < n; ++j)
{
if (array[minIdx] > array[j])
{
minIdx = j;
}
}
if (minIdx != i)
{
int tmp = array[i];
array[i] = array[minIdx];
array[minIdx] = tmp;
}
}
}