我要评论--------------插入排序-------------
1、插入排序思想
插入排序的核心思想是逐步构建有序序列：
将数组分为 “已排序” 和 “未排序” 两部分，初始时已排序部分只包含第一个元素。
每次从未排序部分取出第一个元素，将其向前插入到已排序序列中的正确位置，使得插入后的序列依然保持有序。
重复这个过程，直到所有元素都被 插入到已排序序列中。
这个过程就像整理扑克牌：你会把每一张新摸到的牌，插入到手中已排好序的牌堆里，最终让整副牌都有序。
2、示例代码
// 插入排序（此处为降序，升序将 a[end] < tmp 改为 a[end] > tmp）
void insertsort(int* a, int n)
{
// 遍历未排序元素（从第2个元素开始）
for (int i = 1; i < n; i++)
{
int end = i - 1; // 已排序部分末尾下标
int tmp = a[i]; // 保存当前待插入元素
// 向前查找合适位置，大于tmp（降序）则后移
while (end >= 0)
{
if (a[end] < tmp)
{
a[end + 1] = a[end]; // 元素后移腾位置
end--;
}
else
{
break; // 找到位置，退出循环
}
}
a[end + 1] = tmp; // 插入到正确位置
}
}3、效率分析
时间复杂度：最坏情况下，插入第 1 个待排序元素时最多比较 1 次，第 2 个元素最多比较 2 次…… 第 n-1 个元素最多比较 n-1 次，总比较次数为等差数列求和，因此时间复杂度为o(n^2)；但在数组已有序的情况下，每个元素仅需比较 1 次，时间复杂度可优化至o(n)。
空间复杂度：仅定义了常数级的辅助变量，未额外开辟大规模空间，因此空间复杂度为o(1)。
稳定性：排序是稳定的。因为元素是逐个向前插入的，当遇到相等元素时不会移动，因此相等元素的相对位置在排序前后保持不变。
--------------希尔排序-------------
1、希尔排序思想
希尔排序的核心思想是分组插入排序，逐步缩小增量：
将整个待排序数组按照某个 增量（步长）分割成若干个子序列，每个子序列的元素在原数组中是等间隔的。对每个子序列分别进行插入排序，通过这种分组排序，让数组整体变得 “基本有序”。
然后，逐步缩小增量（通常取上一次的一半），重复上述分组和插入排序的操作。当增量缩小到 1 时，整个数组就变成了一个子序列，此时再进行一次插入排序，数组就完全有序了。
这个过程就像先把乱序的扑克牌按花色分组整理，再按点数细分整理，最后整体微调：
大增量时，元素移动的跨度大，能快速把乱序的数组变得 “大致有序”。
小增量时，数组已经基本有序，插入排序的效率会非常高。
2、示例代码
void shellsort(int* a, int n)
{
//gap > 1 预排序
//gap == 1 插入排序
int gap = n;
while (gap > 1)
{
gap = gap / 3 + 1;
/*----------------多组并排----------------*/
//for (int i = 0; i < n - gap; i++)
//{
// int end = i;
// int tmp = a[i + gap];
// while (end >= 0)
// {
// if (tmp < a[end])
// {
// a[end + gap] = a[end];
// end -= gap;
// }
// else
// {
// break;
// }
// }
// a[end + gap] = tmp;
//}
/*-------------一组排完排另一组-------------*/
for (int j = 0; j < gap; j++)
{
for (int i = 0; i < n - gap; i += gap)
{
int end = i;
int tmp = a[i + gap];
while (end >= 0)
{
if (tmp > a[end])
{
a[end + gap] = a[end];
end -= gap;
}
else
{
break;
}
}
a[end + gap] = tmp;
}
}
}
}
3、效率分析
时间复杂度：
1、外层：外层循环控制增量gap（公式不同如gap/2、gap/3+1会影响效率）从n逐步缩小至 1，迭代次数为对数级别，时间复杂度为 o(logn)
2、内层：刚开始gap很大，for循环大致在n这个量级（具体看图），while循环插入判断跳的很快，是常量级别的，所以最开始是时间复杂度为o(n)，最后gap很小，按理来说应该是n^2，但是由于数组已经无限接近有序，所以按最好的情况算o(n)
因此我们可以大概计算出来应该在n*logn这个量级
这是关于希尔排序时间复杂度不同教材的分析：
空间复杂度：仅定义了常量级的辅助变量，所以为o(1)
稳定性：由于是跳跃调整，相同值的元素可能在分组插入排序的过程中，被交换到彼此的原始相对位置之前，破坏了稳定性，所以希尔排序是不稳定排序。
--------------选择排序-------------
1、选择排序思想
选择排序的核心思想是逐步选择最值，构建有序序列：
将数组分为 “已排序” 和 “未排序” 两部分，初始时已排序部分为空。每次从未排序部分中选出最小（或最大）的元素，将其与未排序部分的第一个元素交换位置，该元素就加入到已排序部分的末尾。
重复这个过程，直到所有元素都被纳入已排序部分，整个数组就完全有序了。
这个过程就像从一堆打乱的扑克牌里，每次挑出最小的一张，放到已整理好的牌堆后面，最终完成整副牌的排序。
2、示例代码
void selectsort(int* a, int n)
{
/*
int left = 0;
while (left < n)
{
int min = left;
for (int i = left + 1; i < n; i++)
{
if (a[min] > a[i])
{
min = i;
}
}
swap(&a[min],&a[left]);
left++;
}
*/
int left = 0;
int right = n - 1;
//left == right就表示只有一个元素了，所以没有选择的必要了
while (left < right)
{
//必须要初始为left，因为是内层循环从left+1开始比较的
//如果有一个初始不为left，就会跳过left这个值
int max = left;
int min = left;
for (int i = left + 1; i <= right; i++)
{
if (a[max] < a[i])
{
max = i;
}
if (a[min] > a[i])
{
min = i;
}
}
swap(&a[left],&a[min]);
//修正:max有可能和left重叠
if (left == max)
{
max = min;
}
swap(&a[right],&a[max]);
left++;
right--;
}
}
修正：
3、效率分析
时间复杂度：第一趟遍历 n-1 遍数组，第二趟遍历 n-2 遍数组，第 n-1 遍遍历1遍数组，是个等差数列，所以时间复杂度为o(n^2)
空间复杂度：仅使用常量级别的变量，因此空间复杂度是o(1)
稳定性：由于交换操作可能会破坏相同值元素的相对顺序，所以选择排序是不稳定排序
---------------堆排序--------------
1、堆排序思想
堆排序的核心思想是利用堆的特性进行排序：
将待排序数组构建成一个大顶堆（或小顶堆），堆顶即为当前未排序部分的最大值（或最小值）。每次将堆顶元素与当前未排序部分的末尾元素交换，使该最大值（或最小值）归位到正确的排序位置。交换后，堆的结构会被破坏，需要对剩余的未排序元素重新调整为大顶堆（或小顶堆）。重复这个过程，直到整个数组有序。
这个过程就像从一堆石头里每次挑出最重的一块，放到已排好的序列末尾，最终让所有石头按重量从大到小排好。
2、示例代码
//向上调整算法 - 建大堆
void adjustup(int* a, int child)
{
int parent = (child - 1) / 2;
while (child > 0)
{
if (a[child] > a[parent])
{
swap(&a[child], &a[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
//向下调整算法
void adjustdown(int* a, int n, int parent)
{
int child = 2 * parent + 1;
while (child < n)//等于n时越界一个位置
{
if (child + 1 < n && a[child + 1] > a[child])
{
child++;
}
if (a[child] > a[parent])
{
swap(&a[child], &a[parent]);
parent = child;
child = 2 * parent + 1;
}
else
{
break;
}
}
}
//堆排序
//n*logn
void heapsort(int* a, int n)
{
//向下调整建堆 -- n
for (int i = (n - 2) / 2; i >= 0; i--)
{
adjustdown(a,n,i);
}
//向上调整建堆 -- n*logn
//for (int i = 1; i < n; i++)
//{
// adjustup(a, i);
//}
//排序
int end = n - 1;
while (end > 0)
{
swap(&a[0], &a[end]);
adjustdown(a, end, 0);
end--;
}
}
3、效率分析
时间复杂度：
向下调整建堆的时间复杂度为o(n)：向下调整建堆的时间复杂度是 o(n)，而不是 o(nlogn)，核心原因是调整成本被平摊了。堆的底层节点数量最多，占了总节点数的一半左右，但它们的调整深度最小；而堆的上层节点数量很少，调整深度才会达到 o(logn)。这种 “数量多的节点成本低，数量少的节点成本高” 的反向分布，把整体的平均调整成本从 o(logn) 拉低到了 o(1)，最终时间复杂度就成了 o(n)。
向上调整建堆的时间复杂度为o(nlogn)，它的调整逻辑与向下调整正好相反：上层节点的调整深度较浅，但下层节点的调整深度很深，而堆的下层恰恰包含了大部分元素。因此，整体来看，大部分节点都需要进行约 logn 次调整，最终时间复杂度为 o(nlogn)。
堆排序的完整过程分为建堆和排序阶段两部分：
建堆阶段：使用向下调整建堆，时间复杂度为 o(n)
排序阶段：共需进行 n−1 次堆顶交换与向下调整，每次调整的时间复杂度为 o(logn)，因此这一阶段的时间复杂度为 o(nlogn)
将两部分时间复杂度相加，取主导项，堆排序的整体时间复杂度为 o(nlogn)，且该复杂度不受输入数据分布的影响，最优、最坏与平均时间复杂度均为 o(nlogn)。
空间复杂度：仅仅使用了常数级别的变量，所以空间复杂度为o(1)
稳定性：堆排序是不稳定的排序算法。因为在堆的调整过程中（无论是向上还是向下调整），相同值的节点可能会因为交换而改变相对顺序，破坏了原有的稳定性。
--------------冒泡排序-------------
1、冒泡排序思想
冒泡排序的核心思想是通过相邻元素的比较与交换，让较大（较小）的元素逐步 “冒泡” 到数组的末尾。
将数组视为一个未排序的整体，从头部开始，依次比较相邻的两个元素。
如果前一个元素大于（小于）后一个元素，就交换它们的位置，使较大（较小）的元素向后移动一位。
每一轮遍历后，当前未排序部分的最大值（最小值）会被 “推” 到末尾，成为已排序部分。
重复这个过程，直到所有元素都完成排序。
这个过程就像水里的气泡一样，较大（较小）的元素会慢慢浮到水面（数组末尾）。
2、示例代码
void bubblesort(int* a, int n)
{
//多少趟
for (int i = 0;i < n - 1;i++)
{
//单趟
int flag = 0;
for (int j = 1; j < n - i; j++)
{
if (a[j - 1] > a[j])
{
swap(&a[j - 1], &a[j]);
flag = 1;
}
}
if (flag == 0)
{
break;
}
}
}3、效率分析
时间复杂度：冒泡排序共进行 n−1 轮遍历，总比较次数为等差数列求和 2n(n−1)，时间复杂度为 o(n^2)；若加入提前终止优化，最优情况可降至 o(n)。
空间复杂度：冒泡排序仅需常数级别的临时变量用于元素交换，因此空间复杂度为 o(1)。
稳定性：冒泡排序是稳定的排序算法，因为它仅在相邻元素前大于后时才交换，相同值的元素不会改变相对顺序。
上述五大排序性能对比：
希尔排序和堆排序时间复杂度都是n*logn这个量级，是这几个中效率最高的两个了
（（希尔排序的时间复杂度）这是一个简化说法，严格来说它介于 o(nlogn) 和 o(n2) 之间，取决于增量序列的选择，但常归为 o(nlogn) 量级）
接下来就是插入排序和冒泡排序，它俩在数组有序时，时间复杂度都能达到 o (n)，最坏都是 o(n^2) 这个量级，但是他们在一些场景下的性能还是有差距的：
有序：一样
接近有序：有一些差距
部分有序：差距就很大
这是由于这两个算法的单次操作导致的：
最后一个就是选择排序，无论是否有序时间复杂度都是在o(n^2)这个量级，也是这几个中效率最差的排序算法
稳定性补充：冒泡、插入排序是稳定的；希尔、堆、选择排序是不稳定的。
总结
到此这篇关于c语言五大经典排序算法插入、希尔、冒泡、选择、堆排序的文章就介绍到这了,更多相关c语言算法插入、希尔、冒泡、选择、堆排序内容请搜索代码网以前的文章或继续浏览下面的相关文章希望大家以后多多支持代码网！
发表评论