快期末考试了，数据结构考试排序应该会有一道排序大题。所以做一个总结

TIP

其实主要使用快排和归并排序，其他的排序没有必要进行记忆，用到的时候查就可以了

简介

排序算法 （Sorting algorithm）是一种将一组特定的数据按某种顺序进行排列的算法。排序算法多种多样，性质也大多不同。

稳定性

稳定性是指相等的元素经过排序之后相对顺序是否发生了改变。

拥有稳定性这一特性的算法会让原本有相等键值的纪录维持相对次序，即如果一个排序算法是稳定的，当有两个相等键值的纪录 $R$ 和 $S$ ，且在原本的列表中 $R$ 出现在 $S$ 之前，在排序过的列表中 $R$ 也将会是在 $S$ 之前。

基数排序、计数排序、插入排序、冒泡排序、归并排序是稳定排序。

选择排序、堆排序、快速排序不是稳定排序。（都可以通过 pair 实现稳定性，所以没有什么实际意义）

① 选择排序

选择排序（Selection sort）是排序算法的一种，它的工作原理是每次找出第 $i$ 小的元素（也就是 $A_{i..n}$ 中最小的元素），然后将这个元素与数组第 $i$ 个位置上的元素交换。

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
template <typename T>
vector<T> &SelectSort(vector<T> &arr) {
    for (size_t i = 0; i < arr.size() - 1; i++) {
        int minindex = i;
        for (size_t j = i + 1; j < arr.size(); j++) {
            if (arr.at(j) < arr.at(minindex)) {
                minindex = j;
            }
        }
        swap(arr.at(minindex), arr.at(i));
    }
    return arr;
}
int main() {
    vector<int> test;
    for (size_t i = 0; i < 10; i += 2) {
        test.push_back(i);
    }
    for (size_t i = 0; i < test.size(); i++) {
        cout << test.at(i) << ' ';
    }
    cout << endl;
    reverse(test.begin(), test.end());
    for (size_t i = 0; i < test.size(); i++) {
        cout << test.at(i) << ' ';
    }
    cout << endl;
    SelectSort(test);
    for (size_t i = 0; i < test.size(); i++) {
        cout << test.at(i) << ' ';
    }
    return 0;
}

稳定性

由于 swap（交换两个元素）操作的存在，选择排序是一种不稳定的排序算法。

时间复杂度

选择排序的最优时间复杂度、平均时间复杂度和最坏时间复杂度均为 $O(n^2)$ 。

代码实现

• 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
• 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
• 重复第二步，直到所有元素均排序完毕。

② 冒泡排序

冒泡排序（英语：Bubble sort）是一种简单的排序算法。由于在算法的执行过程中，较小的元素像是气泡般慢慢「浮」到数列的顶端，故叫做冒泡排序。

工作原理

每次遍历就会就位一个元素，有序部分逐渐扩展，无序部分逐渐减小

它的工作原理是每次检查相邻两个元素，如果前面的元素与后面的元素满足给定的排序条件，就将相邻两个元素交换。当没有相邻的元素需要交换时，排序就完成了。

经过 $i$ 次扫描后，数列的末尾 $i$ 项必然是最大的 $i$ 项，因此冒泡排序最多需要扫描 $n-1$ 遍数组就能完成排序。

稳定性

冒泡排序是一种稳定的排序算法。

时间复杂度

在序列完全有序时，冒泡排序只需遍历一遍数组，不用执行任何交换操作，时间复杂度为 $O(n)$ 。

在最坏情况下，冒泡排序要执行 $\frac{(n-1)n}{2}$ 次交换操作，时间复杂度为 $O(n^2)$ 。

冒泡排序的平均时间复杂度为 $O(n^2)$ 。

代码实现

