数据结构与算法⑰(第五章_八大排序)(完整代码+动图+详解+对比)（上）-阿里云开发者社区

排序：所谓排序，就是使一组杂乱无章的数据，按照其中的一定的规律或某些关键字

(如价格，销量，好评率，排名等)的大小，递增或递减地排列起来的操作。

为了方便，我们这里讲的排序和有序指的都是升序，降序反过来就行了。

1.插入排序

1.1直接插入排序

核心思想：

把一个数插入一个有序区间。

实现方法：假设0—end是已经有序的区间，我们用x存储end后面一个位置的元素，表示要把x存储到0—end的有序区间中。

如果end所指元素比x大，就把end所指的元素赋给后面一个位置的元素（相当于把end所指元素往后移动一个格子），然后end=end-1使end指向前一个元素，继续比较；

1.1.1单趟插入排序：（把x插入一个有序数组）

 
//单趟排序：（把x插入一个有序数组）
// 1 2 3 5 9 10 12    x=4
void InsertSort(int* arr, int sz)
{
    int end;
    int x;
    while (end >= 0)
    {
        if (arr[end] > x)
        {
            arr[end + 1] = arr[end];
            end--;
        }
        else
        {
            break;
        }
    }
    arr[end + 1] = x;//插入在最头上和插入在中间都在这里处理
}

整个数组排序，如何控制呢？我们把上面的x赋值给arr[ end +1 ] 然后重复插入就是这样：

1.1.2完整插入排序代码：

 
void InsertSort(int* arr, int sz)
{
    assert(arr != NULL);
    for (int i = 0;i <= sz - 2;i++)
    {
        int end = i;//把数组第一个元素当作有序，像打扑克牌摸牌排序一样
        int x = arr[end + 1];
        //x已经保存了a[end + 1] 所以后面再覆盖也可以 因此end只能落在n-2
        while (end >= 0)
        {
            if (arr[end] > x)
            {
                arr[end + 1] = arr[end];
                end--;
            }
            else
            {
                break;
            }
        }
        arr[end + 1] = x;
    }
}

为了验证代码，我们像以前一样分文件写，先把部分Sort.c和Test.c放出来，后面再把完整的放出来

 
#include"Sort.h"
先写打印数组函数和交换函数（后面排序使用）
 
