1、冒泡排序

1.1 排序思路

冒泡排序属于交换排序，所谓交换排序就是就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。

这个排序像水面冒气泡一样，从底部(数组开头)冒到水面上(数组结尾)，一次冒一个数据，所以被形象的称为“冒泡排序”。

看一下动图：

1.2 代码实现

冒泡排序的单趟排序会把前(n-j)个元素中的最大值交换到(n-j-1)的位置(增加数组的有序后缀长度)

 // 单趟排序
    int j = 0;  //记录排序的趟数 
    for (int i = j; i < n - j - 1; i++)
    { //交换次数随着趟数减少
      if (a[i] > a[i + 1])
      {
        Swap(&a[i], &a[i + 1]);
        flag = 0;
      }
    }

排n 个数，那么就需要冒泡n−1 趟，将数据冒到结尾，在每趟冒泡排序中，比较相邻两个元素，如果满足条件，则交换，交换到其最终应该出现的位置(比如将第n大的数交换到数组下标为N-n的位置)

void BubbleSort(int* a, int n)
{
    //n个元素排 n - 1 趟
  for (int j = 0; j < n - 1; j++) 
  {
    int flag = 1;//flag用于标记数组是否已经有序
        // 单趟排序
    for (int i = 0; i < n - j - 1; i++)
    {//交换次数随着趟数减少
      if (a[i] > a[i + 1])
      {
        Swap(&a[i], &a[i + 1]);
        flag = 0;
      }
    }
    if (flag)
    {
      break;
    }
  }
}

仔细看，其实这里我们的代码是优化过的：如果一趟冒泡排序中，没有发生交换，说明有序，那么 break 退出循环。

比如序列1 2 2 4 6

在一趟冒泡排序中始终满足 a [ i ] ≤ a [ i + 1 ] ，没有发生交换，说明它本身是有序的，所以无需排序了，直接退出。

1.3 特性及复杂度

冒泡排序的时间复杂度为O(N^2)，可能会感到疑惑，冒泡排序不是优化过了吗？为什么时间复杂度为 O(N^2)？

因为冒泡排序每次的比较次数，是随着趟数而减少的，找一下规律，其实可以发现，它的总执行次数是一个公差为 −1 的等差数列：(n - 1) + (n - 2) + … + 1 ，根据等差数列求和公式得： 根据时间复杂度规律，最终为 O(N^2) 。

，根据时间复杂度规律，最终为 O(N^2) 。

而我们的优化是只对 数组前半部分有序 或 整体几乎有序 才有优化作用，如果有序的部分在后半段，每趟排序还是要从头开始一一比较，相当于还是重新排序。

其实数组前半部分有序的优化程度也不大，最好情况是 优化后 在 整体有序 的情况下，遍历一遍数组，通过 break 退出，这时 最好时间复杂度为O(N) 。

综上，取最坏情况，时间复杂度为O(N^2)。

空间复杂度为 O(1) 。

冒泡排序虽然效率不高，但他有特殊的意义：教学意义(bushi)

特性：冒泡排序是一种非常容易理解的排序。

时间复杂度：O(N^2) 。

空间复杂度：O(1) 。

稳定性：稳定。

2、快速排序

2.1 算法思想

快速排序是Hoare 于1962年提出的一种二叉树结构的交换排序方法，其 基本思想 为任取待排序元素序列中的某元素作为基准值key，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

2.2 快排递归版本

快排为交换排序的一种。用更详细的方式来讲，快排在开始时，会选择一个 key 做基准值，并设定 给定，然后进行单趟排序，单趟排序后，当排序停止，会把 key 的索引或 key 值本身与边界某一值交换，形成区间划分。

这个区间划分通常为 key 左边的值都小于 key ，key 右边的值都大于 key ，这样就使得区间被划分了。中间的 key 值不用管，当前 key 值已经到了正确的位置。那么现在排序就变为：对左区间和右区间的排序。

那么每次排序后都会确定一个元素的位置，确定位置后继续划分区间…这样的过程实际上就是递归，通过递归，对设定的基准值分割开的左右区间完成排序。

递归的返回条件为begin >= end ，此刻说明区间只有 1 个元素或无元素。

根据上述，我们可以写出大概思路：

void QuickSort(int* a, int begin, int end)
{
  if (begin >= end)
  {
    return;
  }
  // 对左右区间进行划分
    int key = partion(a, begin, end);
    // 递归左右区间
    QuickSort(a, begin, key - 1);
    QuickSort(a, key + 1, end);
}

上述为快速排序递归实现的主思路，我们可以发现与这个思路与二叉树前序遍历非常像，在写递归框架时可回想一下二叉树前序遍历规则，最后我们只要分析如何按照 基准值key 来对区间中数据进行划分即可。

而按照基准值划分区间的方法有三种，分别为 hoare 版本、挖坑法、双指针版本 ，接下来我们一一学习。

2.2.1 hoare 版本

hoare 大佬是快速排序发明者，但是在实现这个版本时很容易踩坑。

快速排序的单趟排序要达到的目的:

1.将数组中某个元素(key元素)交换到其在有序序列中最终应该出现的位置,即:

单趟排序结束后要保证key元素之前的元素都比key元素小

单趟排序结束后要保证key元素之后的元素都比key元素大

2.单趟排序接口返回key元素最后的位置下标(作为数组分割点)

先看动图：

hoare 版本的思路：

1.首先取左边界为基准值 key ，定义两个指针left、right 分别指向最左边和最右边的元素。