C++

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
template <typename T> vector<T> &bubble_sort(vector<T> &a) {
  bool flag = true;
  while (flag) {
    flag = false;
    for (int i = 0; i < a.size() - 1; ++i) {
      if (a[i] > a[i + 1]) {
        flag = true;
        swap(a[i], a[i + 1]);
      }
    }
  }
  return a;
}
int main() {
  vector<int> test;
  for (size_t i = 0; i < 10; i += 1) {
    test.push_back(i);
  }
  for (size_t i = 0; i < test.size(); i++) {
    cout << test.at(i) << ' ';
  }
  cout << endl;
  reverse(test.begin(), test.end());
  for (size_t i = 0; i < test.size(); i++) {
    cout << test.at(i) << ' ';
  }
  cout << endl;
  bubble_sort(test);
  for (size_t i = 0; i < test.size(); i++) {
    cout << test.at(i) << ' ';
  }
  return 0;
}

③ 插入排序

插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴，但它的原理应该是最容易理解的了，因为只要打过扑克牌的人都应该能够秒懂。插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

插入排序和冒泡排序一样，也有一种优化算法，叫做拆半插入。

原理

将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。

从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）

稳定性

插入排序是一种稳定的排序算法。

时间复杂度

插入排序的最优时间复杂度为 $O(n)$ ，在数列几乎有序时效率很高。

插入排序的最坏时间复杂度和平均时间复杂度都为 $O(n^2)$ 。

代码实现

template <typename T> vector<T> &insertion_sort(vector<T> &a) {
  for (int i = 1; i < a.size(); ++i) {
    int key = a[i];
    int j = i - 1;
    while (j >= 0 && a[j] > key) { //因为数组中下标为 0 的也需要进行排序
      a[j + 1] = a[j];
      --j;
    }
    a[j + 1] = key;
  }
  return a;
}

④ 计数排序

还没有听过，第一次见到

时间复杂度

计数排序的时间复杂度为 $O(n+w)$ ，其中 $w$ 代表待排序数据的值域大小。

是一种线性时间的排序算法。

计数排序是一种稳定的排序算法。

工作原理

计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

计数排序不是比较排序，排序的速度快于任何比较排序算法。
由于用来计数的数组 C 的长度取决于待排序数组中数据的范围（等于待排序数组的最大值与最小值的差加上 1），这使得计数排序对于数据范围很大的数组，需要大量时间和内存。例如：计数排序是用来排序 0 到 100 之间的数字的最好的算法，但是它不适合按字母顺序排序人名。

通俗地理解，例如有 10 个年龄不同的人，统计出有 8 个人的年龄比 A 小，那 A 的年龄就排在第 9 位，用这个方法可以得到其他每个人的位置，也就排好了序。当然，年龄有重复时需要特殊处理（保证稳定性），这就是为什么最后要反向填充目标数组，以及将每个数字的统计减去 1 的原因。

代码实现

计数排序的工作原理是使用一个额外的数组 $C$ ，其中第 $i$ 个元素是待排序数组 $A$ 中值等于 $i$ 的元素的个数，然后根据数组 $C$ 来将 $A$ 中的元素排到正确的位置。

它的工作过程分为三个步骤：

1. 计算每个数出现了几次；
2. 求出每个数出现次数的 前缀和 (opens new window) ；
3. 利用出现次数的前缀和，从右至左计算每个数的排名。

算法的步骤如下：

• （1）找出待排序的数组中最大和最小的元素
• （2）统计数组中每个值为 i 的元素出现的次数，存入数组 C 的第 i 项
• （3）对所有的计数累加（从 C 中的第一个元素开始，每一项和前一项相加）
• （4）反向填充目标数组：将每个元素 i 放在新数组的第 C (i) 项，每放一个元素就将 C (i) 减去 1

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
template <typename T> vector<T> &count_sort(vector<T> &a) {
  vector<T> ans(a.size(),0);
  T min = a.at(0);
  T max = a.at(0);
  for (size_t i = 0; i < a.size(); i++) {
    min = (a.at(i) < min ? a.at(i) : min);
    max = (a.at(i) > max ? a.at(i) : max);
  } //使用三元运算符要加上括号
  T BetMaxMin = max-min +1;  //多开辟一小格
  vector<int> counter(BetMaxMin,0);
  for (size_t i = 0; i < a.size(); i++) 
    counter.at(a.at(i))++;
  // for (size_t i = 0; i < counter.size(); i++) 
  //   cout << counter.at(i) <<' ';
  // cout <<endl;
  for (size_t i = 1; i < counter.size(); i++) 
    counter.at(i) += counter.at(i-1);
  // for (size_t i = 0; i < counter.size(); i++) 
  //   cout << counter.at(i) << ' ';
  // cout << endl;
  for (int i = a.size()-1; i >= 0; i--) {
    counter[a[i]] = counter[a[i]] -1;
    ans[counter[a[i]]] = a[i];
  }
  a = ans;
  return a;
}
int main() {
  vector<int> test;
  for (size_t i = 0; i < 10; i += 2) {
    test.push_back(i);
  }
  for (size_t i = 0; i < test.size(); i++) {
    cout << test.at(i) << ' ';
  }
  cout << endl;
  reverse(test.begin(), test.end());
  for (size_t i = 0; i < test.size(); i++) {
    cout << test.at(i) << ' ';
  }
  cout << endl;
  count_sort(test);
  for (size_t i = 0; i < test.size(); i++) {
    cout << test.at(i) << ' ';
  }
  return 0;
}

