一、前言

咳咳，好了，现在我们进入正题，首先介绍一下文章内容：

我们的文章内容主要围绕下图来进行讲解，在本篇博客中，我会阐述排序的概念，八大排序的思想、代码思路、代码实现和时空复杂度分析，并且在最后做出总结，并且附上源码链接。

今天的内容还是含金量挺高的(尤其是带⭐️的)，所以小伙伴们，打起精神，如果认认真真看完这边博客并下去练习，我相信你就可以手撕八大排序！

二、排序的概念和运用

所谓排序，就是将一串数据，按照某种规律，或者以某种特性或关键字，将数据按照递增或者递减，将数据从无序转变为有序的操作。

而排序其实在我们生活中运用十分广泛，例如在购物网站上选购一个电脑，可以通过综合、销量、评论数、新品价格来排序，如果对价格有需求，也可以按照价格升序，或者降序来排序，通过这种方式来买到心仪的商品。

而究其根本，这些都需要排序算法来实现。那么在编程中有什么排序算法，它们的性能如何？如何模拟实现这些算法？如果还不太了解的话，没关系，因为今天的内容就是讲解经典八大排序，下面我们就会一一讲解并实现。

三、八大排序讲解及实现

1、直接插入排序

1.1 排序思路

直接插入排序是一种简单的插入排序法，其基本思想是：把待排序的记录按其关键码值的大小逐个插入到一个 已经排好序的有序序列 中，直到所有的记录插入完为止，得到一个新的有序序列 。

我们的扑克牌就使用了插入排序的思想：

比如拿到牌之后，我们都会理牌，那么通常就会按照大小顺序，将“对子”，“顺子”，按照特定顺序，将牌理成整体有序，或者局部有序。

进行插入排序的步骤：

当插入第 i ( i ≥ 1 ) i(i \ge 1) i(i≥1) 个元素时，前面的 a r r a y [ 0 ] , a r r a y [ 1 ] , … , a r r a y [ i − 1 ] array[0],array[1],…,array[i-1] array[0],array[1],…,array[i−1] 已经排好序，此时用 a r r a y [ i ] array[i] array[i] 的排序码与 a r r a y [ i − 1 ] , a r r a y [ i − 2 ] , … array[i-1],array[i-2],… array[i−1],array[i−2],… 的排序码顺序进行比较，找到插入位置即将 a r r a y [ i ] array[i] array[i] 插入，原来位置上的元素顺序后移。

这么说可能还不是很直观，其实插入排序的过程就可以想象成之前我们学习 顺序表的尾插 ，我们假定序列 a r r a y [ ] array[] array[] 只有 1 1 1 个数。假定每次都是插入一个元素，且插入的元素需要将这个 ”顺序表“ 构成有序，如果插入元素 a r r a y [ i ] < a r r [ i − 1 ] array[i] <arr[i - 1] array[i]<arr[i−1] ，那么就至少需要向前调整 1 1 1 次；如果 a r r a y [ i ] ≥ a r r a y [ i − 1 ] array[i] \ge array[i - 1] array[i]≥array[i−1] 那么就 直接插入在 i i i 下标处 即可。

动图演示插入排序过程：

1.2 代码实现

对于 单趟插入排序 ，假设 e n d end end 是上一次排序的最后一个位置，那么本次需要排序的元素为 t m p = a [ e n d + 1 ] tmp = a[end + 1] tmp=a[end+1] 。

之后通过一个循环，如果 a [ e n d ] > t m p a[end] > tmp a[end]>tmp ，说明 t m p tmp tmp 插入的位置在前面，所以把 a [ e n d + 1 ] = a [ e n d ] a[end + 1] = a[end] a[end+1]=a[end] ，将元素往后移 1 1 1 格，并将 e n d − − end-- end−− ，将索引向前调整；如果 a [ e n d ] < = t m p a[end] <= tmp a[end]<=tmp ，说明 t m p tmp tmp 在当前位置： e n d + 1 end + 1 end+1 就可以直接插入，停止循环。

