目录
- 1. 各种排序算法的分类
- 2. 插入排序
- 2.1 直接插入排序
- 2.2 希尔排序
- 3. 选择排序
- 3.1 选择排序
- 3.2 堆排序
- 4. 交换排序
- 4.1 冒泡排序
- 4.2 快速排序
- 4.2.1 霍尔法（hoare）
- 4.2.2 挖坑法（hole）
- 4.4.3 前后指针法
- 4.4.4 补充：非递归快排
- 4.5 快排优化
- 5. 归并排序
- 6. 非比较排序：计数排序
- 7. 排序算法的稳定性
1. 各种排序算法的分类
按照排序逻辑的不同，排序大体可以分为四大类：
- 插入排序
- 选择排序
- 交换排序
- 归并排序
接下来，我们进行这些排序的学习
！注：本章内容中的动图并非原创
2. 插入排序
2.1 直接插入排序
- 将整个数组的元素，从起始遍历，一次向后移动一步，看作是将一个元素插入到数组中。
- 在"插入"的过程中，当新插入的元素小于其前面的元素时，交换两者，循环此步骤，直至前面的元素不小于新插入的元素，到此成功插入一个元素。
过程演示：
void InsertSort(int* a, int n)
{
for (int i = 1; i < n; i++)
{
for (int j = i; a[j - 1] > a[j]; j--)
{
swap(&a[j - 1], &a[j]);
}
}
}
2.2 希尔排序
- 根据给定组距，进行数据的分组，组内进行插入排序。
- 不断减小组距，直至组距为1。
- 注：在组距不为1时，都是预排序，让数据更接近有序。
//多趟排
void ShellSort1(int* a, int n)
{
int gap = n / 2;
while (gap > 0)
{
for (int i = 0; i < gap; i++)
{
for (int j = i; j + gap < n; j += gap)
{
if (a[j] > a[j + gap])
{
swap(&a[j], &a[j + gap]);
}
}
}
gap /= 2;
}
}
//一趟排
void ShellSort2(int* a, int n)
{
int gap = n / 2;
while (gap > 0)
{
for (int i = 0; i + gap < n; i++)
{
if (a[i] > a[i + gap])
{
swap(&a[i], &a[i + gap]);
}
}
gap /= 2;
}
}
3. 选择排序
3.1 选择排序
- 遍历一次，从数据中选出最小（或最大）的数据放至数据首部。
- 多次遍历选择，直至将最后一个数据选走。
过程演示：
void SelectSort(int* a, int n)
{
for (int i = 0; i < n; i++)
{
int min = i;
for (int j = i; j < n; j++)
{
if (a[j] < a[min])
{
min = j;
}
}
swap(&a[i], &a[min]);
}
}
选择排序优化：
一次遍历选出最大值与最小值
void SelectSort2(int* a, int n)
{
for (int i = 0; i < n / 2; i++)
{
int max = i;
int min = i;
for (int j = i; j < n - i; j++)
{
if (a[j] > a[max])
{
max = j;
}
if (a[j] < a[min])
{
min = j;
}
}
swap(&a[max], &a[n - i - 1]);
swap(&a[min], &a[i]);
}
}
3.2 堆排序
- 建大堆
- 交换首尾，size–，向下调整，直到size为0
void AdjustDown(int* a, int n, int root)
{
int child = root * 2 + 1;
while (child < n)
{
if (child + 1 < n && a[child] < a[child + 1])
{
child++;
}
if (a[root] < a[child])
{
swap(&a[root], &a[child]);
}
root = child;
child = root * 2 + 1;
}
}
void HeapSort(int* a, int n)
{
//建大堆
for (int i = (n - 1 - 1) / 2; i >= 0; i--)
{
AdjustDown(a, n, i);
}
//交换首尾，调整
int size = n;
while (size > 0)
{
swap(&a[0], &a[size - 1]);
size--;
AdjustDown(a, size, 0);
}
}
4. 交换排序
4.1 冒泡排序
- 建立两个一前一后的指针，用这两个指针遍历整个数组
- 若后指针指向的数据大于前指针指向的数据，交换前后指针所指向的元素，之后两指针++，直至遍历完数据，得出一个最大数，需遍历的数据长度减1，此为遍历一趟。
- 多次遍历，当长度为0时，排序结束
过程演示：
void BubbleSort(int* arr, int n)
{
for (int i = 0; i < n; i++)
{
int flag = 1;
for (int j = 0; j + 1 < n - i; j++)
{
if (arr[j] > arr[j + 1])
{
swap(&arr[j], &arr[j + 1]);
flag = 0;
}
}
if (flag)
{
break;
}
}
}
4.2 快速排序
4.2.1 霍尔法（hoare）
- 将数据的首位确定为对照key，定义两个指针left（数据首部），right（数据尾部）。
- 右侧指针反向遍历数组，寻找小于key的值，当找到后停止，左侧指针正向遍历数组，寻找大于key的值，找到后将两指针指向的数据交换。
- 重复上述步骤2，直至左右指针相遇，交换key元素与左右指针同时指向的元素，此为一趟排序。
- 将数据分割为[0，key - 1]与[key + 1，n]，在这两个区间内再进行上述步骤2，3。直至所有元素的位置都被确认。
过程演示：
// 快速排序hoare版本
int PartSort1(int* a, int left, int right)
{
int key = left;
int keyi = a[key];
while (left < right)
{
while (left < right && a[right] >= keyi)
{
right--;
}
while (left < right && a[left] <= keyi)
{
left++;
}
swap(&a[left], &a[right]);
}
if (a[left] < keyi)
{
swap(&a[left], &a[key]);
key = left;
}
return key;
}
4.2.2 挖坑法（hole）
- 选择首位数据为key，然后将数据的首位标记为hole，创建两个指针left（首位 ），right（数据尾部）。
- 右侧指针找寻找小于key元素的值，找到后，将所找到的元素填充至挖好的"洞"里，此元素原位置标记为新的洞，然后，移动左侧指针寻找大于key元素的值，找到后，将找到的元素填入洞中。重复上述步骤，直至左右指针相遇，将key值填入左右指针相遇的位置，此时即确定好了key的位置。
- 在[left，key - 1]与[key + 1, right]的区间中，重复步骤2，直至所有位置都被确定。
过程演示：
int PartSort2(int* a, int left, int right)
{
int hole = left;
int keyi = a[hole];
while (left < right)
{
//额外检查，越界可能
while (left < right && a[right] >= keyi)
{
right--;
}
if (a[right] < keyi)
{
a[hole] = a[right];
hole = right;
}
while (left < right && a[left] <= keyi)
{
left++;
}
if (a[left] > keyi)
{
a[hole] = a[left];
hole = left;
}
}
a[hole] = keyi;
return hole;
}
void QuickSort(int* a, int left, int right)
{
if (left >= right)
{
return;
}
int key = PartSort2(a, left, right);
QuickSort(a, left, key - 1);
QuickSort(a, key + 1, right);
}
4.4.3 前后指针法
思路1：
- 将数据首位设置为key，创建两个指针pre（首部），cur（首部 + 1）。
- cur开始遍历整个数组，如果cur指针指向的值小于key，那么pre指针一同++，否则pre指针不动，直至cur再次寻找到小于key的值，此时，pre++，然后将两指针指向的值交换。如此，反复直至cur遍历完整个数组，最后，将key与pre指针指向的值交换。
- 在[left，key - 1]与[key + 1, right]的区间中，重复步骤2，直至所有位置都被确定。
思路2：
- [left + 1，pre]区间为小于key的值，[pre + 1，cur - 1]为大于key的值，[cur，right]为未遍历到的值。
- cur指针遍历寻找小于pre指针的数据，找到后pre++，交换两指针所指向的值。
过程演示：
int PartSort3(int* a, int left, int right)
{
int pre = left;
int cur = left + 1;
int keyi = a[left];
while (cur <= right)
{
if (a[cur] < keyi)
{
swap(&a[++pre], &a[cur]);
}
cur++;
}
swap(&a[left], &a[pre]);
return pre;
}
void QuickSort(int* a, int left, int right)
{
if (left >= right)
{
return;
}
int key = PartSort3(a, left, right);
QuickSort(a, left, key - 1);
QuickSort(a, key + 1, right);
}
4.4.4 补充：非递归快排
- 将原本递归传递的区间存储到栈中，用时从栈中取出
void QuickSortNonR(int* a, int left, int right)
{
Stack stack;
StackInit(&stack);
//插入第一次遍历区间范围
StackPush(&stack, left);
StackPush(&stack, right);
while (!StackEmpty(&stack))
{
//取出区间值进行运算
right = StackTop(&stack);
StackPop(&stack);
left = StackTop(&stack);
StackPop(&stack);
int key = PartSort3(a, left, right);
//区间遍历顺序：左区间，右区间
if (key + 1 < right)
{
StackPush(&stack, key + 1);
StackPush(&stack, right);
}
if (left < key - 1)
{
StackPush(&stack, left);
StackPush(&stack, key - 1);
}
}
}
4.5 快排优化
- 三数取中（getmid）
- 当递归到小区间时，可以转而进行插入排序
//三数取中
int GetMidNum(int* a, int left, int right)
{
int mid = (left + right) / 2;
if(a[mid] > a[left])
{
if(a[mid] < a[right])
{
return mid;
}
else
{
if(a[right] > a[left])
{
return right;
}
else
{
return left;
}
}
}
else
{
if(a[mid] > a[right])
{
return mid;
}
else
{
if(a[left] < a[right])
{
return left;
}
else
{
return right;
}
}
}
}
5. 归并排序
思路1：
归并逻辑：二叉树的遍历（深度优先：左右根）
- 将需要进行归并的区间范围视作结点，根结点的区间为整个数组
- 左右孩子结点为将区间范围一分为2，左孩子为前半区间，右孩子为后半区间
- 对每次得到的新区间都进行上述处理，直至区间中的元素数（<=2），即视为叶子结点。
- 按照后序遍历二叉树的顺序，对结点区间内的数据进行插入排序。
过程演示：
递归法：
void _mergesort(int* a, int* tmp, int left, int right)
{
//深度优先
if (left >= right)
{
return;
}
int mid = (right + left) / 2;
_mergesort(a, tmp, left, mid);
_mergesort(a, tmp, mid + 1, right);
//插入
int i = left;
int j = mid + 1;
int k = left;
while (i <= mid && j <= right)
{
//当存在相同的数时
if (a[i] <= a[j])
{
tmp[k++] = a[i++];
}
else
{
tmp[k++] = a[j++];
}
}
while (i <= mid)
{
tmp[k++] = a[i++];
}
while (j <= right)
{
tmp[k++] = a[j++];
}
memcpy(a + left, tmp + left, (right - left + 1) * sizeof(int));
}
void MergeSort(int* a, int n)
{
int* tmp = (int*)malloc(n * sizeof(int));
_mergesort(a, tmp, 0, n - 1);
free(tmp);
}
思路2：
- 将数组的元素分为两个两个一组，将每一组都使用插入排序调整为有序，遍历一遍数组
- 将一组中的元素数翻倍，重复步骤1，遍历完成再次翻倍，直至一组中的元素数包含整个数组，排序完成
- 当剩余元素不足一组时，将剩余元素也算作一组
非递归法：
void MergeSortNonR(int* a, int n)
{
int* c_a = (int*)malloc(n * sizeof(int));
int gap = 1;
while (gap < n)
{
//确定初始区间
int begin1 = 0;
int end1 = begin1 + gap - 1;
int begin2 = end1 + 1;
int end2 = begin2 + gap - 1;
//检测防止越界
if (end2 >= n)
{
end2 = n - 1;
}
while (begin1 < n)
{
//插入
int i = begin1;
int j = begin2;
int k = begin1;
while (i <= end1 && j <= end2)
{
if (a[i] <= a[j])
{
c_a[k++] = a[i++];
}
else
{
c_a[k++] = a[j++];
}
}
while (i <= end1)
{
c_a[k++] = a[i++];
}
while (j <= end2)
{
c_a[k++] = a[j++];
}
//拷贝回原数组
memcpy(a + begin1, c_a + begin1, (end2 - begin1 + 1) * sizeof(int));
//向后调整区间
begin1 = end2 + 1;
end1 = begin1 + gap - 1;
begin2 = end1 + 1;
end2 = begin2 + gap - 1;
//判断是否越界
if (end1 >= n)
{
end1 = n - 1;
}
if (end1 < n && end2 >= n)
{
end2 = n - 1;
}
}
gap *= 2;
}
free(c_a);
}
优化：
void MergeSortNonR(int* arr, int n)
{
int* tmp = (int*)malloc(n * sizeof(int));
//确定间距
int gap = 1;
while (gap < n)
{
//i中间记录
for (int i = 0; i < n; i += 2 * gap)
{
int begin1 = i;
int end1 = begin1 + gap - 1;
int begin2 = end1 + 1;
int end2 = begin2 + gap - 1;
//上一趟已经遍历过
if (end1 >= n)
{
break;
}
if (end2 >= n)
{
end2 = n - 1;
}
int index = begin1;
while (begin1 <= end1 && begin2 <= end2)
{
if (arr[begin1] <= arr[begin2])
{
tmp[index++] = arr[begin1++];
}
else
{
tmp[index++] = arr[begin2];
}
}
while (begin1 <= end1)
{
tmp[index++] = arr[begin1++];
}
while (begin2 <= end2)
{
tmp[index++] = arr[begin2++];
}
memcpy(arr + i, tmp + i, (end2 - i + 1) * sizeof(int));
}
gap *= 2;
}
}
6. 非比较排序：计数排序
- 根据数据的范围，创建一个合适大小的数组。
- 下标对应数据，根据数据中各个数字的出现次数在对应的下标处计数++。
- 限制：
<1> 数据范围不可跨度太大，会导致空间复杂度过高
<2>只能用来处理整形数据。
过程演示：
void CountSort(int* a, int n)
{
//选出最大值与最小值
int min = a[0];
int max = a[0];
for (int i = 0; i < n; i++)
{
if (a[i] < min)
{
min = a[i];
}
if (a[i] > max)
{
max = a[i];
}
}
//开辟空间
int size = max - min + 1;
int* count = (int*)malloc(size * sizeof(int));
memset(count, 0, n * sizeof(int));
//计数
for (int i = 0; i < n; i++)
{
count[a[i] - min]++;
}
//读数
int index = 0;
for (int i = 0; i < size; i++)
{
while (count[i])
{
a[index++] = i + min;
count[i]--;
}
}
}
7. 排序算法的稳定性
算法稳定性的判断标准：数据中相同数据在排序后，他们的相对位置是否变化。
- 直接插入排序（稳定，时间复杂度：O( n 2 n^2 n2)）
- 希尔排序（不稳定，时间复杂度略小于O( n 2 n^2 n2)）
- 选择排序（稳定，O( n 2 n^2 n2)）
- 堆排序（不稳定，O( n n n * logn)）
- 冒泡排序（稳定，O( n 2 n^2 n2)）
- 快速排序（不稳定，O( n n n * logn)）
- 归并排序（不稳定，O( n n n * logn)）
- 计数排序（稳定，O(n，Max)）