0 2 4 6 8
8 6 4 2 0
1 0 1 0 1 0 1 0 1
1 1 2 2 3 3 4 4 5
0 2 4 6 8

⑤ 快速排序

快速排序（英语：Quicksort），又称分区交换排序（英语：partition-exchange sort），简称快排，是一种被广泛运用的排序算法。

快速排序是由东尼・霍尔所发展的一种排序算法。在平均状况下，排序 n 个项目要 Ο(nlogn) 次比较。在最坏状况下则需要 Ο(n2) 次比较，但这种状况并不常见。事实上，快速排序通常明显比其他 Ο(nlogn) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。

快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。

快速排序又是一种分而治之思想在排序算法上的典型应用。本质上来看，快速排序应该算是在冒泡排序基础上的递归分治法。

快速排序的名字起的是简单粗暴，因为一听到这个名字你就知道它存在的意义，就是快，而且效率高！它是处理大数据最快的排序算法之一了。虽然 Worst Case 的时间复杂度达到了 O (n²)，但是人家就是优秀，在大多数情况下都比平均时间复杂度为 O (n logn) 的排序算法表现要更好，可是这是为什么呢，我也不知道。

算法步骤

快速排序分为三个过程：

1. 将数列划分为两部分（要求保证相对大小关系）；
2. 递归到两个子序列中分别进行快速排序；
3. 不用合并，因为此时数列已经完全有序。

和归并排序不同，第一步并不是直接分成前后两个序列，而是在分的过程中要保证相对大小关系。具体来说，第一步要是要把数列分成两个部分，然后保证前一个子数列中的数都小于后一个子数列中的数。为了保证平均时间复杂度，一般是随机选择一个数 $m$ 来当做两个子数列的分界。

之后，维护一前一后两个指针 $p$ 和 $q$ ，依次考虑当前的数是否放在了应该放的位置（前还是后）。如果当前的数没放对，比如说如果后面的指针 $q$ 遇到了一个比 $m$ 小的数，那么可以交换 $p$ 和 $q$ 位置上的数，再把 $p$ 向后移一位。当前的数的位置全放对后，再移动指针继续处理，直到两个指针相遇。

其实，快速排序没有指定应如何具体实现第一步，不论是选择 $m$ 的过程还是划分的过程，都有不止一种实现方法。

第三步中的序列已经分别有序且第一个序列中的数都小于第二个数，所以直接拼接起来就好了。

实现 c