最后 e n d end end 停下来的位置永远是插入位置的前一个位置 ，比如：

   有序序列为 1   3   5 1 \ 3 \ 5 1 3 5 ， e n d = 2 end = 2 end=2 ， a [ e n d ] = 5 a[end] = 5 a[end]=5 ， t m p = a [ e n d + 1 ] = 0 tmp = a[end + 1] = 0 tmp=a[end+1]=0

   e n d = 2 , a [ e n d ] = 5 , t m p = 0 → a [ e n d ] > t m p → a [ e n d + 1 ] = a [ e n d ] → a [ 3 ] = 5 e n d − − → e n d = 1 end = 2, a[end] = 5, tmp = 0 → a[end] > tmp →a[end + 1] = a[end] → a[3] = 5 end-- → end = 1 end=2,a[end]=5,tmp=0→a[end]>tmp→a[end+1]=a[end]→a[3]=5end−−→end=1

   e n d = 1 , a [ e n d ] = 3 , t m p = 0 → a [ e n d ] > t m p → a [ e n d + 1 ] = a [ e n d ] → a [ 2 ] = 3 e n d − − → e n d = 0 end = 1, a[end] = 3, tmp = 0 → a[end] > tmp → a[end + 1] = a[end] → a[2] = 3 end-- → end = 0 end=1,a[end]=3,tmp=0→a[end]>tmp→a[end+1]=a[end]→a[2]=3end−−→end=0

   e n d = 0 , a [ e n d ] = 1 , t m p = 0 → a [ e n d ] > t m p → a [ e n d + 1 ] = a [ e n d ] → a [ 1 ] = 0 e n d − − → e n d = − 1 end = 0, a[end] = 1, tmp = 0 → a[end] > tmp → a[end + 1] = a[end] → a[1] = 0 end-- → end = -1 end=0,a[end]=1,tmp=0→a[end]>tmp→a[end+1]=a[end]→a[1]=0end−−→end=−1

   e n d = − 1   → e n d < 0 \color{red}end = -1 \ → end < 0 end=−1 →end<0，终止循环

   a [ e n d + 1 ] = t m p a[end + 1] = tmp a[end+1]=tmp ，最终序列 0   1   3   5 0 \ 1 \ 3 \ 5 0 1 3 5

这是单趟，那么完整的也很简单嘛，其实就是 n − 1 n - 1 n−1 趟，因为第一个元素是不用排的，第一趟其实就是排的序列的第二个元素了。每趟最终插入的位置为 e n d + 1 end + 1 end+1 ，需要防止越界。

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 (a[end] > tmp)
      {
        a[end + 1] = a[end];
        end--;
      }
      else
      {
        break;
      }
    }
    // 填到 end + 1 位置
    a[end + 1] = tmp;
  }
}

1.3 时空复杂度

插入排序的最坏的情况为，数组与我们需要排序的目标相悖。比如我们需要排升序，但是原始序列为降序 。为最坏情况，为 O ( N 2 ) O(N^{2}) O(N2) 。如果目的是升序，序列也正好是升序的话，为最好情况，这时时间复杂度为 O ( N ) O(N) O(N) 。

取其最坏，最终时间复杂度： O ( N 2 ) O(N^{2}) O(N2) 。

插入排序并没有开辟额外空间，所以 空间复杂度： O ( 1 ) O(1) O(1)

2、希尔排序

2.1 排序思路

希尔排序也属于插入排序，但是和直接插入排序又略微不同。

先看一下概念：

   希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工作。当到达=1时，所有记录在统一组内排好序。

这段话是什么意思呢？这句话是说，取一个整数，作为 间距 g a p gap gap ，对于每个元素，与其间隔为 g a p gap gap 的元素分成一个组，对每组排序 。不断调整 g a p gap gap ，对每组进行不断排序，在 g a p gap gap 调整到 1 1 1 后进行插入排序，就可以将数据排成有序。而按照间距 g a p gap gap 分组并排序被称为 预排序 。

