【数据结构】八大排序（上）

排序的基础知识

1.排序的相关概念

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

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

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

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

比较排序：通过比较两个元素的大小来确定元素在内存中的次序，我们常见的入选择排序、插入排序、比较排序与归并排序都属于比较排序。

非比较排序：通过确定每个元素之前，应该有多少个元素来排序，常见的非比较排序有基数排序、计数排序与桶排序。

2.常见的排序种类

3.排序的应用

排序在我们的日常生活中是非常常见的，比如我们在京东/淘宝上购物商品时，可以选择按销量排序、按价格排序、按评论排序，又比如世界500强企业，中国前50所高校等等，这些地方都需要用到排序。

常见排序的算法实现

注：以下排序全部基于升序举例

1.直接插入排序

1.排序思想

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

实际中我们玩扑克牌时，就用了插入排序的思想

动图演示：

2.代码实现

void InsertSort(int* a, int n)
{
  //假设[0,end]有序，要排序的是[0,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;
      }
    }
    a[end + 1] = tmp;
  }
}

注意：我们实现代码的时候假设[0,end]是有序的，然后将end+1的值插入到其中，使[0,end+1]有序，上述代码中，for循环里面我们让tmp保存的是数组中下标为end+1的值，end是i，所以当end=n-1的时候，tmp保存的值就已经越界了，所以我们的循环条件设置为i < n - 1。

3.复杂度

时间复杂度：

最坏情况：每次插入的新数据最后都需要插入在下标为0的位置上，此时每个单趟排序的时间复杂度为end，所以一共要挪动1+2+3+…+n-1次，所以最坏时间复杂度为O(N2).

最好情况：每次插入新的数据的时候，都不需要挪动，此时的时间复杂度为O(N).

结论：直接插入排序的时间复杂度为O(N)

空间复杂度

由于没有开辟新的空间，因此空间复杂度为O(1).

4.特性总结

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

2.希尔排序(缩小增量排序)

1.排序思想

希尔排序是直接插入排序的优化。它分为两个步骤

1. 预排序 目的：接近有序
2. 直接插入排序

预排序的时候，需要选定一个gap，然后把相隔gap距离的元素分为一组，一共分为gap组，对每一组进行排序，然后重复操作，当gap为1的时候就是直接插入排序。

希尔排序相较于直接插入排序优化的点：对于需要排序数据量特别大，数据特别乱的数据，预排序会让数据更快趋近于有序，当gap==1的时候就是直接插入排序。

2.代码实现

void ShellSort(int* a, int n)
{
  int gap = 3;
  while (gap > 1)
  {
    gap = gap / 3 + 1;
    //假设[0,end]有序，插入a[end+gap]保持有序
    for (int i = 0; i < n - gap; i++)
    {
      int end = i;
      int tmp = a[end + gap];
      while (end >= 0)
      {
        if (a[end] > tmp)
        {
          a[end + gap] = a[end];
          end -= gap;
        }
        else
        {
          break;
        }
        a[end + gap] = tmp;
      }
    }
  }
}

注意：希尔排序中gap的取值时不确定的，我们这里对gap的处理是初始化为n，然后除3加1，这就意味着如果按照最坏的情况来看，第一次预排序的时候一个元素只需要3次就可以达到它应该在的位置附近，加1是为了保证最后一次gap的值为1，当gap==1时，就是直接插入排序。

3.复杂度

时间复杂度：

希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在很多书中给出的希尔排序的时间复杂度都不固定：

《数据结构(C语言版)》— 严蔚敏

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

由于我们这里对gap的处理是按照Knuth提出的方式取值的，而且Knuth进行了大量的试验统计，我们暂时就按照：O(N^1.25)

到O(1.6*N^1.25)来算。

空间复杂度

由于没有开辟新的空间，因此空间复杂度为O(1).

4.特性总结

1. 希尔排序是对直接插入排序的优化。
2. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。
3. 时间复杂度O(N^1.25)到O(1.6*N^1.25)
4. 稳定性：不稳定