#include <stdio.h>
int a[101], n; //定义全局变量，这两个变量需要在子函数中使用
void quicksort(int left, int right) {
  int i, j, t, temp;
  if (left > right)
    return;
  temp = a[left]; // temp 中存的就是基准数
  i = left;
  j = right;  //定义两个指针
  while (i != j) {
    //顺序很重要，要先从右边开始找，找到第一个小于基准的值
    while (a[j] >= temp && i < j)
      j--;
    //再找左面的，找到大于当前基准的地方
    while (a[i] <= temp && i < j)
      i++;
    //交换两个数在数组中的位置
    if (i < j) {
      t = a[i];
      a[i] = a[j];
      a[j] = t;
    }
  }
  //最后循环停止的那个地方就是将大于基准和小于基准分开的地方
  //最终将基准数归位
  a[left] = a[i]; //重置 a[left] 的数值为边界值（因为先从右面开始找的，所以 a[i] 必然小于 a[left]）
  a[i] = temp;    //将 基准移动到他应该存在的地方
  quicksort(left, i - 1); //继续处理左边的，这里是一个递归的过程
  quicksort(i + 1, right); //继续处理右边的 ，这里是一个递归的过程
}
int main() {
  int i, j, t;
  //读入数据
  scanf("%d", &n);
  for (i = 1; i <= n; i++)
    scanf("%d", &a[i]);
  quicksort(1, n); //快速排序调用
  //输出排序后的结果
  for (i = 1; i <= n; i++)
    printf("%d ", a[i]);
  getchar();
  return 0;
}

实现（C++）

struct Range {
  int start, end;
  Range(int s = 0, int e = 0) { start = s, end = e; }
};
template <typename T>
void quick_sort(T arr[], const int len) {
  if (len <= 0) return;
  Range r[len];
  int p = 0;
  r[p++] = Range(0, len - 1);
  while (p) {
    Range range = r[--p];
    if (range.start >= range.end) continue;
    T mid = arr[range.end];
    int left = range.start, right = range.end - 1;
    while (left < right) {
      while (arr[left] < mid && left < right) left++;
      while (arr[right] >= mid && left < right) right--;
      std::swap(arr[left], arr[right]);
    }
    if (arr[left] >= arr[range.end])
      std::swap(arr[left], arr[range.end]);
    else
      left++;
    r[p++] = Range(range.start, left - 1);
    r[p++] = Range(left + 1, range.end);
  }
}

稳定性

快速排序是一种不稳定的排序算法。

时间复杂度

快速排序的最优时间复杂度和平均时间复杂度为 $O(n\log n)$ ，最坏时间复杂度为 $O(n^2)$ 。

朴素优化思想

如果仅按照上文所述的基本思想来实现快速排序（或者是直接照抄模板）的话，那大概率是通不过 P1177【模板】快速排序 (opens new window) 这道模板的。因为有毒瘤数据能够把朴素的快速排序卡成 $O(n^2)$ 。

所以，我们需要对朴素快速排序思想加以优化。较为常见的优化思路有以下三种。

• 通过 三数取中（即选取第一个、最后一个以及中间的元素中的中位数） 的方法来选择两个子序列的分界元素（即比较基准）。这样可以避免极端数据（如升序序列或降序序列）带来的退化；
• 当序列较短时，使用 插入排序 的效率更高；（当待排序序列的长度分割到一定大小后，使用插入排序）
• 每趟排序后， 将与分界元素相等的元素聚集在分界元素周围 （三路快速排序），这样可以避免极端数据（如序列中大部分元素都相等）带来的退化。

下面列举了几种较为成熟的快速排序优化方式。

三路快速排序

三路快速排序（英语：3-way Radix Quicksort）是快速排序和 基数排序 的混合。它的算法思想基于 荷兰国旗问题 (opens new window) 的解法。

与原始的快速排序不同，三路快速排序在随机选取分界点 $m$ 后，将待排数列划分为三个部分：小于 $m$ 、等于 $m$ 以及大于 $m$ 。这样做即实现了将与分界元素相等的元素聚集在分界元素周围这一效果。

三路快速排序在处理含有多个重复值的数组时，效率远高于原始快速排序。其最佳时间复杂度为 $O(n)$ 。

三路快速排序实现起来非常简单。下面给出了一种三路快排的 C++ 实现，其表现在模板题中并不输给 STL 的 sort。