2.right 先走，如果right 指向的元素大于 key 指向的元素，则right−− ，如果指向元素小于 key 指向的元素，则停止；

3.停止之后，left 开始走，如果 left 指向的元素小于key 指向的元素，则left++ ，如果指向元素大于key 指向的元素，则停止；

4.当 left 和right 都停下后，交换left 和 right 位置的值。

5.直到left≥right ，循环停止。

上面过程就保证了 left 和 right 相遇的位置的值是小于key 的， 此刻交换 a[left]（或a[right]）和a[key] ，令key=left（或right） ，此刻左右区间就已经被划分好了，key 就是分割点。

规定:如果取左边作为key 就要保证左边比 key 小，右边比key 大；如果取右边作为key 则右边比 key 小，左边比key 大。

一些相关的问题 ：

问题1：为什么 left 和 right 相遇的位置是小于 key或直接就是key的位置(序列为升序) 的？是巧合还是必然？

这是必然的，接下来分析一下，一共有两种情况：

第一种是 right 停住，left 遇到right ，相遇位置就是right 停住的位置。

当前情况就是right 在走时，遇到比 a[key] 小的元素停住了，然后 left 走时，和right 位置是小于key 。

第二种是left 停止，right 遇到left ，相遇位置是 left 停住的位置。

left 和right 已经交换过一次元素，所以left 的位置必定小于key ，left 停住了，之后right 走，直到和left 相遇，相遇位置是小于key 的。

还有一种特殊情况，就是right 先走，右边的数字都比 a[key] 大，right−− ，right 一直走到与 left 重合，a[key] 和 a[left] 交换后不变。

否则，当key在左，L先走的时候，就会出现问题

问题2：开头说过hoare 大佬的版本很容易踩坑，坑在哪里？如何解决？

其实这里容易引起的错误还是很多的，比如：

1.左右两边都有和 key 相等的值，导致左右两边卡死。

举个例子：

例如这种情况，a[key]=6 ，右边先走时，由于 a[right]=a[key] ，不走；左边走时，由于 a[left]=a[key] ，也不走。这样就死循环了！

所以，我们一开始的思路是需要 改进 的，当a[right]≥a[key] 时，right−−；在 a [ left ] < = a[left]<=a[key] 时，left++。这样就解决了 死循环的问题 。

2.但是修好了这个 bug 另一个 bug 就冒出来了，一旦加上上面的条件，如果 key 右边的值都大于key ，且循环内部不加限制，right 就会一直 −− ，由于没有限制，right 就 停不下来了。 所以在 right 和left 每次走的时候需要加上限制 left<right 。 3.但还是存在问题，由于一开始的时候++left，导致最后交换的时候没有考虑到最开始keyi的值的比较 如何解决呢？去掉++left 由此，我们就可以写出代码：

// hoare 版本
int partion1(int* a, int begin, int end)
{
  int left = begin, right = end;
  int key = left;
  while (left < right)
  {
    // 右边先走
    // 两个条件一个防止跑出去，找大于 a[key] 的值
    while (left < right && a[right] >= a[key])
    {
      right--;
    }
    while (left < right && a[left] <= a[key])
    {
      left++;
    }
    Swap(&a[left], &a[right]);
  }
  // 交换值, key 作为分割点
  Swap(&a[left], &a[key]);
  key = left;
  return key;
}

2.2.2 挖坑法

由于hoare 大佬版本存在的 “坑” 比较多，后面就有一些未留名的大佬在 hoare 版本的基础上，对快排做出了一些改良，比如我们的 挖坑法 。

优点：不需要左边作key，右边先走等要求，且排出来顺序一般与hoare的版本不一样

单趟排序算法实现思想:

1.选择arr[left]作为key(key变量存储key元素的值)

2.以初始left指向的位置作为初始坑位(坑位下标用hole变量来记录)

3.right指针向前遍历寻找比key小的数,找到后将right指向的元素赋值到坑位上,将right下标值赋给hole(更新坑位)

4.left指针向后遍历寻找比key大的数,找到后将left指向的元素赋值到坑位上,将left下标值赋给hole(更新坑位)

5.重复上述迭代过程直到left指针和right指针相遇

挖坑法的思路：

1.挖坑法多了一个hole ，也就是坑位。我们将 key = a[left] ，将 key 保存到一个临时变量中，假设 key 这个位置的值被挖掉了，形成一个坑位。此时 hole 就是坑位的下标。

2.依然是右边先走，循环条件为left<right 并且right 指向的元素大于等于key ，一旦 right 停下来，那么就把 a[hole]=a[right] ，把right 指向的值填到坑中，此刻right 作为新的坑。

3.而 right 之前的值也被转移到了别的地方，这个位置就被看做为空，变成坑。

4.左边则是相同的思路，同理左边停下后，让 a[hole]=a[left] ，让 left 作为新的坑。

5.直到left≥right 停止。

6.最后的hole 就是key 值该去的地方，把这个地方填上 key ，此刻 hole 为分割点。

代码实现：

int partion2(int* a, int begin, int end)
{
  int left = begin, right = end;
  int key = a[left];
  int hole = left;
  while (left < right)
  {
    // 右边找小，填到左边坑里面
    while (left < right && a[right] >= key)
    {
      right--;
    }
    a[hole] = a[right];
    hole = right;
    // 左边找大，填到右边坑里面
    while (left < right && a[left] <= key)
    {
      left++;
    }
    a[hole] = a[left];
    hole = left;
  }
  a[hole] = key;
  // 最后 left 和 right 都在坑上，和 hole 是重合的
  return hole;
}