所以可以归纳希尔排序的步骤就是 两点 ：

   预排序

   插入排序

比如，一次完整希尔排序 就像下图：

2.2 代码实现

希尔排序属于插入排序，而它的思想其实是和直接插入排序差不多的，因为最后一次希尔排序为插入排序。希尔排序无非就是多了几组预排序的过程。

所以它的代码和直接插入排序是十分相似的。

对于插入排序，我们其实就可以看做是 g a p = 1 gap = 1 gap=1 的希尔排序，那么把插入排序一些数据做一下替换，就得出了单组希尔排序 ：

// 对于一组
for (int i = 0; i < n - gap; i += gap)
{
    // 对于单个元素
    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;
}

这里的 g a p gap gap 不仅是每组中元素的间距，也是组数。上面代码只完成了单组，对于完整的一组需要在外面套上一层循环，需要循环 g a p gap gap 次：

for (int j = 0; j < gap ;j++)  
{
  for (int i = j; i < n - gap; i += gap)
    {
        // ...
    }
}

我们发现，当我们学习了直接插入排序之后，写一趟希尔排序还是很简单的。原理嘛，就和之前插入排序得到思路是相似的，只需要把之前的挪动 1 1 1 位看成挪动 g a p gap gap 位。不懂的画一下图，就完全ok了。

还有注意一下对单组进行排序时的结束条件 i < n − g a p i < n - gap i<n−gap ，这里结束条件是这个的原因为最后一组的最后一个元素下标为 n − g a p − 1 n - gap - 1 n−gap−1 ，当元素进行插入时，不能越界。

而这样写，就套了 三层循环 了，看起来比较繁杂，我们可以做出一些调整，上方代码为排 g a p gap gap 组，每次排一组。我们可以改进为 g a p gap gap 组并排 ：

for (int i = 0; i < n - gap; i++) // 注意这里从 i+= 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 + = g a p i+= gap i+=gap 变为 i + + i++ i++ 。

这里就相当于，每一次都是排其他组的数据，举个例子：当前 i = 0 i = 0 i=0 ，那么此刻排的就是第一组，之后 i + + i++ i++ ， i = 1 i = 1 i=1 ，那么此刻就是排的第二组 … 当循环结束，这 g a p gap gap 组数据也就都被排好了。这就是 g a p gap gap 组并排。

而 希尔排序的预排序的 g a p gap gap 越大时，那么对于单组中的数据就可以更快地到后面(挪动间距为 g a p gap gap)，这就造成了数据就越不接近有序；而 g a p gap gap 越小时，数据跳动越慢，但是越来越接近有序(比如插入排序) 。综合这两点，所以我们一般进行希尔排序时， g a p gap gap 是动态变化的， g a p gap gap 的初值一般为数组长度 。之后每次除以一半或者除以三分之一。

比如我们每次除以三分之一：

while (gap > 1)
{
    gap = gap / 3 + 1; // 或 gap /= 2;
    // gap 组并排
    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;
    }
}

分析：

这里调整时，是用的 g a p = g a p / 3 + 1 gap = gap / 3 + 1 gap=gap/3+1，为什么在这边 + 1 +1 +1 呢？原因是希尔排序最后 1 1 1 次为插入排序，所以最后 1 1 1 次 g a p = 1 gap = 1 gap=1 ，如果 g a p gap gap 初值为 8 8 8 ，如果每次仅仅让 g a p / = 3 gap /= 3 gap/=3 ，由于c语言中 / 是下取整，那么每次 g a p gap gap 就为 8   2   0 8 \ 2 \ 0 8 2 0 ，最后 1 1 1 次为 0 0 0 ，无法完成希尔排序，所以要加上一个 1 1 1 ，这样就可以保证最后 1 1 1 次 g a p = 1 gap = 1 gap=1 。