// 模板的 T 参数表示元素的类型，此类型需要定义小于（<）运算
template <typename T>
// arr 为需要被排序的数组，len 为数组长度
void quick_sort(T arr[], const int len) {
  if (len <= 1) return;
  // 随机选择基准（pivot）
  const T pivot = arr[rand() % len];
  // i：当前操作的元素
  // j：第一个等于 pivot 的元素
  // k：第一个大于 pivot 的元素
  int i = 0, j = 0, k = len;
  // 完成一趟三路快排，将序列分为：小于 pivot 的元素 ｜ 等于 pivot 的元素 ｜
  // 大于 pivot 的元素
  while (i < k) {
    if (arr[i] < pivot)
      swap(arr[i++], arr[j++]);
    else if (pivot < arr[i])
      swap(arr[i], arr[--k]);
    else
      i++;
  }
  // 递归完成对于两个子序列的快速排序
  quick_sort(arr, j);
  quick_sort(arr + k, len - k);
}

内省排序

内省排序（英语：Introsort 或 Introspective sort）是快速排序和 堆排序 的结合，由 David Musser 于 1997 年发明。内省排序其实是对快速排序的一种优化，保证了最差时间复杂度为 $O(n\log n)$ 。

内省排序将快速排序的最大递归深度限制为 $\lfloor \log_2n \rfloor$ ，超过限制时就转换为堆排序。这样既保留了快速排序内存访问的局部性，又可以防止快速排序在某些情况下性能退化为 $O(n^2)$ 。

从 2000 年 6 月起，SGI C++ STL 的 stl_algo.h 中 sort() 函数的实现采用了内省排序算法。

线性找第 k 大的数

在下面的代码示例中，第 $k$ 大的数被定义为序列排成升序时，第 $k$ 个位置上的数（编号从 0 开始）。

找第 $k$ 大的数（K-th order statistic），最简单的方法是先排序，然后直接找到第 $k$ 大的位置的元素。这样做的时间复杂度是 $O(n\log n)$ ，对于这个问题来说很不划算。

我们可以借助快速排序的思想解决这个问题。考虑快速排序的划分过程，在快速排序的「划分」结束后，数列 $A_{p} \cdots A_{r}$ 被分成了 $A_{p} \cdots A_{q}$ 和 $A_{q+1} \cdots A_{r}$ ，此时可以按照左边元素的个数（ $q - p + 1$ ）和 $k$ 的大小关系来判断是只在左边还是只在右边递归地求解。

可以证明，在期望意义下，程序的时间复杂度为 $O(n)$ 。

实现（C++）

// 模板的 T 参数表示元素的类型，此类型需要定义小于（<）运算
template <typename T>
// arr 为查找范围数组，rk 为需要查找的排名（从 0 开始），len 为数组长度
T find_kth_element(T arr[], int rk, const int len) {
  if (len <= 1) return arr[0];
  // 随机选择基准（pivot）
  const T pivot = arr[rand() % len];
  // i：当前操作的元素
  // j：第一个等于 pivot 的元素
  // k：第一个大于 pivot 的元素
  int i = 0, j = 0, k = len;
  // 完成一趟三路快排，将序列分为：小于 pivot 的元素 ｜ 等于 pivot 的元素 ｜
  // 大于 pivot 的元素
  while (i < k) {
    if (arr[i] < pivot)
      swap(arr[i++], arr[j++]);
    else if (pivot < arr[i])
      swap(arr[i], arr[--k]);
    else
      i++;
  }
  // 根据要找的排名与两条分界线的位置，去不同的区间递归查找第 k 大的数
  // 如果小于 pivot 的元素个数比 k 多，则第 k 大的元素一定是一个小于 pivot 的元素
  if (rk < j) return find_kth_element(arr, rk, j);
  // 否则，如果小于 pivot 和等于 pivot 的元素加起来也没有 k 多，则第 k 大的元素一定是一个大于 pivot 的元素
  else if (rk >= k)
    return find_kth_element(arr + k, rk - k, len - k);
  // 否则，pivot 就是第 k 大的元素
  return pivot;
}

⑦ 希尔排序

TODO
希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

• 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；
• 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位；
  希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录 "基本有序" 时，再对全体记录进行依次直接插入排序。

希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录 "基本有序" 时，再对全体记录进行依次直接插入排序。

算法步骤

排序对不相邻的记录进行比较和移动：

1. 将待排序序列分为若干子序列（每个子序列的元素在原始数组中间距相同）；
2. 对这些子序列进行插入排序；
3. 减小每个子序列中元素之间的间距，重复上述过程直至间距减少为 1。