void printArr(int* arr, int sz)
{
    for (int i = 0;i <= sz - 1;i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n");
}
 
int main()
{
    int arr[] = { 1,6,5,4,7,8,9,2,0,3 };
    int sz = sizeof(arr) / sizeof(arr[0]);
    printArr(arr, sz);
 
    InsertSort(arr, sz);
    printArr(arr, sz);
    //输出：0 1 2 3 4 5 6 7 8 9
    return 0;
}

1.1.3插入排序复杂度分析：

直接插入排序最坏情况是逆序（每插入一个都要移动,从第二个元素开始，第二个元素需要移动1次，第三个元素需要移动2次，…，第n个元素需要移动n-1次）

取最大项就是O(N^2).

最好情况是已经有序或者基本有序，就只需要遍历一次数组（有序）或者偶尔几个元素需要移动几次格子再插入其他的直接插入在end所指元素后面就行（基本有序），故最好情况下时间复杂度是O(N)。

没有开辟额外的空间所以：插入排序的空间复杂度是O（1），时间复杂度是O（N^2）

我们之前写过冒泡排序

我们现在元素移动次数上进行分析，如果一组无序的数据通过冒泡排序排好序之后，

它的交换次数是这种数据的逆序度；对于插入排序来说也是一样的，

移动次数上都是原本数据的逆序度。

元素的移动次数是相同的，那我们接下来看看元素的交换次数。从代码上分析可以明显看出，

冒泡排序的一次交换需要三行代码，而插入排序的交换却需要一行，

所以总的交换次数冒泡排序大于插入排序。

有小伙伴会问，这两行的差别有那么大吗？移动一次，我们可以不计较，

如果数据很多，想想下，两者的效率差别很轻易的就比较出来了。

虽然冒泡排序的时间复杂度和插入排序的时间复杂度是相同的，

但是我们实际使用中还是优先选择插入排序。

对于插入排序还是可以优化的，对了，没错，就是下面的希尔排序

这里先说插入排序是比冒泡排序好的排序。（铺垫）

（我在最后的八大排序完整代码中放入了测试效率的测试，想测任何排序的时候可以去看看）

这里想到方便对比，所以讲完八大排序后再统一讲完八大排序的复杂度

1.2希尔排序

插入排序面对逆序或不太有序的情况下效率比较低，但是面对基本有序的情况它是非常棒的排序

（基本有序的话时间复杂度是O(N)，是排序算法的天花板，没有一个排序算法能比O(N)快）。

为了优化直接插入排序，一个叫希尔的人想出来了一种排序（希尔排序），核心思想：

希尔排序就是在直接插入排序上优化，既然对基本有序的情况直接插入排序很棒，

那我先分成gap组进行一个预排序（这个过程可以使数组基本有序），

然后再进行一个直接插入排序，那么怎么样进行预排序呢？

预排序步骤：

1.2.1单趟预排序：

按gap（缺口，缝隙，差距）分组，分成gap组，gap>1，对每个组进行插入排序，

使总体数组看起来接近有序

实际上就是把0，0+gap，0+2gap…视为一组，1，1+gap，1+2gap…视为一组...

对每一组进行直接插入排序，这样每一组都是有序的了，总体数组就比之前有有序多了。

那么对0,0+gap,0+2gap…这一组预排序的单趟排序代码如下（这里gap取3）：

 
//分组的单趟和前面单趟插入排序一样，间距是gap，前面可以认为gap=1
//按gap分组进行预排序
    int gap = 3;
    int end = 0;
    int x = arr[end + gap];
    while (end >= 0)
    {
        if (arr[end] > x)
        {
            arr[end + gap] = arr[end];
            end -= gap;
        }
        else
        {
            break;
        }
    }
    arr[end + gap] = x;

1.2.2对所有组的预排序：

 
//依次排完gap组
int gap = 3;
for (int j = 0; j < gap; j++)
{
    for (int i = j; i < n - gap; i += gap)
    {
        int end = i;
        int x = arr[end + gap];
        while (end >= 0)
        {
            if (arr[end] > x)
            {
                arr[end + gap] = arr[end];
                end -= gap;
            }
            else
            {
                break;
            }
        }
        arr[end + gap] = x;
   }
}

上面的代码虽然清楚，但是不够简洁，我们可以对多组同时进行预排序，

就好像把多组同时一锅炖了一样。对单趟多组预排序的代码改造如下：

1.2.3预排序代码简化：

 
int gap = 3;
for (int i = 0; i < n - gap; i++)
{
    int end = i;
    int x = arr[end + gap];
    while (end >= 0)
    {
        if (arr[end] > x)
        {
            //如果end所指的元素比x大
            //就把end所指元素往后移动，空出一个格子
            arr[end + gap] = arr[end];
            end -= gap;
        }
        else
        {
            //否则就跳出去，
            //这样可以同时处理end小于0的情况（插入在最头上的情况）
            break;
        }
    }
    arr[end + gap] = x;
}

怎么取gap呢？讨论一下预排序的时间复杂度

与直接插入排序类似，最好情况是已经有序的时候，是O(N)（遍历一遍就行了）

最坏情况：每一组都是逆序的，每一组的元素个数是[N/gap]，这样的总共需要的循环次数是：gap*(1+2+3+…+[N/gap]-1)（套用最糟糕情况直接插入排序的循环次数，gap组）。

观察这个总共需要的循环次数的函数，发现:

gap越大预排越快(gap=N，O(N)) ,但是因为分的组数太多了，排完后越接近无序；

gap越小预排越慢(gap=1，O(N^2)),分的组数少排完后越接近有序。

多趟分组预排序与最后的直接插入排序

为了让最后进行插入排序的时候数组能更接近有序一些，我们可以加一个循环控制gap不断变化进行多趟分组预排序，并且把gap=1时，也就是最终进行直接插入排序耦合到while循环里，代码如下：

1.2.4完整希尔排序代码：

 
void ShellSort(int* arr, int sz)
{
    int gap = sz;
    //多次预排序(gap > 1)+直接插入排序(gap == 1)
    while (gap > 1)//gap进去以后才除所以大于1就行
    {
        //两种取gap的方法：
        //gap = gap / 2;//一次跳一半
        gap = gap / 3 + 1;
        //加一是为了保证最后一次gap小于3的时候
        //能够有gap等于1来表示直接插入排序
        //多组同时搞：
        for (int i = 0; i < sz - gap; i++)
        {
            int end = i;
            int x = arr[end + gap];
            while (end >= 0)
            {
                if (arr[end] > x)
                {
                    arr[end + gap] = arr[end];
                    end -= gap;
                }
                else
                {
                    break;
                }
            }
            arr[end + gap] = x;
        }
    }
}

代码测试（依然输出0 1 2 3 4 5 6 7 8 9）

 
#include"Sort.h"
 
int main()
{
    int arr[] = { 1,6,5,4,7,8,9,2,0,3 };
    int sz = sizeof(arr) / sizeof(arr[0]);
    printArr(arr, sz);
 
    //InsertSort(arr, sz);
    ShellSort(arr, sz);
    printArr(arr, sz);
    return 0;
}

2.选择排序

2.1选择排序

在一个长度为 N 的无序数组中，第一次遍历 n-1 个数找到最小的和第一个数交换。
第二次从下一个数开始遍历 n-2个数，找到最小的数和第二个数交换。

重复以上操作直到第 n-1 次遍历最小的数和第 n-1 个数交换，排序完成。

2.1.1选择排序代码：

 
void SelectSort(int* arr, int sz)
{
    //先假设第一个元素最小
    for (int i = 0; i < sz; i++)
    {
        int begin = i;
        int minindex = i;
        while (begin < sz)
        {
            if (arr[begin] < arr[minindex])
            {
                minindex = begin;
            }
            begin++;
        }
        Swap(&arr[minindex], &arr[i]);
    }
}

2.1.2选择排序代码优化：

我们可以定义一个begin变量，一个end变量，用来记录数据首和尾的下标，我们一个可以找出两个值，一个最大值，一个最小值，最小值放在a[begin]中，最大值放在a[end]中，这样我们就比上面的快多了

 
void SelectSort(int* arr, int sz)
{
    int begin = 0;
    int end = sz - 1;
    while (begin < end)
    {
        int mini = begin;
        int maxi = end;
        int i = 0;
        for (i = begin;i <= end;i++)
        {
            //选出[begin,end]中最大和最小的
            if (arr[i] < arr[mini])
            {
                mini = i;
            }
            if (arr[i] > arr[maxi])
            {
                maxi = i;
            }
        }
        Swap(&arr[begin], &arr[mini]);
        //这里需要考虑第一个值放最大值的情况，如果第一个值为最大值,此时最大值位置被移动
        if (begin == maxi)
        {
            maxi = mini;//最大的值被换到了mini的位置，更新最大值的位置
        }
        Swap(&arr[end], & arr[maxi]);
        begin++;
        end--;
    }
}

2.2堆排序

要学习堆排序，首先要学习基础的二叉树结构，学习堆的向下调整算法，使用堆排序之前，

我们得先建一个堆出来，堆的向下调整算法的前提是：根节点的左右子树均是大堆或小堆。

由于堆排序在向下调整的过程中，需要从孩子中选择出较大或较小的那个孩子，

父亲才与孩子进行交换，所以堆排序是一种选择排序。

堆排序的详解请移至博客：

数据结构与算法⑫(第四章_中_续一)堆排序（详解）_GR C的博客-CSDN博客

2.1.1堆排序代码：

 
void justDown(int* arr, int sz, int father_idx)
{
    int child_idx = father_idx * 2 + 1; // 计算出左孩子的值（默认认为左孩子大）
    while (child_idx < sz) // 最坏情況：调到叶子（child_idx >= 数组范围时必然已经调到叶子）
    {
        if ((child_idx + 1 < sz) && (arr[child_idx + 1] > arr[child_idx]))
        {   // 如果右孩子存在且右孩子比左孩子大
            child_idx = child_idx + 1;// 让其代表右孩子
        }
        if (arr[child_idx] > arr[father_idx])//如果孩子的值大于父亲的值（不符合大堆的性质）
        {
            Swap(&arr[child_idx], &arr[father_idx]);
            father_idx = child_idx;          // 更新下标往下走
            child_idx = father_idx * 2 + 1;  // 计算出该节点路线的新父亲
        }
        else // 如果孩子的值小于父亲的值（符合大堆的性质）
        {
            break;
        }
    }
}
 
//完整堆排序_升序
void HeapSort(int* arr, int sz)
{
    //创建大堆，选出最大的数，时间：O(N)
    int father = ((sz - 1) - 1) / 2;  // 计算出最后一个叶子节点的父亲
    while (father >= 0)
    {
        justDown(arr, sz, father);
        father--;
    }
 
    //交换后调堆  时间：O(N * logN)
    int end = sz - 1;
    while (end > 0)
    {
        Swap(&arr[0], &arr[end]);
        justDown(arr, end, 0);
        end--;
    }
}

数据结构与算法⑰(第五章_八大排序)(完整代码+动图+详解+对比)（中）：https://developer.aliyun.com/article/1513587

数据结构与算法⑰(第五章_八大排序)(完整代码+动图+详解+对比)（上）