冒泡排序（Bubble Sort）
它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序（如从大到小、首字母从Z到A）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成。
排序过程描述：
- 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
- 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
- 针对所有的元素重复以上的步骤，除了最后一个。
- 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
- 稳定性： 它是指对同样的数据排序，会不会改变它的相对位置。比如
[1, 3, 2, 4, 2]经过排序后，两个相同的元素2位置会不会被交换。冒泡排序是比较相邻两个元素的大小，显然不会破坏稳定性。 - 空间复杂度： 由于整个排序过程是在原数据上进行操作，故为
O(1)。 - 平均时间复杂度： 由于嵌套了
2层循环，故为O(n^2)。最好为O(n)。
两个优化点：
- 如果一趟比较下来，没有任何一对相邻元素发生过交换，则表明当前的元素列已经是有序的了。
- 记录一趟排序下来最后发生交换时相邻元素的最低下标，且它后面的数据都是已经有序的了，下趟排序可把后面的有序的都忽略掉。
代码实现：
void bubbleSort(int nums[], int count) {
if (nums == nullptr || count <= 0) {
return;
}
int k = count - 1; // 第二层循环的边界
for (int i = 0; i < count - 1; ++i) { // 边界是 < count - 1 是因为和其它排序方式比，
// 它是每次把最大或者最小值放在序列的最右侧了，比如插入和选择排序则是把最小或者最大值放在序列的最左侧
bool noExchange = true; // 标记一趟比较操作下来是否发生过交换，如果没有的话表示当前序列已经有序
int n = 0; // 记录一趟排序中最后一次交换的两个相邻元素的最小下标，此后该最小下标以后的数据就都是有序的
for (int j = 0; j < k; ++j) {
if (nums[j] > nums[j + 1]) {
swap(&nums[j], &nums[j + 1]);
noExchange = false;
n = j;
}
}
if (noExchange) {
break;
}
k = n; // 更新 k 值
}
}
选择排序（Selection sort）
首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
- 稳定性： 不稳定，例如
[2, 2, 1]第一趟下来，第一个2就被交换到1的位置了，两个2相对位置发生了改变。 - 空间复杂度： 由于整个排序过程是在原数据上进行操作，故为
O(1)。 - 时间复杂度：
O(n^2)。
代码实现：
void selectionSort(int nums[], int count) {
if (nums == nullptr || count <= 0) {
return;
}
for (int i = 0; i < count; ++i) {
int minIndex = i; // 用于记录一趟下来找到的最小元素的下标，默认 i 位置是最小元素
for (int j = i + 1; j < count; ++j) {
if (nums[j] < nums[minIndex]) {
minIndex = j; // 发现更小的元素，更新 minIndex
}
}
swap(&nums[i], &nums[minIndex]); // 一趟循环下来把最小的元素放在数列的头部
}
}
插入排序（Insertion Sort）
把原数组在逻辑上分两个组，左边是已排序序列，右边是待排序序列，每次从右边序列取第一个值插入左边序列中，并保持左边序列有序，i 从 1 开始，0 下标元素定为左侧已排序序列的第一个元素。在其实现过程使用双层循环，外层循环对除了第一个元素之外的所有元素，内层循环对当前元素前面有序表进行待插入位置查找，并进行移动。
排序过程描述：
- 从第一个元素开始，该元素可以认为已经被排序。
- 取出下一个元素，在已经排序的元素序列中从后向前扫描。
- 如果该元素（已排序）大于新元素，将该元素移到下一位置。
- 重复步骤 3，直到找到已排序的元素小于或者等于新元素的位置。
- 将新元素插入到该位置。
- 持续把剩余元素插入左侧有序序列中。
- 稳定性： 由于待插入的元素遇到第一个小于或者等于自己的元素便不再进行查找交换，故稳定。
- 空间复杂度： 由于整个排序过程是在原数据上进行操作，故为
O(1)。 - 平均时间复杂度： 由于嵌套了
2层循环，故为O(n^2)。最好为O(n)。
代码实现：
void insertionSort(int nums[], int count) {
if (nums == nullptr || count <= 0) {
return;
}
for (int i = 1; i < count; ++i) { // i 从 1 开始
for (int j = i; j > 0 && nums[j - 1] > nums[j]; --j) {
swap(&nums[j - 1], &nums[j]);
}
}
}
希尔排序（Shell's Sort）
希尔排序（Shell's Sort）是插入排序的一种又称 “缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。该方法因 D.L.Shell 于 1959 年提出而得名。希尔排序是把数据按下标的一定增量分组，对每组使用直接插入排序算法排序，随着增量逐渐减少，每组包含的元素越来越多，当增量减至 1 时，整个数据恰被分成一组，算法便终止。
希尔排序是基于插入排序的以下两点性质而提出改进方法的：
- 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率。
- 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位。
- 稳定性： 不稳定。例如相同元素被分到不同组时，它们最终的相对位置可能会被改变。
- 空间复杂度： 由于整个排序过程是在原数据上进行操作，故为
O(1)。 - 时间复杂度： 希尔排序的时间复杂度与增量序列的选取有关，例如希尔增量时间复杂度为
O(n^2)，而Hibbard增量的希尔排序的时间复杂度为O(log n的3/2)，希尔排序时间复杂度的下界是n*logn。
代码实现：
void shellSort(int nums[], int count) {
if (nums == nullptr || count <= 0) {
return;
}
// for (int gap = count / 2; gap > 0; gap /= 2) {
// for (int i = 0; i < gap; ++i) {
// for (int j = i + gap; j < count; j += gap) {
// for (int k = j - gap; k >= 0 && nums[k] > nums[k + gap]; k -= gap) {
// swap(&nums[k], &nums[k + gap]);
// }
// }
// }
// }
for (int gap = count / 2; gap > 0; gap /= 2) {
for (int i = gap; i < count; ++i) {
for (int j = i - gap; j >= 0 && nums[j] > nums[j + gap]; j -= gap) { // j 是左边元素
swap(&nums[j], &nums[j + gap]);
}
}
}
}
快速排序（Quick Sort）
通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行。快速排序又是一种分而治之思想在排序算法上的典型应用。本质上来看，快速排序应该算是在冒泡排序基础上的递归分治法。
排序过程描述：
- 首先设定一个分界值，通过该分界值将数组分成左右两部分。
- 将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。
- 然后，左边和右边的数据可以独立排序。
- 重复上述过程，可以看出，这是一个递归定义。
- 通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。
- 当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。
- 稳定性： 不稳定。例如
[5, 2, 2]从5开始挖坑，从右边开始，最后一个2放到了第一个2的前面。 - 空间复杂度： 从空间性能上看，尽管快速排序只需要 一个元素的辅助空间。但快速排序 需要一个栈空间来实现递归。最好的情况下，即快速排序的每一趟排序都将元素序列均匀地分割成长度相近的两个子表，所需栈的最大深度为
log2(n+1)，但最坏的情况下，栈的最大深度为n，这样，快速排序的空间复杂度为O(logn)。 - 时间复杂度： 快速排序的一次划分算法从两头交替搜索，直到
low和hight重合，因此其时间复杂度是O(n)，而整个快速排序算法的时间复杂度与 划分的趟数 有关。理想的情况是，每次划分所选择的中间数恰好将当前序列 几乎等分，经过logn趟划分，便可得到长度为1的子表。这样，整个算法的时间复杂度为O(n*logn)。最坏的情况是，每次所选的中间数是当前序列中的最大或最小元素，这使得每次划分所得的子表中一个为空表，另一子表的长度为原表的长度 -1。这样，长度为n的数据表的快速排序需要经过n趟划分，使得整个排序算法的时间复杂度为O(n^2)。平均时间复杂度也是O(n*logn)。事实上，快速排序通常明显比其它Ο(n*logn)算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。
代码实现: (挖坑+分治法)
void quickSort(int nums[], int l, int r) {
if (l >= r) {
return;
}
int i = l, j = r, x = nums[l];
while (i < j) {
while (i < j && nums[j] >= x) { // 从右找到第一个小于 x 的值
--j;
}
if (i < j) {
nums[i++] = nums[j];
}
while (i < j && nums[i] < x) { // 从左找到第一个大于等于 x 的值
++i;
}
if (i < j) {
nums[j--] = nums[i];
}
}
nums[i] = x;
quickSort(nums, l, i - 1);
quickSort(nums, i + 1, r);
}
归并排序（Merge Sort）
归并排序（Merge Sort）是建立在归并操作上的一种有效，稳定的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将 已有序的子序列 合并，得到完全有序的序列, 即先使每个子序列有序，再使子序列段间有序。一般用于对总体无序，但是各子项相对有序的数列。
- 稳定性： 稳定。
- 空间复杂度： 申请空间用来临时存放合并后的序列，使其大小为两个已经排序序列之和（原序列
n即可）。故为O(n)。归并排序的比较次数小于快速排序的比较次数，移动次数一般多于快速排序的移动次数。 - 时间复杂度： 设数列长为
n，将数列分开成小数列一共要logn步，每步都是一个合并有序数列的过程，时间复杂度可以记为O(n)，故一共为O(n*logn)。因为归并排序每次都是在相邻的数据中进行操作，所以归并排序在O(n*logn)的几种排序方法（快速排序，归并排序，希尔排序，堆排序）也是效率比较高的。
代码实现：
// 将有两个有序数列 a[first...mid] 和 a[mid...last] 合并
void mergeSort(int nums[], int first, int last, int temp[]) {
if (first >= last) {
return;
}
int mid = ((last - first) >> 1 ) + first; // 右移一位等于除以 2，可防止 (first + last) / 2 中求和溢出
mergeSort(nums, first, mid, temp); // 递归拆 [first...mid] 的数据
mergeSort(nums, mid + 1, last, temp); // 递归拆 [mid + 1...last] 的数据
mergeArray(nums, first, mid, last, temp); // 递归结束开始合并
}
void mergeArray(int nums[], int first, int mid, int last, int temp[]) {
if (nums[mid] <= nums[mid + 1]) {
return;
}
// 两个有序序列 nums[first...mid] nums[mid+1...last] 合并
int i = first, j = mid + 1; // i 和 j 表示各从两个数列的最左侧开始
int m = mid, n = last; // m 和 n 表示两个数列的最右侧边界
int k = 0; // k 用于记录两个数列的数据总个数
while (i <= m && j <= n) {
if (nums[i] <= nums[j]) {
temp[k++] = nums[i++]; // 把 nums[first...mid] 中较小元素放在 temp 中
} else {
temp[k++] = nums[j++]; // 把 nums[mid+1...last] 中较小元素放在 temp 中
}
}
while (i <= m) { // 把 nums[first...mid] 中剩余的元素放在 temp 中
temp[k++] = nums[i++];
}
while (j <= n) { // 把 nums[mid+1...last] 中剩余的元素放在 temp 中
temp[k++] = nums[j++];
}
for (i = 0; i < k; ++i) { // temp 中是按顺序合并好的元素，然后放回到 nums 中
nums[first + i] = temp[i];
}
}
堆排序（Heap Sort）
堆排序和快速排序、归并排序一样都是时间复杂度为 O(n*logn) 的几种常见排序方法。
二叉堆的定义
二叉堆是完全二叉树或者是近似完全二叉树。二叉堆满足二个特性：
- 父结点的键值总是大于或等于（小于或等于）任何一个子节点的键值。
- 每个结点的左子树和右子树都是一个二叉堆（都是最大堆或最小堆）。
当父结点的键值总是大于或等于任何一个子节点的键值时为最大堆。当父结点的键值总是小于或等于任何一个子节点的键值时为最小堆。由于其它几种堆（二项式堆，斐波纳契堆等）用的较少，一般将二叉堆就简称为堆。
堆的存储
一般都用数组来表示堆，i 结点的父结点下标就为 (i – 1) / 2。它的左右子结点下标分别为 2 * i + 1 和 2 * i + 2。如第 0 个结点左右子结点下标分别为 1 和 2。
堆的插入
每次插入都是将新数据放在数组最后。 可以发现从这个新数据的父结点到根结点必然为一个有序的数列，现在的任务是将这个新数据插入到这个有序数据中—这就类似于插入排序中将一个数据并入到有序区间中，需要为这个新数据找到一个合适的位置。
// 插入时:
// 在最小堆中加入新的数据 nNum
void MinHeapAddNumber(int a[], int n, int nNum) {
a[n] = nNum;
MinHeapFixup(a, n); // 调整 nNum 到合适的位置
}
// 新加入 i 结点，其父结点为 (i - 1) / 2
void MinHeapFixup(int a[], int i) {
int j, temp;
temp = a[i];
j = (i - 1) / 2; // 父结点的下标
while (j >= 0 && i != 0) {
if (a[j] <= temp) { // 如果新加入的结点大于等于它的父结点，那就表明没有调整的必要了，直接 break 就好了
break;
}
a[i] = a[j]; // 把刚刚找到的较大的父结点下移，替换它子结点
i = j; // 更新 i，向上继续为新加入的结点找合适的位置
j = (i - 1) / 2; // 更新 j，新的父结点
}
a[i] = temp; // 最后把新加入的结点值放在合适的位置
}
// 更简短的表达式
void MinHeapFixup(int a[], int i) {
for (int j = (i - 1) / 2; (j >= 0 && i != 0) && a[i] > a[j]; i = j, j = (i - 1) / 2)
Swap(a[i], a[j]);
}
堆的删除
按定义，堆中每次都只能删除第 0 个数据。为了便于重建堆，实际的操作是将最后一个数据的值赋给根结点，然后再从根结点开始进行一次从上向下的调整。调整时先在左右儿子结点中找最小的，如果父结点比这个最小的子结点还小说明不需要调整了，反之将父结点和它交换后再考虑后面的结点。相当于从根结点将一个数据的 “下沉” 过程。
// 在最小堆中删除数
void MinHeapDeleteNumber(int a[], int n) {
Swap(a[0], a[n - 1]);
MinHeapFixdown(a, 0, n - 1);
}
// 从 i 结点开始调整，n 为结点总数，从 0 开始计算 i 结点的子结点为 2 * i + 1, 2 * i + 2
void MinHeapFixdown(int a[], int i, int n) {
int j, temp;
temp = a[i];
j = 2 * i + 1; // 左结点下标
while (j < n) {
if (j + 1 < n && a[j + 1] < a[j]) { // 在左右子结点中找到最小的
j++;
}
if (a[j] >= temp) { // 如果 i 结点的值比其左右子结点的值都要小，则不需要调整了，直接 return
break;
}
a[i] = a[j]; // 把较小的子结点往上移动，替换它的父结点
i = j;
j = 2 * i + 1;
}
a[i] = temp;
}
堆化数组
首先对所有的叶子结点而言，可以认为它们已经是一个合法的堆了，所以从数组最后一个元素的父结点（((n - 1) - 1) / 2）开始调整就可以了。
// 建立最小堆
void MakeMinHeap(int a[], int n) {
for (int i = n / 2 - 1; i >= 0; --i) {
MinHeapFixdown(a, i, n);
}
}
堆排序
首先可以看到堆建好之后堆中第 0 个数据是堆中最小的数据。取出这个数据再执行下堆的删除操作。这样堆中第 0 个数据又是堆中最小的数据，重复上述步骤直至堆中只有一个数据时就直接取出这个数据。由于堆也是用数组模拟的，故堆化数组后，第一次将 A[0] 与 A[n - 1] 交换，再对 A[0…n-2] 重新恢复堆。第二次将 A[0] 与 A[n – 2] 交换，再对 A[0…n - 3] 重新恢复堆，重复这样的操作直到 A[0] 与 A[1] 交换。由于每次都是将最小的数据并入到后面的有序区间，故操作完成后整个数组就有序了。
void heapSort(int nums[], int count) {
if (nums == nullptr || count <= 0) {
return;
}
int i = (count - 1 - 1) / 2; // 最后一个元素的父节点
// 建堆
for (; i >= 0; --i) {
maxHeapFixdown(nums, i, count);
}
// 排序。每次把 0 节点的放到数组的最后面，然后再重新堆化数据
for (i = count - 1; i >= 1; --i) {
swap(&nums[0], &nums[i]);
maxHeapFixdown(nums, 0, i);
}
}
void maxHeapFixdown(int nums[], int i, int n) {
int j = i * 2 + 1; // 左子节点下标
int temp = nums[i]; // 节点的值
while (j < n) {
// 找到 i 节点的左右子节点中的较大值
if (j + 1 < n && nums[j + 1] > nums[j]) {
++j;
}
// 如果父节点的值大于等于左右子节点的值，则不用交换
if (nums[j] <= temp) {
break;
}
// 把子节点中较大的值赋给父节点
swap(&nums[i], &nums[j]);
// 更新 i 和 j
i = j;
j = i * 2 + 1;
}
}
- 稳定性： 不稳定。
- 空间复杂度：
O(1)。 - 时间复杂度： 由于每次重新恢复堆的时间复杂度为
O(logn)，共n - 1次重新恢复堆操作，再加上前面建立堆时n / 2次向下调整，每次调整时间复杂度也为O(logn)。二次操作时间相加还是O(n*logn)。故堆排序的时间复杂度为O(n*logn)。
参考链接
参考链接:🔗