但是如果每次除以2的情况就不需要，因为每次 g a p / = 2 gap /= 2 gap/=2 最终结果必定等于 1 1 1 ，不信的话可以测试几组数据试试。

2.3 时空复杂度⭐️

数据被分为 g a p gap gap 组，每组有 N / g a p N / gap N/gap 个数据。那么对于那么对于单组，最坏的挪动次数就是 1 + 2 + 3 + . . . + N / g a p − 1 \color{blue}1 + 2 + 3 + ... + N/gap - 1 1+2+3+...+N/gap−1 ，是公差为 1 1 1 的等差数列。

一共有 g a p gap gap 组，那么对于一次预排序的总次数就为 ( 1 + 2 + 3 + . . . + N / g a p − 1 ) × g a p \color{blue}(1 + 2 + 3 + ... + N/gap - 1) \times gap (1+2+3+...+N/gap−1)×gap ，但是这里 g a p gap gap 是不确定的，是不好算的。

   既然这样，我们就换个角度来看，对于每次预排序的时间复杂度，该怎么计算：

   假设 g a p gap gap 每次除以 3 3 3 ，一开始 N N N 很大， g a p = N / 3 + 1 gap = N / 3 + 1 gap=N/3+1 ，将当前 g a p gap gap 的取值带入上方对于一次预排序的次数的公式中， ( 1 + 2 + 3 + . . . + N N / 3 + 1 − 1 ) × ( N / 3 + 1 ) ≈ N \color{blue}(1 + 2 + 3 + ... + \frac{N}{N / 3 + 1} - 1) \times (N/3 + 1) \approx N (1+2+3+...+N/3+1N−1)×(N/3+1)≈N ，那么起始处， 预排总次数约为 N N N 。

   … … …

   快结束时， g a p gap gap 很小，这时次数也约为 N N N ，因为此刻由于预排序的作用 ，数组几乎有序，几乎不需要排序，遍历一遍大约就可以求出！！！

   而中间的结果我们先忽略，就看起始两次，我们将其认为对于每次预排序，时间复杂度为 O ( N ) O(N) O(N) 。

如果 g a p gap gap 每次除以 3 3 3 ，那么就大约进行 N / 3 / 3 / 3... / 3 = log ⁡ 3 N N / 3 / 3 / 3 ... / 3 = \log_{3}{N} N/3/3/3.../3=log3N ；

如果 g a p gap gap 每次除以 2 2 2 ，那么就大约进行 N / 2 / 2 / 2... / 2 = log ⁡ 2 N N / 2 / 2 / 2 ... / 2 = \log_{2}{N} N/2/2/2.../2=log2N ；

那么综合起来，实际上希尔排序的时间复杂度大约在 [   log ⁡ 3 N ∗ N   ,   log ⁡ 2 N ∗ N   ] [\ \log_{3}{N} * N \ , \ \log_{2}{N} * N \ ] [ log3N∗N , log2N∗N ] 这个量级之间 ，和我们之前学习过的堆排序的时间复杂度相近。

但是这只是我们的一些计算推导，实际上希尔排序真正的时间复杂度很难计算，上面我们计算只是简单推导而已，里面其实涉及到了很多数学只是，所以我们再参考一下著名的数据结构书籍中对于希尔排序时间复杂度的分析：

《数据结构-用面相对象方法与C++描述》— 殷人昆

而 g a p gap gap 是按照 K n u t h Knuth Knuth 大佬提出的方式取值的， K n u t h Knuth Knuth大佬进行了大量的试验统计，我们在这里先认为 希尔排序的最终时间复杂度为 O ( N 1.3 ) O(N^{1.3}) O(N1.3) 。

而空间复杂度就很简单了，并没有开辟额外的空间，所以空间复杂度为 O ( 1 ) O(1) O(1) 。

3、直接选择排序