稳定性

希尔排序是一种不稳定的排序算法。

时间复杂度

希尔排序的最优时间复杂度为 $O(n)$ 。

希尔排序的平均时间复杂度和最坏时间复杂度与间距序列的选取（就是间距如何减小到 1）有关，比如「间距每次除以 3」的希尔排序的时间复杂度是 $O(n^{3/2})$ 。已知最好的最坏时间复杂度为 $O(n \log^2n)$ 。

空间复杂度

希尔排序的空间复杂度为 $O(n)$ 。

实现 C++

template <typename T>
void shell_sort(T array[], int length) {
  int h = 1;
  while (h < length / 3) {
    h = 3 * h + 1;
  }
  while (h >= 1) {
    for (int i = h; i < length; i++) {
      for (int j = i; j >= h && array[j] < array[j - h]; j -= h) {
        std::swap(array[j], array[j - h]);
      }
    }
    h = h / 3;
  }
}

⑧ 归并排序

归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

作为一种典型的分而治之思想的算法应用，归并排序的实现由两种方法：

• 自上而下的递归（所有递归的方法都可以用迭代重写，所以就有了第 2 种方法）；
• 自下而上的迭代；

和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是 O (nlogn) 的时间复杂度。代价是需要额外的内存空间。

工作原理

归并排序分为三个步骤：

1. 将数列划分为两部分；
2. 递归地分别对两个子序列进行归并排序；
3. 合并两个子序列。

不难发现，归并排序的前两步都很好实现，关键是如何合并两个子序列。注意到两个子序列在第二步中已经保证了都是有序的了，第三步中实际上是想要把两个 有序 的序列合并起来。

性质

归并排序是一种稳定的排序算法。

归并排序的最优时间复杂度、平均时间复杂度和最坏时间复杂度均为 $O(n\log n)$ 。

归并排序的空间复杂度为 $O(n)$ 。

算法步骤

• 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；（开辟一个即可）
• 设定两个指针，最初位置分别为两个已经排序序列的起始位置；
• 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
• 重复步骤 3 直到某一指针达到序列尾；
• 将另一序列剩下的所有元素直接复制到合并序列尾

C++

TODO

void merge(int ll, int rr) {
  // 用来把 a[ll.. rr - 1] 这一区间的数排序。 t 数组是临时存放有序的版本用的。
  if (rr - ll <= 1) return;
  int mid = ll + (rr - ll >> 1);
  merge(ll, mid);
  merge(mid, rr);
  int p = ll, q = mid, s = ll;
  while (s < rr) {
    if (p >= mid || (q < rr && a[p] > a[q])) {
      t[s++] = a[q++];
      // ans += mid - p;
    } else
      t[s++] = a[p++];
  }
  for (int i = ll; i < rr; ++i) a[i] = t[i];
}
//关键点在于一次性创建数组，避免在每次递归调用时创建，以避免对象的无谓构造和析构。

迭代和递归

TODO
迭代版

template<typename T> // 整數或浮點數皆可使用，若要使用物件 (class) 時必須設定"小於"(<) 的運算子功能
void merge_sort(T arr[], int len) {
    T *a = arr;
    T *b = new T[len];
    for (int seg = 1; seg < len; seg += seg) {
        for (int start = 0; start < len; start += seg + seg) {
            int low = start, mid = min(start + seg, len), high = min(start + seg + seg, len);
            int k = low;
            int start1 = low, end1 = mid;
            int start2 = mid, end2 = high;
            while (start1 < end1 && start2 < end2)
                b[k++] = a[start1] < a[start2] ? a[start1++] : a[start2++];
            while (start1 < end1)
                b[k++] = a[start1++];
            while (start2 < end2)
                b[k++] = a[start2++];
        }
        T *temp = a;
        a = b;
        b = temp;
    }
    if (a != arr) {
        for (int i = 0; i < len; i++)
            b[i] = a[i];
        b = a;
    }
    delete[] b;
}

递归版

