系列文章目录
🎈 🎈 我的CSDN主页:OTWOL的主页，欢迎！！！👋🏼👋🏼
🎉🎉我的C语言初阶合集：C语言初阶合集，希望能帮到你！！！😍 😍
🔍🔍我的C语言进阶合集：我的C语言进阶合集，期待你的点击！！！🌈🌈
🎉🎉我的数据结构与算法合集：数据结构与算法合集，点进去看看吧！！！ 🎊🎊
😍 👋🏼🎉🎊创作不易，欢迎大家留言、点赞加收藏！！！ 🥳😁😍
文章目录
- 系列文章目录
- 一、直接插入排序
- （1）定义
- （2）基本步骤
- （3）动图展示
- （4）代码示例
- 二、希尔排序
- （1）定义
- （2）基本步骤
- （3）代码示例
- 三、选择排序
- （1）定义
- （2）基本步骤
- （3）动图展示
- （4）代码示例
- 四、堆排序
- （1）定义
- （2）基本步骤
- （3）动图展示
- （4）代码示例
- 五、冒泡排序
- （1）定义
- （2）基本步骤
- （3）动图展示
- （4）代码示例
- 六、快速排序
- （1）定义
- （2）基本步骤
- （3）动图展示
- （4）代码示例
- Hoare版本
- 动图展示
- 代码示例
- 挖坑法版本
- 动图展示
- 代码示例
- 双指针法版本
- 动图展示
- 代码示例
- 七、归并排序
- （1）定义
- （2）基本步骤
- （3）动图展示
- （4）代码示例
- 八、计数排序
- （1）定义
- （2）基本步骤
- （3）动图展示
- （4）代码示例
- END
一、直接插入排序
（1）定义
将未排序的数据，在已排序序列中从后向前扫描，找到相应位置并插入。
（2）基本步骤
1. 从第2个元素开始遍历数组
2. 取出当前元素：
将当前元素（未排序部分的第一个元素）暂存到变量tmp中。
3. 在已排序部分找插入位置：
从已排序部分的最后一个元素（索引为i）开始，向前遍历。
如果tmp小于当前元素，则将当前元素向后移动一位，继续向前比较。
如果tmp大于等于当前元素，说明找到插入位置，退出循环。
4. 插入元素：
将tmp插入到找到的合适位置。
5. 重复上述过程，直到所有元素都被插入到已排序部分。
（3）动图展示
（4）代码示例
void InsertSort(int* a, int n)
{
// 遍历数组，从第1个元素开始（索引为0），到倒数第二个元素（索引为n-2）
for (int i = 0; i < n - 1; ++i)
{
// 定义当前已排序部分的最后一个元素的索引
int end = i;
// 将待插入的元素（当前未排序部分的第一个元素）暂存到变量tmp中
int tmp = a[end + 1];
// 从已排序部分的最后一个元素开始向前遍历
while (end >= 0)
{
// 如果暂存的元素tmp小于当前已排序部分的元素a[end]
if (tmp < a[end])
{
// 将a[end]向后移动一位，为tmp腾出空间
a[end + 1] = a[end];
--end; // 继续向前比较
}
// 如果tmp大于等于a[end]，说明找到了合适的插入位置，退出循环
else
{
break;
}
}
// 将暂存的元素tmp插入到合适的位置
a[end + 1] = tmp;
}
}
二、希尔排序
（1）定义
希尔排序是直接插入排序的改进版本，
通过分组的方式减少元素之间的比较次数，每组进行插入排序，随着分组的间隔逐渐减小，最终达到整体有序。
（2）基本步骤
1. 分组排序：
首先选定一个增量（gap），将待排序的元素分为多个子序列，每个子序列的元素间隔为gap。对每个子序列进行插入排序。
2. 逐步减小增量：
逐渐减小增量（gap），重复上述分组和插入排序的过程，直到增量减至1。
3. 最终排序：
当增量为1时，对整个序列进行一次插入排序，此时序列已经接近有序，因此效率较高。
（3）代码示例
void ShellSort(int* a, int n)
{
int gap = n; // 初始化步长（gap），初始值为数组长度
// 当步长大于1时，继续进行分组和排序
while (gap > 1)
{
gap /= 2; // 每次将步长减半，逐步缩小分组间隔
// 遍历数组，对每个分组进行插入排序
for (int i = 0; i < n - gap; ++i)
{
int end = i; // 当前分组的起始位置
int tmp = a[end + gap]; // 暂存当前需要插入的元素
// 在当前分组内进行插入排序
while (end >= 0)
{
// 如果当前元素小于分组内的前一个元素，则将前一个元素向后移动
if (tmp < a[end])
{
a[end + gap] = a[end]; // 将a[end]向后移动到a[end + gap]
end -= gap; // 更新索引，继续向前比较
}
else
{
break; // 如果当前元素大于等于前一个元素，说明找到合适位置，退出循环
}
}
// 将暂存的元素插入到合适的位置
a[end + gap] = tmp;
}
}
}
三、选择排序
（1）定义
通过不断地从待排序的数据集合中选择出最小（或最大）的元素，并将其放置在已排序序列的合适位置，逐步构建出一个有序序列。
（2）基本步骤
1. 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
2. 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
3. 重复第二步，直到所有元素均排序完毕。
（3）动图展示
（4）代码示例
注意：
这个代码示例是每次在未排序序列中找到最小和最大元素的两个元素。
交换两个整型变量
void Swap(int* p1, int* p2)
{
int tmp = *p1; // 使用临时变量tmp保存p1指向的值
*p1 = *p2; // 将p2指向的值赋给p1指向的位置
*p2 = tmp; // 将临时变量tmp的值赋给p2指向的位置
}
选择排序
void SelectSort(int* a, int n)
{
int left = 0; // 左边界，初始值为数组的起始位置
int right = n - 1; // 右边界，初始值为数组的结束位置
// 当左边界小于右边界时，继续排序
while (left < right)
{
int maxi = right; // 假设最大值在右边界
int mini = left; // 假设最小值在左边界
// 遍历当前未排序部分的数组，寻找最小值和最大值的索引
for (int i = left; i <= right; ++i)
{
// 如果找到更小的值，更新最小值的索引
if (a[i] < a[mini])
mini = i;
// 如果找到更大的值，更新最大值的索引
if (a[i] > a[maxi])
maxi = i;
}
// 将找到的最小值与左边界交换
Swap(&a[left], &a[mini]);
// 如果最大值的索引刚好是左边界（被交换走了），更新最大值的索引为最小值的索引
if (maxi == left)
maxi = mini;
// 将找到的最大值与右边界交换
Swap(&a[right], &a[maxi]);
// 缩小未排序部分的范围
--right;
++left;
}
}
四、堆排序
（1）定义
指利用堆这种数据结构所设计的一种排序算法。
堆是一个近似完全二叉树的结构，
并同时满足堆的性质：
即子结点的键值或索引总是小于等于（或者大于等于）它的父节点。
（2）基本步骤
堆排序分为两个阶段：
1. 建堆：
从最后一个非叶子节点开始向上调整，使得整个数组满足大根堆性质。
2. 排序：
通过不断将堆顶（最大值）与堆的最后一个元素交换，并缩小堆的范围，逐步将数组排序。
（3）动图展示
（4）代码示例
交换两个整型变量
void Swap(int* p1, int* p2)
{
int tmp = *p1; // 使用临时变量tmp保存p1指向的值
*p1 = *p2; // 将p2指向的值赋给p1指向的位置
*p2 = tmp; // 将临时变量tmp的值赋给p2指向的位置
}
大根堆的向下调整算法
void AdjustDown(int* a, int n, int parent)
{
int child = parent * 2 + 1; // 计算当前父节点的左孩子的索引
while (child < n) // 当孩子节点索引在数组范围内时，继续调整
{
// 如果右孩子存在且右孩子比左孩子大
if (child + 1 < n && a[child + 1] > a[child])
++child; // 将child指向较大的右孩子
// 如果孩子节点大于父节点
if (a[child] > a[parent])
{
Swap(&a[child], &a[parent]); // 交换父节点和孩子节点的值
parent = child; // 更新父节点为当前孩子节点
child = parent * 2 + 1; // 更新孩子节点的索引
}
else
break; // 如果父节点已经大于孩子节点，调整结束
}
}
堆排序
void HeapSort(int* a, int n)
{
// 排序升序 -- 建大堆
for (int i = (n - 1 - 1) / 2; i >= 0; --i) // 从最后一个非叶子节点开始向上调整
AdjustDown(a, n, i); // 调整每个非叶子节点，使其满足大顶堆性质
// 排序过程
int end = n - 1; // 初始化堆的最后一个元素的索引
while (end > 0) // 当堆中还有多个元素时
{
Swap(&a[0], &a[end]); // 将堆顶（最大值）与堆的最后一个元素交换
AdjustDown(a, end, 0); // 重新调整堆顶元素，使其满足大顶堆性质，此时 end 表示数组中未排序好的元素个数
--end; // 缩小堆的范围，排除已经排序好的最后一个元素
}
}
五、冒泡排序
（1）定义
通过多次遍历待排序的数列，比较相邻元素的值，并在必要时交换它们的位置，从而将较大的元素逐步“冒泡”到数列的末尾。
这个过程会重复进行，直到整个数列有序为止。
（2）基本步骤
1. 一趟一趟地比较：
我们需要比较很多次，每次比较都会让一个数字“冒泡”到它该在的位置。总共要比较 n-1 次（n 是数字的个数）。
2. 比较相邻的数字：
每次比较两个挨着的数字，如果前面的数字比后面的数字大，就交换它们的位置。这样，大的数字就会慢慢往后移，就像气泡往上浮一样。
3. 减少比较范围：
每完成一次比较，数组的最后面就会多一个排好序的数字，所以下次比较的时候，就不用再看最后那个已经排好的数字了。
4. 提前结束：
如果在某次比较中，所有数字都没有交换位置，说明它们已经排好序了，就可以提前结束，不用再比较了。
（3）动图展示
（4）代码示例
交换两个整型变量
void Swap(int* p1, int* p2)
{
int tmp = *p1; // 使用临时变量tmp保存p1指向的值
*p1 = *p2; // 将p2指向的值赋给p1指向的位置
*p2 = tmp; // 将临时变量tmp的值赋给p2指向的位置
}
冒泡排序
void BubbleSort(int* a, int n)
{
// 外层循环控制排序的趟数，一共进行 n-1 趟
// 因为是两两相邻元素进行比较，例如：3个数字进行排序，一共需要两趟
for (int i = 1; i < n; ++i) // i 表示第 i 趟排序
{
bool exchange = false; // 用于标记这一趟是否发生了交换操作
// 内层循环控制每一趟的比较过程
// 每一趟的比较次数逐渐减少，因为最后的元素已经排好序
for (int j = 1; j <= n - i; ++j) // j 表示当前比较的元素索引
{
// 比较相邻的两个元素 a[j-1] 和 a[j]
if (a[j - 1] > a[j])
{
exchange = true; // 发生了交换，标记为 true
Swap(&a[j - 1], &a[j]); // 交换两个元素的位置
}
}
// 如果在一趟中没有发生任何交换，说明数组已经有序，可以直接结束排序
if (exchange == false)
break;
}
}
六、快速排序
（1）定义
是一种高效的排序算法，采用分治的思想进行排序。
其基本思想是通过一趟排序将要排序的数据分割成独立的两部分，
其中一部分的所有数据都比另一部分的数据小，
然后分别对这两部分数据继续进行快速排序，
整个排序过程可以递归进行，以此达到整个数据变成有序序列。
（2）基本步骤
1. 选择基准元素：
从待排序的数组中选择一个元素的下标作为基准元素的下标（keyi）。
2. 分区操作：
将数组中小于基准元素的元素移到基准元素的左边，将大于基准元素的元素移到右边。这个过程称为分区。
3. 递归排序：
递归地对基准元素左边的子数组和右边的子数组进行快速排序。
（3）动图展示
（4）代码示例
Hoare版本
动图展示
代码示例
交换两个整型变量
void Swap(int* p1, int* p2)
{
int tmp = *p1; // 使用临时变量tmp保存p1指向的值
*p1 = *p2; // 将p2指向的值赋给p1指向的位置
*p2 = tmp; // 将临时变量tmp的值赋给p2指向的位置
}
快速排序
void QuickSort(int* a, int left, int right)
{
// 如果左边界大于等于右边界，说明子数组只有一个或没有元素，无需排序
if (left >= right)
return;
int begin = left; // 记录子数组的起始位置
int end = right; // 记录子数组的结束位置
int keyi = left; // 选择子数组的第一个元素作为基准值
// 开始分区操作，将数组分为小于基准值和大于基准值的两部分
while (left < right) // 当左指针小于右指针时，继续循环
{
// 从右向左找小于基准值的元素
while (left < right && a[right] >= a[keyi])
--right;
// 从左向右找大于基准值的元素
while (left < right && a[left] <= a[keyi])
++left;
// 如果找到满足条件的元素，交换它们的位置
Swap(&a[left], &a[right]);
}
// 当 left == right 时，将基准值放到中间位置
Swap(&a[left], &a[keyi]);
keyi = left; // 更新基准值的位置
// 递归对基准值左边和右边的子数组进行快速排序
// 排序基准值左边的子数组 [begin, keyi - 1]
QuickSort(a, begin, keyi - 1);
// 排序基准值右边的子数组 [keyi + 1, end]
QuickSort(a, keyi + 1, end);
}
挖坑法版本
动图展示
代码示例
void QuickSort(int* a, int left, int right)
{
// 如果左边界大于等于右边界，说明子数组只有一个或没有元素，无需排序
if (left >= right)
return;
int begin = left; // 记录子数组的起始位置
int end = right; // 记录子数组的结束位置
int hole = left; // 挖坑的位置，初始为子数组的第一个元素
int key = a[hole]; // 基准值，即挖出的元素
// 开始分区操作，将数组分为小于基准值和大于基准值的两部分
while (left < right) // 当左指针小于右指针时，继续循环
{
// 从右向左找小于基准值的元素
while (left < right && a[right] >= key)
--right;
// 将找到的元素填入坑中
a[hole] = a[right];
hole = right; // 更新坑的位置为当前填入的位置
// 从左向右找大于基准值的元素
while (left < right && a[left] <= key)
++left;
// 将找到的元素填入坑中
a[hole] = a[left];
hole = left; // 更新坑的位置为当前填入的位置
}
// 当 left == right 时，将基准值放回坑中
a[hole] = key;
// 递归对基准值左边和右边的子数组进行快速排序
// 排序基准值左边的子数组 [begin, hole - 1]
QuickSort(a, begin, hole - 1);
// 排序基准值右边的子数组 [hole + 1, end]
QuickSort(a, hole + 1, end);
}
双指针法版本
动图展示
代码示例
void QuickSort(int* a, int left, int right)
{
// 如果左边界大于等于右边界，说明子数组只有一个或没有元素，无需排序
if (left >= right)
return;
int keyi = left; // 基准值的索引，选择子数组的第一个元素作为基准值
int prev = left; // prev 指向小于等于基准值的最后一个元素的位置
int cur = left + 1; // cur 是当前正在比较的元素的索引
// 遍历子数组，将小于等于基准值的元素移动到基准值的左侧
while (cur <= right)
{
if (a[cur] <= a[keyi]) // 如果当前元素小于等于基准值
{
++prev; // 扩展 prev 的范围
Swap(&a[prev], &a[cur]); // 将当前元素与 prev 位置的元素交换
}
++cur; // 移动到下一个元素
}
// 将基准值放到正确的位置（prev 位置）
Swap(&a[prev], &a[keyi]);
// 递归对基准值左边和右边的子数组进行快速排序
QuickSort(a, left, prev - 1); // 排序基准值左边的子数组 [left, prev - 1]
QuickSort(a, prev + 1, right); // 排序基准值右边的子数组 [prev + 1, right]
}
七、归并排序
（1）定义
归并排序的基本思想是将一个未排序的数组递归地分成两个子数组，对每个子数组进行排序，然后将它们合并成一个有序数组。
（2）基本步骤
1. 分解：
将待排序的数组或列表递归地分成两个子序列，直到每个子序列只有一个元素。这个过程通过不断地将序列一分为二，直到无法再分解为止。
2. 合并：
将两个有序的子序列合并成一个有序序列。通过比较两个子序列的元素大小，将较小的元素放入结果序列，并从该子序列中移除该元素。重复这个过程，直到所有子序列都被合并成一个有序序列。
3. 递归：
递归地应用上述两个步骤，直到所有子序列都被合并成一个有序序列为止。
（3）动图展示
（4）代码示例
// 辅助函数，用于实现归并排序的核心逻辑
void _MergeSort(int* a, int begin, int end, int* tmp)
{
// 如果子数组只有一个或没有元素，无需排序，直接返回
if (begin >= end)
return;
// 计算子数组的中间位置，用于将数组分成两部分
int mid = (begin + end) / 2;
// 递归地对左半部分 [begin, mid] 进行归并排序
_MergeSort(a, begin, mid, tmp);
// 递归地对右半部分 [mid+1, end] 进行归并排序
_MergeSort(a, mid + 1, end, tmp);
// 初始化左右两部分的起始和结束位置
int begin1 = begin; // 左半部分的起始位置
int begin2 = mid + 1; // 右半部分的起始位置
int end1 = mid; // 左半部分的结束位置
int end2 = end; // 右半部分的结束位置
// 初始化临时数组的索引
int j = begin;
// 合并左右两部分
// 比较左右两部分的元素，将较小的元素放入临时数组 tmp 中
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] < a[begin2]) // 如果左半部分的当前元素较小
tmp[j++] = a[begin1++]; // 将左半部分的元素放入 tmp，并移动指针
else
tmp[j++] = a[begin2++]; // 否则将右半部分的元素放入 tmp，并移动指针
}
// 如果左半部分还有剩余元素，直接将它们复制到临时数组中
while (begin1 <= end1)
tmp[j++] = a[begin1++];
// 如果右半部分还有剩余元素，直接将它们复制到临时数组中
while (begin2 <= end2)
tmp[j++] = a[begin2++];
// 将临时数组中的排序结果复制回原数组 a
memcpy(a + begin, tmp + begin, (end - begin + 1) * sizeof(int));
}
// 主函数，用于初始化临时数组并调用辅助函数
void MergeSort(int* a, int n)
{
// 分配一个临时数组，用于存储归并过程中的中间结果
int* tmp = (int*)calloc(n, sizeof(int));
if (tmp == NULL)
{
perror("calloc fail\n"); // 如果分配失败，打印错误信息并返回
return;
}
// 调用辅助函数进行归并排序
_MergeSort(a, 0, n - 1, tmp);
// 释放临时数组
free(tmp);
}
八、计数排序
（1）定义
通过统计每个数字出现的次数来实现排序，然后按顺序重新排列。
（2）基本步骤
1. 计算边界
遍历数组，找到数组中的最大值 max 和最小值 min。
这一步是为了确定计数数组的大小。
2. 计算范围
计算范围 range = max - min + 1。
这个范围决定了计数数组的大小。
3. 创建计数数组
使用 calloc 分配一个大小为 range 的计数数组 CountA，并初始化为 0。
计数数组用于统计每个数字出现的次数。
4. 计数
遍历原数组，将每个数字映射到计数数组中，并增加对应的计数。
映射方式：CountA[a[i] - min]++。
5. 排序
遍历计数数组，根据计数结果将数字按顺序放回原数组。
如果某个数字出现了多次，则通过循环将其全部放回原数组。
6. 释放内存
释放计数数组 CountA，避免内存泄漏。
（3）动图展示
（4）代码示例
void CountSort(int* a, int n)
{
// 1. 计算数组的最大值和最小值，确定范围
int max = a[0];
int min = a[0];
for (int i = 1; i < n; ++i)
{
if (a[i] < min)
min = a[i]; // 更新最小值
if (a[i] > max)
max = a[i]; // 更新最大值
}
// 2. 计算范围（最大值 - 最小值 + 1）
int range = max - min + 1;
// 3. 创建计数数组，用于统计每个数字出现的次数
int* CountA = (int*)calloc(range, sizeof(int));
if (CountA == NULL)
{
perror("calloc fail\n");
return;
}
// 4. 遍历原数组，统计每个数字出现的次数
for (int i = 0; i < n; ++i)
CountA[a[i] - min]++; // 将数字映射到计数数组中
// 5. 根据统计结果重新填充原数组
int j = 0;
for (int i = 0; i < range; ++i)
{
while (CountA[i]--)
a[j++] = i + min; // 将数字按顺序放回原数组
}
// 6. 释放计数数组
free(CountA);
}
END
每天都在学习的路上！
On The Way Of Learning
![[Spring] Gateway详解](https://i-blog.csdnimg.cn/direct/623da991737f49c2a252e5cb5bac96df.png)