3.1 排序思路

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

   选择排序的步骤：

       在元素集合 a r r a y [ i ] − − a r r a y [ n − 1 ] array[i]--array[n-1] array[i]−−array[n−1] 中选择关键码最大(小)的数据元素

       若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后一个（第一个）元素交换

       在剩余的 a r r a y [ i ] − − a r r a y [ n − 2 ] array[i]--array[n-2] array[i]−−array[n−2]（ a r r a y [ i + 1 ] − − a r r a y [ n − 1 ] array[i+1]--array[n-1] array[i+1]−−array[n−1]）集合中，重复上述步骤，直到集合剩余 1 1 1 个元素

下面使用动图展示一下选择排序的过程：

3.2 代码实现

假设我们排升序，那么每次就要选最小数的下标 m i n i mini mini ，遍历数组，找出 m i n i mini mini ，然后交换，让起始位置 b e g i n + + begin++ begin++ ，直到 b e g i n = n begin = n begin=n 停止，此刻数组就有序了。

void SelectSort(int* a, int n)
{
  // 选 1 个数
  int begin = 0;
  while (begin < n)
  {
    int mini = begin;
    for (int i = begin + 1; i < n; i++)
    {
      if (a[i] < a[mini])
      {
        mini = i;
      }
    }
    Swap(&a[begin], &a[mini]);
    begin++;
  }
}

这是我们单次选 1 1 1 个数的情况，实际上我们还可以一次选两个数 m i n i mini mini 和 m a x i maxi maxi 对应最小和最大值：

这里代码需要做出一些改变，增加一个终止位置 e n d end end 。循环找 m i n i mini mini 和 m a x i maxi maxi ，每次找到之后交换 b e g i n begin begin 和 m i n i mini mini 对应的值和 e n d end end 和 m a x i maxi maxi 对应的值，将 b e g i n + + , e n d − − begin++, end-- begin++,end−− ，直到 b e g i n ≥ e n d begin \ge end begin≥end 。

但是这里有一个 注意点 ：

假设序列已经找到了 m i n i mini mini 和 m a x i maxi maxi ：

begin 和 m a x i maxi maxi 的位置重合了，那么 b e g i n begin begin 和 m i n i mini mini 在交换的时候，就把最小值换到了 b e g i n ( m a x i ) begin(maxi) begin(maxi) 处，最大值被换走了 。那么接下来交换 e n d end end 和 m a x i maxi maxi 的时候，就把 最小值 换到了 e n d end end 处。

这就导致了排序错误，我们原本期望的序列为图中含有绿色方格的一块。

所以我们需要处理一下，但 b e g i n = = m a x i begin == maxi begin==maxi 时，在交换过 b e g i n begin begin 和 m i n i mini mini 的值后，原 m i n i mini mini 的值为当前的最大值，那么就把 m a x i = m i n i maxi = mini maxi=mini ，让最大值下一次能交换到正确的位置。

void SelectSort(int* a, int n)
{
  int begin = 0, end = n - 1;
  while (begin < end)
  {
    int mini = begin, maxi = begin;
    for (int i = begin + 1; i <= end; i++)
    {
      if (a[i] < a[mini])
      {
        mini = i;
      }
      if (a[i] > a[maxi])
      {
        maxi = i;
      }
    }
    Swap(&a[begin], &a[mini]);
    // 特殊处理
        if (begin == maxi)
    {
      maxi = mini;
    }
    Swap(&a[end], &a[maxi]);
    begin++;
    end--;
  }
}

3.3 时空复杂度

选择排序无论是选单边，还是两边一起选，时间复杂度都是铁铁的 O ( N 2 ) O(N^{2}) O(N2) 。因为总是要每次遍历选出 最小/大下标，然后进行数据交换。

所以选择排序的效率是不太行的，一般不常用，但是它的思路很简单。

空间复杂度是 O ( 1 ) O(1) O(1) ，因为没有开辟额外空间 。