void Merge(vector<int> &Array, int front, int mid, int end) {
    // preconditions:
    // Array[front...mid] is sorted
    // Array[mid+1 ... end] is sorted
    // Copy Array[front ... mid] to LeftSubArray
    // Copy Array[mid+1 ... end] to RightSubArray
    vector<int> LeftSubArray(Array.begin() + front, Array.begin() + mid + 1);
    vector<int> RightSubArray(Array.begin() + mid + 1, Array.begin() + end + 1);
    int idxLeft = 0, idxRight = 0;
    LeftSubArray.insert(LeftSubArray.end(), numeric_limits<int>::max());
    RightSubArray.insert(RightSubArray.end(), numeric_limits<int>::max());
    // Pick min of LeftSubArray[idxLeft] and RightSubArray[idxRight], and put into Array[i]
    for (int i = front; i <= end; i++) {
        if (LeftSubArray[idxLeft] < RightSubArray[idxRight]) {
            Array[i] = LeftSubArray[idxLeft];
            idxLeft++;
        } else {
            Array[i] = RightSubArray[idxRight];
            idxRight++;
        }
    }
}
void MergeSort(vector<int> &Array, int front, int end) {
    if (front >= end)
        return;
    int mid = (front + end) / 2;
    MergeSort(Array, front, mid);
    MergeSort(Array, mid + 1, end);
    Merge(Array, front, mid, end);
}

⑨ 堆排序

https://www.cnblogs.com/chengxiao/p/6129630.html

堆排序（英语：Heapsort）是指利用 堆 这种数据结构所设计的一种排序算法。堆排序的适用数据结构为数组。

堆排序的基本思想是：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素（最底层的最右节点）进行交换，此时末尾就为最大值。然后将剩余 n-1 个元素重新构造成一个堆，这样会得到 n 个元素的次小值。如此反复执行，便能得到一个有序序列了

反复进行交换、重建、交换

稳定性

堆排序是一种不稳定的排序算法。

时间复杂度

堆排序的最优时间复杂度、平均时间复杂度、最坏时间复杂度均为 $O(n\log n)$ 。

TODO

C++

void max_heapify(int arr[], int start, int end) {
  // 建立父结点指标和子结点指标
  int dad = start;
  int son = dad * 2 + 1;
  while (son <= end) {  // 子结点指标在范围内才做比较
    if (son + 1 <= end &&
        arr[son] < arr[son + 1])  // 先比较两个子结点大小，选择最大的
      son++;
    if (arr[dad] >
        arr[son])  // 如果父结点比子结点大，代表调整完毕，直接跳出函数
      return;
    else {  // 否则交换父子内容，子结点再和孙结点比较
      swap(arr[dad], arr[son]);
      dad = son;
      son = dad * 2 + 1;
    }
  }
}
void heap_sort(int arr[], int len) {
  // 初始化，i 从最后一个父结点开始调整
  for (int i = len / 2 - 1; i >= 0; i--) max_heapify(arr, i, len - 1);
  // 先将第一个元素和已经排好的元素前一位做交换，再重新调整（刚调整的元素之前的元素），直到排序完毕
  for (int i = len - 1; i > 0; i--) {
    swap(arr[0], arr[i]);
    max_heapify(arr, 0, i - 1);
  }
}

桶排序

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效，我们需要做到这两点：

• 在额外空间充足的情况下，尽量增大桶的数量
• 使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中

桶排序按下列步骤进行：

设置一个定量的数组当作空桶；
遍历序列，并将元素一个个放到对应的桶中；
对每个不是空的桶进行排序；
从不是空的桶里把元素再放回原来的序列中。

同时，对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要。

元素分布在桶中：

然后，元素在每个桶中排序：

• 什么时候最快：当输入的数据可以均匀的分配到每一个桶中。
• 什么时候最慢：当输入的数据被分配到了同一个桶中。

稳定性

如果使用稳定的内层排序，并且将元素插入桶中时不改变元素间的相对顺序，那么桶排序就是一种稳定的排序算法。
由于每块元素不多，一般使用插入排序。此时桶排序是一种稳定的排序算法。

实现 C++

