【数据结构】排序之插入排序和选择排序

🗒️前言：

排序是我们数据结构学习中很重要的章节，我们在生活中买东西都会挑选更好的，点外卖会选评分高的等等，这些都需要用到排序。接下来我们将会学习常见的排序算法。

一、排序的概念及其分类

📒1.1排序的概念

排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。

稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次 序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排 序算法是稳定的；否则称为不稳定的。

内部排序：数据元素全部放在内存中的排序。

外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。

📒1.2排序的分类

二、插入排序

📒2.1直接插入排序

🎀2.1.1直接插入排序的思想

把待排序的数据按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的数据插入完为止，得到一个新的有序序列 。 实际中我们玩扑克牌时，就用了插入排序的思想。

注意：数组中除了第一个元素（默认有序），其余所有元素都看作待插入数据。

🎀2.1.2排序步骤

1. 将有序数据的最后一个元素的下标记为 end，则第一个待插入元素的下标为 end+1，记作 tmp
2. 将 tmp 与有序数据从后向前依次比较
3. 如果 tmp < a[end]，就将 a[end] 向后移动，end--，再去找下一位进行比较
4. 直到 tmp > a[end] 或者 end < 0，将 tmp 插入到 end+1 的位置
5. 重复步骤，就可以实现排序

🎀2.1.3代码实现

void InsertSort(int* a, int n)
{
    for (int i = 0; i < n - 1; i++)
    {
        int end = i;
        int tmp = a[end + 1];
        while (end >= 0)
        {
            if (tmp < a[end])
            {
                a[end + 1] = a[end];
            }
            else
            {
                break;
            }
            --end;
        }
        a[end + 1] = tmp;
    }
}

🎀2.1.4直接插入排序的特点

1. 元素集合越接近有序，直接插入排序算法的时间效率越高
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)，它是一种稳定的排序算法
4. 稳定性：稳定

📒2.2希尔排序

🎀2.2.1希尔排序法的基本思想

先选定一个整数，把待排序文件中所有记录分成个组，所有距离为3的数据分在同一组内，并对每一组内的数据进行排序。然后，重复上述分组和排序的工作。当距离=1时，所有数据在统一组内排好序。

希尔排序分为两步：

1. 预排序
2. 直接插入排序

当元素集合越接近有序，直接插入排序的效率很高，希尔排序就是通过预排序使元素集合接近有序，再进行直接插入排序，这样大大提高了效率。

🎀2.2.2排序步骤

1. 选取一个合适的 gap 作为间距
2. 将间距为 gap 的数据分为一组，分成 gap 组
3. 每一组数据都进行直接插入排序，使数据接近有序
4. 不断缩小间距，当 gap==1 时，数据进行直接插入排序，实现排序

🎀2.2.3代码实现

void ShellSort(int* a, int n)
{
    int gap = n;
    while (gap > 1)
    {
        gap = gap / 3 + 1;
        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];
                    end -= gap;
                }
                else
                {
                    break;
                }
            }
            a[end + gap] = tmp;
        }
    }
}

将 i+=gap 改为 i++， 将分组排序，变为多组并排，减少了循环。

gap = gap / 3 + 1 的目的是保证 gap 最后的值为1.

🎀2.2.4希尔排序的特点

1. 希尔排序是对直接插入排序的优化。
2. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。
3. 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算。
4. 空间复杂度：O(1)
5. 稳定性：不稳定

三、选择排序

📒3.1直接选择排序

🎀3.1.1直接选择排序的思想

每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完 。

🎀3.1.2排序步骤

1. 先遍历一遍数组，找到最大的数和最小的数，记住它们的下标
2. 将最小的数交换到数组的左边，最大的数交换到数组的右边
3. begin++，end--，重复上述步骤，即可实现排序

🎀3.1.3代码实现

void SelectSort(int* a, int n)
{
    int begin = 0, end = n - 1;
    while (begin < end)
    {
        int min = begin, max = begin;
        for (int i = begin + 1; i <= end; i++)
        {
            if (a[min] > a[i])
            {
                min = i;
            }
            if (a[max] < a[i])
            {
                max = i;
            }
        }
        Swap(&a[min], &a[begin]);
        if (max == begin)
        {
            max = min;
        }
        Swap(&a[max], &a[end]);
        begin++;
        end--;
    }
}

我们要注意，当 a[max] 在数组元素的第一个，进行 Swap(&a[min], &a[begin]) 后，最大的元素的位置就发生了改变，要及时修改 max。

🎀3.1.4直接选择排序的特点

1. 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)
4. 稳定性：不稳定

📒3.2堆排序

🎀3.2.1堆排序的思想

堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。

🎀3.2.2排序步骤

1. 将待排序的数据构造成一个大堆，当前堆的根节点（堆顶）就是该组数组中最大的元素；
2. 将堆顶元素和最后一个元素交换，将剩下的节点重新构造成一个大堆；
3. 重复步骤2，每次循环构建都能找到当前堆中的最大值，并通过交换的方式把它放到该大堆的尾部，直至所有元素全部有序

🎀3.2.3代码实现

void HeapSort(int* a, int n)
{
  //第一步：建大堆
    for (int i = (n - 1 - 1) / 2; i >= 0; i--)
    {
        AdjustDown(a, n, i);
    }
    //第二步：堆删除思想进行排序（依次选数，调堆）
    for (int i = n - 1; i > 0; i--)
    {
        Swap(&a[0], &a[i]);
        AdjustDown(a, i , 0);
    }
}
void AdjustDown(HPDataType* a, int n, int parent)
{
    //默认左孩子是较小的
    int child = parent * 2 + 1;
    while (child < n)
    {
        // 找出小的那个孩子
        if (child + 1 < n && a[child + 1] < a[child])
        {
            ++child;
        }
        if (a[child] < a[parent])
        {
            Swap(&a[child], &a[parent]);
            // 继续往下调整
            parent = child;
            child = parent * 2 + 1;
        }
        else
        {
            break;
        }
    }
}

🎀3.2.4堆排序的特点

1. 堆排序使用堆来选数，效率就高了很多。
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(1)
4. 稳定性：不稳定

本次的内容到这里就结束啦。希望大家阅读完可以有所收获，同时也感谢各位读者三连支持。文章有问题可以在评论区留言，博主一定认真认真修改，以后写出更好的文章。你们的支持就是博主最大的动力。