end 初始指向已排序部分的最后一个下标，end+1 初始为待排序数据。我们将 end+1 的数据暂存到 tmp 变量中。
tmp 与 end 位置的数据比较，若 end 比 tmp 大，则将 end 的数据放到 end+1 位置上，并让 end--，在已排好序的数组中寻找合适位置；反之则将 tmp 数据放到 end+1 的位置。
// 直接插入排序voidInsertSort(int* arr, int num) {
for (int i = 0; i < num - 1; i++) {
int end = i;
int tmp = arr[end + 1];
while (end >= 0) {
if (arr[end] > tmp)
arr[end + 1] = arr[end];
elsebreak;
end--;
}
arr[end + 1] = tmp;
}
}
1.2 希尔排序
该算法属于插入排序的优化版本。
优化思路
首先明确，直接插入排序为何时间复杂度较高？
最坏情况下，若数组倒序，每次插入都需要调整到已排序部分的最前面。若能减少调整次数，效率将提升。
算法尝试
若先将数组调整为只需少量调整的预排序状态，可解决逐个查找的问题。通过设置间隔变量 gap（如 num/3+1）进行大步长调整，之后逐渐减小 gap，直至 gap 为 1 时执行完整插入排序。
代码实现
基于插入排序修改：
for (int i = 0; i < num - gap; i++) {
int end = i;
int tmp = arr[end + gap];
while (end >= 0) {
if (arr[end] > tmp)
arr[end + gap] = arr[end];
elsebreak;
end -= gap;
}
arr[end + gap] = tmp;
}
外层循环控制 gap 变化：
voidShellSort(int* arr, int num) {
int gap = num;
while (gap > 1) {
gap = gap / 3 + 1;
for (int i = 0; i < num - gap; i++) {
int end = i;
int tmp = arr[end + gap];
while (end >= 0) {
if (arr[end] > tmp)
arr[end + gap] = arr[end];
elsebreak;
end -= gap;
}
arr[end + gap] = tmp;
}
}
}
先给 gap 赋值为数组长度，确保循环内部修改后 gap 为 1 时能执行一次。
2. 选择排序算法
2.1 直接选择排序
代码思路
遍历数组查找最小值，与已排序末尾交换。
遍历效率较低，能否一次循环找最大和最小两个值？
算法尝试
使用 begin 和 end 分别指向待排序数组的头尾，将找到的最小值和最大值与 begin 和 end 交换。中间为未排序部分，两边为已排序部分。用 maxi 和 mini 记录最大和最小值的下标。
代码实现
内层逻辑：
int mini = begin;
int maxi = end;
for (int i = begin; i <= end; i++) {
if (arr[i] > arr[maxi]) maxi = i;
if (arr[i] < arr[mini]) mini = i;
}
if (maxi == begin) maxi = mini;
Swap(&arr[begin], &arr[mini]);
Swap(&arr[end], &arr[maxi]);
begin++;
end--;
增加判断是为了避免当 maxi 位于 begin 位置时，第一次交换导致数据错位的问题。
完整函数：
voidSelectSort(int* arr, int num) {
int begin = 0;
int end = num - 1;
while (begin < end) {
int mini = begin;
int maxi = end;
for (int i = begin; i <= end; i++) {
if (arr[i] > arr[maxi]) maxi = i;
if (arr[i] < arr[mini]) mini = i;
}
if (maxi == begin) maxi = mini;
Swap(&arr[begin], &arr[mini]);
Swap(&arr[end], &arr[maxi]);
begin++;
end--;
}
}
// 堆排序voidHeapSort(int* arr, int num) {
// 建堆for (int i = (num - 2) / 2; i >= 0; i--) {
AdjustDown(arr, i, num);
}
// 堆排序for (int i = num - 1; i > 0; i--) {
Swap(&arr[0], &arr[i]);
AdjustDown(arr, 0, i);
}
}
3. 交换排序
3.1 冒泡排序
代码思路
相邻元素比较，大的往后放，每轮确定一个最大值。
代码实现
// 冒泡排序voidBubbleSort(int* arr, int num) {
for (int i = 0; i < num - 1; i++) {
for (int j = 0; j < num - i - 1; j++) {
if (arr[j] > arr[j + 1])
Swap(&arr[j], &arr[j + 1]);
}
}
}
3.2 快速排序
代码思路
选取基准值 key，小于 key 的放左边，大于 key 的放右边。
Hoare 版本快排
left 从右往左找小于 key 的值，right 从左往右找大于 key 的值，交换后继续，直到 right < left。
// Hoare 版本int _QuickSort(int* arr, int left, int right) {
int keyi = left;
left++;
while (left <= right) {
while (arr[right] >= arr[keyi] && left < right)
right--;
while (arr[left] <= arr[keyi] && left < right)
left++;
if (left <= right)
Swap(&arr[left++], &arr[right--]);
}
Swap(&arr[keyi], &arr[right]);
return right;
}
递归代码：
// 快速排序voidQuickSort(int* arr, int left, int right) {
if (left >= right)
return;
int keyi = _QuickSort(arr, left, right);
QuickSort(arr, left, keyi - 1);
QuickSort(arr, keyi + 1, right);
}
挖坑法
第一个数据放入坑中，left 位置产生坑，right 先走找小于 key 的值填入左边坑，随后 left 走找大于 key 的值填入右边坑，循环至 right < left，最后填入 key。
// 挖坑法int _QuickSort_hole(int* arr, int left, int right) {
int hole = left;
int key = arr[hole];
while (left < right) {
while (arr[right] >= key && left < right)
right--;
arr[hole] = arr[right];
hole = right;
while (arr[left] <= key && left < right)
left++;
arr[hole] = arr[left];
hole = left;
}
arr[hole] = key;
return hole;
}
// Lomuto 前后指针int _QuickSort_lomuto(int* arr, int left, int right) {
int keyi = left;
int prev = left;
int cur = left + 1;
while (cur <= right) {
if (arr[cur] < arr[keyi] && ++prev != cur)
Swap(&arr[prev], &arr[cur]);
cur++;
}
Swap(&arr[keyi], &arr[prev]);
return prev;
}
快排的非递归实现方法
借助栈代替递归，保存左右边界参数。
// 非递归版本快速排序——借助栈voidQuickSortNoR(int* arr, int left, int right) {
ST st;
StackInit(&st);
StackPush(&st, left);
StackPush(&st, right);
while (!STEmpty(&st)) {
int end = StackTop(&st);
StackPop(&st);
int start = StackTop(&st);
StackPop(&st);
int keyi = _QuickSort_lomuto(arr, start, end);
if (start < keyi - 1) {
StackPush(&st, start);
StackPush(&st, keyi - 1);
}
if (end > keyi + 1) {
StackPush(&st, keyi + 1);
StackPush(&st, end);
}
}
StackDestory(&st);
}
4. 归并排序
代码思想
递归将数组拆分至单个数据，回档时合并有序序列。
算法实现
void _MergeSort(int* arr, int left, int right, int* tmp) {
if (left >= right)
return;
int mid = (left + right) / 2;
_MergeSort(arr, left, mid, tmp);
_MergeSort(arr, mid + 1, right, tmp);
// 合并两个有序的序列int begin1 = left, end1 = mid;
int begin2 = mid + 1, end2 = right;
int i = begin1;
while (begin1 <= end1 && begin2 <= end2) {
if (arr[begin1] < arr[begin2])
tmp[i++] = arr[begin1++];
else
tmp[i++] = arr[begin2++];
}
while (begin1 <= end1)
tmp[i++] = arr[begin1++];
while (begin2 <= end2)
tmp[i++] = arr[begin2++];
memmove(arr + left, tmp + left, (right - left + 1) * sizeof(int));
}
// 归并排序voidMergeSort(int* arr, int num) {
int* tmp = (int*)malloc(num * sizeof(int));
if (tmp == NULL) {
perror("MergeSort::malloc");
exit(1);
}
_MergeSort(arr, 0, num - 1, tmp);
free(tmp);
}
5. 非比较排序
5.1 计数排序
算法思想
通过数组记录每个数据的个数，再根据计数表还原数据。
算法实现
// 计数排序voidCountSort(int* arr, int num) {
int min = arr[0];
int max = arr[0];
// 获取当前数据的偏移量for (int i = 0; i < num; i++) {
if (arr[i] < min)
min = arr[i];
if (arr[i] > max)
max = arr[i];
}
int range = max - min + 1;
int* count = (int*)calloc(range, sizeof(int));
if (count == NULL) {
perror("CountSort::malloc");
exit(1);
}
// 将数据放到计数表中for (int i = 0; i < num; i++) {
count[arr[i] - min]++;
}
// 将数据放到原数组当中int index = 0;
for (int i = 0; i < range; i++) {
while (count[i]--)
arr[index++] = i + min;
}
free(count);
}
