排序
排序算法 (Sort Algorithm)
排序本质上是试图将一个向量中的数据（数字、字母或者其他内容）按照一定规则排列。而排序的规则是可以人为设定的。比如小学经常做的，按照数字大小、首字母顺序排序等等。
对于什么样的排序是好的？我们应当有一套标准。很直接的两个评价维度是：
- 时间上：快速、操作少的；特别是数据量大时；
- 空间上：不借助额外空间的、就地操作。
另外，我们考虑下面一种情况。对于一张记录姓名和年龄的表而言：
#(name, age)
('A', 19)
('B', 18)
('C', 21)
('D', 19)
('E', 23)如果输入数据是按照姓名排序好的，我们在排序年龄时调换了相同数字的位置，就会导致输入数据的有序性丧失。
于是，我们还应当追求稳定性。
同时，一个好的排序还应当根据输入数据已有顺序自适应的调整自身，减小计算量，其最佳时间复杂度通常优于平均时间复杂度。
显然，迄今为止尚未发现兼具以上所有特性的排序算法。
基于比较运算符的排序理论最优时间复杂度为 ，而不使用的排序最优可达 ，但通用性较差。
选择排序 (Selection Sort)
这个算法的原理非常简单。写一个循环，从未排序区间里选择一个最小的放到最前面。
对于一个长度为 n 的数组 Array，算法流程：
从[0, n-1]中选择最小的和 Array[0] 交换，前 1 个数据已排序；
从[1, n-1]中选择最小的和 Array[1] 交换，前 2 个数据已排序…
从[n-2, n-1]中选择最小的和 Array[n-2] 交换，前 n-1 个数据已排序；
仅剩的一个必是最大元素。
用 C++ 语言实现的版本：
/* 选择排序 */
void selectionSort(vector<int> &nums) {
int n = nums.size();
// 外循环：未排序区间为 [i, n-1)
for (int i = 0; i < n - 1; i++) {
// 内循环：找到未排序区间内的最小元素
int k = i;
for (int j = i + 1; j < n; j++) {
if (nums[j] < nums[k])
k = j; // 记录最小元素的索引
}
// 将该最小元素与未排序区间的首个元素交换
swap(nums[i], nums[k]);
}
}时间复杂度 ，空间复杂度 。不具备稳定性和自适应性。
冒泡排序 (Bubble Sort)
这个算法非常的著名也很有意思。与选择排序不同，选择是将未排序区间的最小的通过和基准逐一比较挑出来放到前头。而冒泡是将未排序区间的数据通过相邻比较将最大的气泡冒到最上面。
对于一个长度为 n 的数组 Array，算法流程：
对 [0, n-1] 执行冒泡，将数组的最大元素交换至正确位置；
对 [0, n-2] 执行冒泡，将数组的第二大元素交换至正确位置…
对 [0, 1] 执行冒泡，将数组的第 n-1 大元素交换至正确位置；
这样执行 n-1 轮后，剩下的必然是最小的。
用 C++ 语言实现的版本：
/* 冒泡排序 */
void bubbleSort(vector<int> &nums) {
// 外循环：未排序区间为 [0, i]
for (int i = nums.size() - 1; i > 0; i--) {
// 内循环：将未排序区间 [0, i] 中的最大元素交换至该区间的最右端
for (int j = 0; j < i; j++) {
if (nums[j] > nums[j + 1]) {
swap(nums[j], nums[j + 1]);
}
}
}
}时间复杂度 ，空间复杂度 ，具备稳定性和自适应性。
也就是说，如果我们发现某轮冒泡中没有发生交换，也就意味着排序已完成，直接退出即可，可达最佳时间复杂度 。这就是自适应性的体现。
void newbubbleSort(vector<int> &nums) {
for (int i = nums.size() - 1; i > 0; i--) {
bool flag = False; // 引入一个标志位
for (int j = 0; j < i; j++) {
if (nums[j] > nums[j + 1]) {
swap(nums[j], nums[j + 1]);
flag = true;
}
}
if (!flag) {
break; // --------此轮冒泡未交换元素
}
}
}插入排序 (Insertion Sort)
我们在未排序区间选择基准元素，将该元素插入到已排序区间的正确位置。
对于一个长度为 n 的数组 Array，算法流程：
[0] 已排序，选择 [1] 作为 base 和 [0] 比大小，插入到正确位置；
[0, 1] 已排序，选择 [2] 作为 base 和 [0, 1] 比大小，插入到正确位置…
[0, n-2] 已排序，选择 [n-1] 作为 base 和 [0, n-2] 比大小，插入到正确位置。
用 C++ 语言实现的版本：
/* 插入排序 */
void insertionSort(vector<int> &nums) {
// 外循环：已排序区间为 [0, i-1]
for (int i = 1; i < nums.size(); i++) {
int base = nums[i], j = i - 1;
// 内循环：将 base 插入到已排序区间 [0, i-1] 中的正确位置
while (j >= 0 && nums[j] > base) {
nums[j + 1] = nums[j]; // 将 nums[j] 向右移动一位
j--;
}
nums[j + 1] = base; // 将 base 赋值到正确位置
}
}时间复杂度 ，空间复杂度 。当数据自然有序时，由于不会进 while，达到最佳时间复杂度 。具有稳定性。
实际情况中，插入排序的使用频率显著高于冒泡排序和选择排序，主要有以下原因：
冒泡排序基于元素交换实现，需要借助一个临时变量，共涉及 3 个单元操作；插入排序基于元素赋值实现，仅需 1 个单元操作。
如果给定一组部分有序的数据，插入排序通常比选择排序效率更高。选择排序不稳定。
快速排序 (Quick Sort)
我们前面了解的三种算法的平均时间都为 ，下面我们来看一种快速排序的方法，这是一种分治策略，也就是递归，实质是将一个较长数组的排序问题简化为两个较短数组的排序问题。
那么算法递归执行了一个怎样的操作呢？我们将其称为一个“划分”。
选取数组最左端元素作为基准数，初始化两个指针 i 和 j 分别指向数组的两端。
设置一个循环，在每轮中使用 i（j）分别寻找第一个比基准数大（小）的元素，然后交换这两个元素。注意是 j 先从右往左查找，i 再从左往右查找，顺序不能交换。
循环执行上述步骤，直到 i 和 j 相遇时停止，最后将基准数交换至两个子数组的分界线。
这样一个划分下来，我们就将整个数组分为：左数组、基准数和右数组。显然满足：左数组的任意元素 <= 基准数 <= 右数组。
/* 划分 */
int partition(vector<int> &nums, int left, int right) {
// 以 nums[left] 为基准数
int i = left, j = right;
while (i < j) {
while (i < j && nums[j] >= nums[left])
j--; // 从右向左找首个小于基准数的元素
while (i < j && nums[i] <= nums[left])
i++; // 从左向右找首个大于基准数的元素
swap(nums[i], nums[j]); // 交换这两个元素
}
swap(nums[i], nums[left]); // 将基准数交换至两子数组的分界线
return i; // 返回基准数的索引
}
/* 快速排序 */
void quickSort(vector<int> &nums, int left, int right) {
// 子数组长度为 1 时终止递归
if (left >= right)
return;
// 哨兵划分
int pivot = partition(nums, left, right);
// 递归左子数组、右子数组
quickSort(nums, left, pivot - 1);
quickSort(nums, pivot + 1, right);
}
时间复杂度 ，空间复杂度 。我们来分析一下：
首先，每一层划分的总工作量是 ，无论 pivot 选的好坏，实际上都需要扫描整个数组；
其次，对于好的 pivot 比如把数组分为两半，递归时第一次长度为 ，第二次为 ，第三次为 ，树高为 ；
最后，在极端情况下，如数组完全倒序，递归深度可达 n，占用 的栈帧空间，此时最差时间复杂度为 .
因此，我们可以对其进行基准数选取或递归深度的优化。