【数据结构】手撕排序（一）

一、排序的概念及其运用

1.1 排序的概念

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

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

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

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

1.2 常见的算法排序

排序算法分为比较类排序和非比较类排序，如下图所示：

二、 冒泡排序

• 思想 : 在一个序列中，每次对序列中的相邻记录的键值大小进行比较，将较大(升序)或较小(降序)的记录向后移动。如此循环，大/小的记录会慢慢“浮”到序列的后端，整个过程就像是冒泡一样，顾称之为冒泡排序。
• 冒泡过程：以下是对某个序列进行冒泡排序的过程

可以看出，对于上面具有5个元素的无序数组，我们通过4趟的冒泡后就将其变为有序数组，每一趟冒泡后都可以使最大的数沉底。

• 动图演示：我们可以通过一下动图感受一下冒泡两两比较的过程：

• 循环控制：很明显，我们需要两层循环来控制冒泡排序的过程。内层循环控制当前趟的数据交换，外层循环控制冒泡排序的趟数。
• 外层循环结束条件：由于每一趟结束后都有一个数冒到序列后端，因此对于N个数的序列来说，一共需要N-1趟(只剩一个数不需要冒泡)。

for (int i = 0; i < n - 1; i++) //外层循环，N-1趟
{
     ; 
}

• 内层循环结束条件：内层循环用于数据的比较。已知N个数据共需比较N-1次，由于每一趟结束后就有数据到正确的位置，下一趟需要比较的数据个数就会少1，因此每趟的比较次数随着趟数的增加呈递减趋势，初始为N-1次。

for (int i = 0; i < n - 1; i++) //外层循环，N-1趟
{
  for (int j = 0; j < n - 1 - i; j++) //内层循环，次数随趟数增加而递减，初始为N-1
  {
           ;
  }
}

• 完整代码：

void swap(int* x, int* y)
{
  int tmp = *x;
  *x = *y;
  *y = tmp;
}
void BubblingSort(int* a, int n)
{
  for (int i = 0; i < n - 1; i++) //外层循环，N-1趟
  {
    for (int j = 0; j < n - 1 - i; j++) //内层循环，次数随趟数增加而递减，初始为N-1
    {
      if (a[j] > a[j + 1]) //升序排列，较大的往后移
      {
        swap(&a[j], &a[j + 1]); //交换
      }
    }
  }
}

• 改进优化：上面的代码还存在着改进空间，我们来看下面两个情景：

对于情境1，我们只需一趟冒泡即可让数组有序，而如果按照上面的代码，我们依旧要进行4趟的冒泡，即有三趟是无效的。

而情境2就更夸张了，数组已经有序，我们却傻乎乎的做了4趟无效冒泡。无疑是非常浪费时间的。

考虑到这些情况，我们提出了优化方案：在每趟结束后判断一下当前趟是否发生了元素交换，如果没有，则说明序列已经有序了，及时止损，反之继续。优化后的代码如下：

void swap(int* x, int* y)
{
  int tmp = *x;
  *x = *y;
  *y = tmp;
}
void BubblingSort(int* a, int n)
{
  for (int i = 0; i < n - 1; i++) //外层循环，N-1趟
  {
    int flag = 0;
    for (int j = 0; j < n - 1 - i; j++) //内层循环，次数随趟数增加而递减，初始为N-1
    {
      if (a[j] > a[j + 1]) //升序排列，较大的往后移
      {
        swap(&a[j], &a[j + 1]); //交换
        flag = 1;
      }
    }
    if (flag == 0)
      break;
  }
}

• 时间/空间复杂度：结合上面的图片和代码我们可以看出，总共N-1趟，每趟N-1，N-2…次比较，共比较 (N-1) + (N-2) + (N-3) + (N-4) + (N-5) + … + 1次，时间复杂度为O(N^2)；而由于没有额外的辅助空间，空间复杂度为O(1)。
• 稳定性分析：由于我们是将较大的或较小的进行交换，当两个数相等时并不会进行交换，因而不会改变相同元素的先后次序，所以冒泡排序是稳定的排序。

三、直接插入排序

• 基本思想

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

• 过程分析

我们可以将第一个元素作为一个有序序列，从第二个元素开始插入到这个有序序列中，过程如下：

以升序为例：

当插入第i个元素时(i>=1)，说明前面的array[0],array[1],…,array[i-1]已经排好序，我们将array[i]位置的值从后往前与array[i-1],array[i-2],…依次进行比较，找到插入位置即将array[i]插入，原来位置上的元素顺序后移。

为什么不从前往后开始进行比较？

如果我们从前往后进行比较，当找到插入位置时，根据顺序表的插入我们知道：必须先将后面的元素全部后移，而后移又不能从前往后移，否则会造成元素覆盖，我们必须从后往前移动。折腾了半天又要从后往前遍历，那为什么不一开始就从后往前比较，在比较的同时一并挪动元素，何乐而不为呢？

单趟插入动图：

全过程动图:

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];
      else
        break;
      end--;
    }
    a[end + 1] = tmp;
  }
}

复杂度/稳定性分析

复杂度:

根据上面的动图我们可以发现，当元素集合越接近有序，直接插入的时间效率越高，当元素集合已经有序时，时间复杂度便是O(N)，即遍历一遍数组（最优情况）。

而时间复杂度我们看的是最坏情况，即数组元素逆序的情况。此时每次插入相当于头插，而头插的时间复杂度为O(N)，因此总时间复杂度为O( 插入次数 * 单次插入时间复杂度 ) = O(N^2)。

而除了待排序数组之外只有常数级的辅助空间，空间复杂度为O(1)。

稳定性:

由于我们是大于tmp才进行元素挪动，当等于tmp时直接将tmp放到后方，不会对相同元素的顺序进行改变，因此直接插入排序是稳定的排序

【数据结构】手撕排序（二）：https://developer.aliyun.com/article/1393530