const int N = 100010;
int n, w, a[N];
vector<int> bucket[N];
void insertion_sort(vector<int>& A) {
  for (int i = 1; i < A.size(); ++i) {
    int key = A[i];
    int j = i - 1;
    while (j >= 0 && A[j] > key) {
      A[j + 1] = A[j];
      --j;
    }
    A[j + 1] = key;
  }
}
void bucket_sort() {
  int bucket_size = w / n + 1;
  for (int i = 0; i < n; ++i) {
    bucket[i].clear();
  }
  for (int i = 1; i <= n; ++i) {
    bucket[a[i] / bucket_size].push_back(a[i]);
  }
  int p = 0;
  for (int i = 0; i < n; ++i) {
    insertion_sort(bucket[i]);
    for (int j = 0; j < bucket[i].size(); ++j) {
      a[++p] = bucket[i][j];
    }
  }
}

⑩ 基数排序

基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。

基数排序 vs 计数排序 vs 桶排序

基数排序有两种方法：

这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：

• 基数排序：根据键值的每位数字来分配桶；
• 计数排序：每个桶只存储单一键值；
• 桶排序：每个桶存储一定范围的数值；

C++

int maxbit(int data[], int n) //辅助函数，求数据的最大位数
{
    int maxData = data[0];              ///< 最大数
    /// 先求出最大数，再求其位数，这样有原先依次每个数判断其位数，稍微优化点。
    for (int i = 1; i < n; ++i)
    {
        if (maxData < data[i])
            maxData = data[i];
    }
    int d = 1;
    int p = 10;
    while (maxData >= p)
    {
        //p *= 10; // Maybe overflow
        maxData /= 10;
        ++d;
    }
    return d;
/*    int d = 1; //保存最大的位数
    int p = 10;
    for(int i = 0; i < n; ++i)
    {
        while(data[i] >= p)
        {
            p *= 10;
            ++d;
        }
    }
    return d;*/
}
void radixsort(int data[], int n) //基数排序
{
    int d = maxbit(data, n);
    int *tmp = new int[n];
    int *count = new int[10]; //计数器
    int i, j, k;
    int radix = 1;
    for(i = 1; i <= d; i++) //进行 d 次排序
    {
        for(j = 0; j < 10; j++)
            count[j] = 0; //每次分配前清空计数器
        for(j = 0; j < n; j++)
        {
            k = (data[j] / radix) % 10; //统计每个桶中的记录数
            count[k]++;
        }
        for(j = 1; j < 10; j++)
            count[j] = count[j - 1] + count[j]; //将 tmp 中的位置依次分配给每个桶
        for(j = n - 1; j >= 0; j--) //将所有桶中记录依次收集到 tmp 中
        {
            k = (data[j] / radix) % 10;
            tmp[count[k] - 1] = data[j];
            count[k]--;
        }
        for(j = 0; j < n; j++) //将临时数组的内容复制到 data 中
            data[j] = tmp[j];
        radix = radix * 10;
    }
    delete []tmp;
    delete []count;
}

TODO 重构相关算法

const int N = 100010;
const int W = 100010;
const int K = 100;
int n, w[K], k, cnt[W];
struct Element {
  int key[K];
  bool operator<(const Element& y) const {
    // 两个元素的比较流程
    for (int i = 1; i <= k; ++i) {
      if (key[i] == y.key[i]) continue;
      return key[i] < y.key[i];
    }
    return false;
  }
} a[N], b[N];
void counting_sort(int p) {
  memset(cnt, 0, sizeof(cnt));
  for (int i = 1; i <= n; ++i) ++cnt[a[i].key[p]];
  for (int i = 1; i <= w[p]; ++i) cnt[i] += cnt[i - 1];
  // 为保证排序的稳定性，此处循环 i 应从 n 到 1
  // 即当两元素关键字的值相同时，原先排在后面的元素在排序后仍应排在后面
  for (int i = n; i >= 1; --i) b[cnt[a[i].key[p]]--] = a[i];
  memcpy(a, b, sizeof(a));
}
void radix_sort() {
  for (int i = k; i >= 1; --i) {
    //借助计数排序完成对关键字的排序
    counting_sort(i);
  }
}

锦标赛排序