✨个人主页： Yohifo

🎉所属专栏： 数据结构 | C语言

🎊每篇一句： 图片来源

Every challenge, every adversity, contains within it the seeds of opportunity and growth.

每个挑战，每次逆境，里面都藏有机会与成长的种子。

📘前言

排序（Sort）是初阶数据结构中的最后一块内容，所谓排序，就是通过某种手段，使目标数据变为递增或递减，排序有很多种方式：插入、选择、交换、归并、映射 等等，本文会介绍这些方式下的详细实现方法，因篇幅较长，故分为上下文的形式介绍，本文是上半部分。

下面是通过排序生成的排行榜

📘正文

📖插入排序

插入，指将数据插入到合适位置，这个分类中包含了两种排序算法：直接插入与希尔，其中希尔排序又称缩小增量排序，是一种非常快但不稳定的排序，它的时间复杂度计算极为复杂，下面详细来看看这两个排序吧

📃直接插入排序

思路：从第二个数开始，假设此数为 tmp ，逐个往前进行比对，如果前数大于 tmp ，就将前数值赋值到 tmp 处，然后继续往前比对，直到找到小于或等于 tmp 的数（或者比对至数据首）就停止，最后将 tmp 的值赋值到此处就行了

//直接插入排序voidInsertSort(int*pa, intn)
{
assert(pa);
//从后往前比较，找到合适位置就插入for (inti=1; i<n; i++)
    {
intend=i;
inttmp=pa[end];
while (end)
        {
if (pa[end-1] >tmp)
pa[end] =pa[end-1];
elsebreak;
end--;
        }
pa[end] =tmp;
    }
}

动图展示

时间复杂度：

最坏：数据为一个逆序的等差数列 O(N^2)

最好：顺序有序 O(N)

空间复杂度：

仅仅只需要一个 tmp 变量 O(1)

稳定性：

稳定，当两个相同数相遇时，后者是不会跑到前者前面去的

📃希尔排序

希尔排序是在直接插入排序上进行优化的一种排序，希尔排序分为两步：

1、预排序，使得数据尽可能接近有序

2、直接插入排序，最后调用一次直接插入排序，快速的完成排序

思路：预排序是通过区间划分实现的，假设当前区间为 gap，那么 1、1+gap*n 可以分成一组，同理2、3、4 都可以分，将这些组分别进行直接插入排序（数据少，效率高）。每完成一次分组排序，gap 就会缩小，直到 gap 为1时，进行一次直接插入排序，整个希尔排序就完成了

//希尔排序voidShellSort(int*pa, intn)
{
assert(pa);
//思路：在插入排序的基础上，先分为n个区间，使数组尽可能有序（预排序）intgap=n;
while (gap>1)
    {
gap=gap/3+1;  //确保gap最后为1for (inti=0; i<n-gap; i++)
        {
intend=i;
inttmp=pa[end+gap];
while (end>=0)
            {
//此时的end位于tmp之前sif (pa[end] >tmp)
pa[end+gap] =pa[end];
elsebreak;
end-=gap;
            }
pa[end+gap] =tmp;
        }
    }
}

动图展示（图太长了，分段展示）

1、预排序

2、直接插入排序

时间复杂度：

希尔的时间复杂度计算是一个极其复杂的过程，需要用到高等数学的知识，这里直接记就行 O(N^1.3)

空间复杂度：

仅仅只需要一个 tmp 变量 O(1)

稳定性：

不稳定，当两个相同数被不同区间选中时，可能会发生交换现象，示例 1 4 2 2 3

📖选择排序

选择排序下也可以分为两种：简单选择与之前学过的堆排序，两者的本质是一样的，都是依赖于不断的比对，选到合适数后进行交换

📃简单选择排序

思路：选到最大的数，然后与 end 值交换；优化：选最大与最小，分别与 end 值和 begin 值交换

voidswap(int*pnum1, int*pnum2)
{
assert(pnum1&&pnum2);
inttmp=*pnum1;
*pnum1=*pnum2;
*pnum2=tmp;
}
//简单选择排序voidSelectSort(int*pa, intn)
{
assert(pa);
//思路：选最小的放前面，选最大的放后面intbegin=0;
intend=n-1;
while (begin<end)
    {
intmaxi=begin;
intmini=begin;
for (inti=begin+1; i<=end; i++)
        {
if (pa[i] >pa[maxi])
maxi=i;
if (pa[i] <pa[mini])
mini=i;
        }
swap(&pa[begin], &pa[mini]);
if (maxi==begin)
maxi=mini;
swap(&pa[end], &pa[maxi]);
begin++, end--;
    }
}

动图展示：

时间复杂度：

这是一个比较糟糕的排序，因为不管是什么情况都是 O(N^2)

空间复杂度：

仅借助变量辅助交换 O(1)

稳定性：

不稳定，在选择时，可能把相同数中的后者选到前面，示例 1 4 2 2 3

注意：

当交换 min 值与 begin 值后，如果 max 等于此时的 begin ，那么就要将 max 赋为 min，即 max = min

📃堆排序

思路：堆排序用到了堆的知识，如果想排升序的话建大堆，因为大堆中堆顶是最大值，将堆顶值与堆低值交换后，执行向下调整，使其再次变为大堆，就这样反复交换、调整，堆排序就完成了

voidswap(int*pnum1, int*pnum2)
{
assert(pnum1&&pnum2);
inttmp=*pnum1;
*pnum1=*pnum2;
*pnum2=tmp;
}
voidAdjustDown(int*pa, intn, intparent)
{
assert(pa);
//大堆，找大孩子，调整intchild=parent*2+1;
while (child<n)
    {
if (child+1<n&&pa[child+1] >pa[child])
child++;
if (pa[child] >pa[parent])
        {
swap(&pa[child], &pa[parent]);
parent=child;
child=parent*2+1;
        }
elsebreak;
    }
}
//堆排序voidHeapSort(int*pa, intn)
{
assert(pa);
//思路：升序建大堆，将堆顶元素沉底，然后再调整intparent= (n-1-1) /2;   //找父亲for (inti=parent; i>=0; i--)
AdjustDown(pa, n, i);
//将堆顶元素沉底后调整intend=n-1;
while (end>0)
    {
swap(&pa[0], &pa[end]);
AdjustDown(pa, end--, 0);
    }
}

动图展示：

1、调整建堆

2、向下调整排序（上）

3、向下调整排序（下）

时间复杂度：

向下调整+交换 O(N*logN)

空间复杂度：

仅借助变量辅助交换 O(1)

稳定性：

不稳定，当两个相同值分别位于首尾时，向下调整会打乱相对顺序，示例 2 4 1 3 2

📖排序小结

更多排序将在下篇文章中讲解

📘总结

排序有很多种，有好的、有坏的，我们要重点掌握优秀的排序，比如希尔和堆排，当前其他排序的思想也得清楚，知道怎么实现就行了。本文只是排序的上半部分，涉及的排序都还算简单，下一篇文章中将会介绍排序大哥：快排，以及同样优秀的归并排序，知识点很难，但也很重要，敬请期待吧

如果你觉得本文写的还不错的话，期待留下一个小小的赞👍，你的支持是我分享的最大动力！

如果本文有不足或错误的地方，随时欢迎指出，我会在第一时间改正