一、排序算法
冒泡排序在C语言部分学过，堆排序上一章学过，还剩五种常见排序算法。以下默认从小到大排序。
稳定性：相同元素在排序过后，前后相对位置依旧不变。一个本身稳定的排序，可以改成不稳定的；但一个本身不稳定的排序，无法改为稳定的。
二、直接插入排序
2.1、算法思想
第一个元素默认已排好，第 i 个元素依次与第 i-1 ~ 0 个元素比较，大于 i 号元素的就往后移一位，小于等于 i 号元素的，i 号元素就插入在其后，结束此趟排序。
2.2、代码实现
/*** 直接插入排序* 最坏时间复杂度：1 + 2 + 3 + ... + n = O(n^2)* 最好时间复杂度：O(n)，基本有序* 空间复杂度：O(1)* 稳定性：稳定*/public static void insertSort(int[] arr) {// 第一个元素默认已排好序，从第二个元素开始for (int i = 1; i < arr.length; i++) {int temp = arr[i]; // 待排序元素// 与 i-1 ~ 0 之间的所有元素比较int j = i - 1;for (; j >= 0; j--) {if (arr[j] > temp) { // 大于 arr[i] 的元素，向后移动一位arr[j + 1] = arr[j];} else { // 小于等于 arr[i] 的元素，在其后插入 arr[i]，结束次趟排序// 与 0 位置的元素比较后，仅仅是 0 位置元素向后移动一位，并没有在 0 位置插入 arr[i]，就退出了内循环// 因此，插入代码应该放在外循环。放在内循环，会导致没有考虑到在 0 位置插入 arr[i] 的情况。
// arr[j + 1] = temp;break;}}// 在 0 位置插入的情况，退出时 j = -1arr[j + 1] = temp; // 插入 arr[i]}}2.3、时间复杂度分析
最坏时间复杂度（倒序）：每第 i 个元素都要与前 i 个已排序好的元素比较。从第 2 个元素开始，1 + 2 + 3 + ... + n-1 = n*(n-1)/2 = O(n^2)。
最好时间复杂度（顺序）：每第 i 个元素都已经有序，只需要跟第 i-1 个元素比较一次。一共要比较 n-1 次，O(n)。如果序列基本有序的时候，可以使用直接插入排序算法。
二、希尔排序（缩小增量排序）
是优化版的直接插入排序。
2.1、算法思想
将数组分为 gap 组，组内进行直接插入排序，gap 逐渐缩小，直到 gap 为 1，此时数组已经基本有序，进行最后一次直接插入排序。（gap > 1 时，属于预排序，目的是让数组更接近有序。最后一次排序，数组已基本有序，排序就很快了。）
gap 的取法有很多，比如 n/2（后续每次 gap/2）、n/3+1。
gap 的分组是间隔 gap 个元素分为一组，而不是邻近元素分为一组：如下图，初始 gap=5，第 0 个元素和第 0+gap 个元素分为一组。
间隔元素分为一组的目的：排序后，让小的都在前一半，让大的都在后一半，更趋于有序。若是邻近元素分为一组，则没有这个规律，排序后数组是混乱的。
2.2、手动模拟希尔排序
gap=10/2=5 时，分5组。
组内进行直接插入排序。
gap=gap/2=5/2=2：
组内进行插入排序：
gap=2/2=1：
排序后：1 2 3 4 5 6 7 8 9。
2.3、代码实现
第一层循环，gap 从 n/2 逐步缩减到 1。第二层和第三层循环：组内进行直接插入排序。一组内：i 从 gap 开始，下一个组内元素递增 gap，直到 gap ≥ len 为止；j 从 i-1 开始，前一个组内元素递减 gap，直到 gap ＜ 0 结束。但这样存在一个问题，只排序好了一组，剩下的组并没有实现插入排序。
所以我们应该间断式地进行插入排序，将第二层循环的 i 自增 gap 改为自增 1，这一次对第一组的第二个元素进行插入排序，下一次对第二组的第二个元素进行插入排序……这样所有组都能完成插入排序。
/*** 希尔排序* 时间复杂度：难以准确计算* 空间复杂度：O(1)* 稳定性：不稳定*/public static void shellSort(int[] arr) {int gap = arr.length / 2; // 初始步长。第一趟排序后，前一半元素小，后一半元素大// gap 逐渐缩减到 1（即最后对基本有序的一组元素进行插入排序）while (gap > 0) {shellInsertSort(arr, gap);gap /= 2;}}// 希尔排序中的插入排序private static void shellInsertSort(int[] arr, int gap) {// 从第一组的第2个元素开始，不同组交叉进行插入排序for (int i = gap; i < arr.length; i++) {int temp = arr[i];// 组内每个元素之间间隔 gapint j = i - gap;for (; j >= 0; j -= gap) {if(arr[j] > temp) {arr[j + gap] = arr[j];}else {break;}}arr[j + gap] = temp;}}2.4、时间复杂度分析
若数组有 n 个元素，gap 组，则组内有 n/gap 个元素。最坏情况下，组内的比较次数为 1+2+……+(n/gap-1)。
以 gap=gap/2 为例子，当 gap=n/2 时，比较次数为 n/2 * 1 = (1/2)*n；
当 gap=n/4 时，比较次数为 n/4 * (1+2+3) = (3/2)*n；
当 gap=n/8 时，比较次数为 n/8 * (1+2+3+4+5+6+7) = (7/2)*n；
当 gap=n/16 时，比较次数为 n/16 * (1+2+……+15) = (15/2)*n；
…………
当 gap=1时，数组基本有序，比较次数接近 n 。
因此，我们可以得知，随着 gap 的缩减，比较次数会先递增，再递减，会存在一个最大比较次数。而 gap 为何值时，比较次数达到最大，我们是难以计算的。这也就导致，希尔排序的时间复杂度难以准确计算。
根据《数据结构(C语言版)》严蔚敏所说，希尔排序的时间复杂度大致为 O(N^1.5)。
总的来说，时间复杂度是比直接插入排序法更优的。
我们通过测试，也能直观地看到这种差距：（3万个随机整数排序）
三、选择排序
3.1、算法思想
在 n 个元素中选择最小值，与第一个位置的元素交换；在后 n-1 个元素中选择最小值，与第二个位置的元素交换……直到排好前 n-1 个小元素，最后一个元素自然排好。
3.2、代码实现
/*** 选择排序* 时间复杂度：O(n^2)* 空间复杂度：O(1)* 稳定性：不稳定*/public static void selectSort(int[] arr) {// 排前 n-1 个元素，最后一个元素自然排好for (int i = 0; i < arr.length - 1; i++) {int minIndex = i; // 最小元素的索引// 找出 i 到 n-1 之间最小的元素的索引for (int j = i + 1; j < arr.length; j++) {if (arr[j] < arr[minIndex]) {minIndex = j;}}// 交换 i 与最小元素。最小元素索引为 i 时，不需要交换if (minIndex!= i) {swap(arr, i, minIndex);}}}3.3、时间复杂度分析
不管时倒序还是正序，都需要比较 i 后所有的元素，以找到最小值，因此不分最好、最坏时间复杂度。
时间复杂度：找到第1小元素，比较 n-1 次，找到第2小元素，比较 n-2 次，……，找到第二大元素，比较 1 次。因此，(n-1)+(n-2)+……+2+1 = n*(n-1)/2，O(n^2)。
3.4、另一种选择排序
思路：在未排序的元素中选择最小值和最大值，分别与第一个未排序元素和最后一个未排序元素交换。
/*** 选择排序：同时选择最小值和最大值*/public static void selectSort2(int[] arr) {// left 和 right 分别指向未排序部分的第一个元素和最后一个元素int left = 0;int right = arr.length - 1;// left 和 right 相遇时，排序完成while (left < right) {// 找出 [left, right] 范围内的最小值和最大值int minIndex = left;int maxIndex = left;for (int i = left + 1; i <= right; i++) {if (arr[i] < arr[minIndex]) {minIndex = i;}if (arr[i] > arr[maxIndex]) {maxIndex = i;}}// 交换最小值和 left 指向的元素if (minIndex!= left) {swap(arr, left, minIndex);}// 如果 left 指向的元素就是最大值，left 与最小值交换后，会把最大值换走// 因此，当 left 指向的元素就是最大值时，需要把 maxIndex 改为 minIndex（最大值被换到的位置）if (arr[left] == arr[maxIndex]) {maxIndex = minIndex;}// 交换最大值和 right 指向的元素if (maxIndex != right) {swap(arr, right, maxIndex);}// 移动 left 和 right 指针left++;right--;}}四、堆排序
4.1、算法思想
创建大根堆，每次将最大值堆顶换到最后一个未排序元素位置，再从堆顶开始向下调整，调整范围是未排序元素。
4.2、代码实现
/*** 堆排序* 时间复杂度：O(N*logN)* 空间复杂度：O(1)* 稳定性：不稳定*/public static void heapSort(int[] arr) {// 建堆，O(N*logN)buildMaxHeap(arr, arr.length);// 排序,O(N*logN)for (int i = arr.length - 1; i > 0; i--) {swap(arr, 0, i); // 堆顶元素与最后一个元素交换shiftDown(arr, 0, i); // 堆调整}}// 创建大根堆private static void buildMaxHeap(int[] arr, int n) {// 从下往上调整每一棵子树for (int parent = (n-1-1) / 2; parent >= 0; parent--) {shiftDown(arr, parent, n);}}// 向下调整堆private static void shiftDown(int[] arr, int i, int n) {int parent = i;int child = 2 * i + 1;while (child < n) { // 存在孩子if (child + 1 < n && arr[child + 1] > arr[child]) { // 存在右孩子，且右孩子大于左孩子child++; // 最大孩子指向右孩子}if (arr[child] > arr[parent]) {swap(arr, child, parent); // 孩子大于父节点，交换parent = child; // 继续向下调整child = 2 * parent + 1;} else {break;}}}五、冒泡排序
5.1、算法思想
每次将邻近值比较，逐渐将最大值“冒”到后面。
5.2、代码实现
/*** 冒泡排序：优化版本，分析时间复杂度时，不考虑优化情况* 时间复杂度：O(N^2)* 如果考虑优化：O(N)，对比一趟就结束* 空间复杂度：O(1)*/public static void bubbleSort(int[] arr) {// 最后一个元素自然排好for (int i = 0; i < arr.length - 1; i++) {boolean flag = false; // 标记是否发生交换// j+1 < arr.length-i 每一趟排序后，最大的元素被排到最后for (int j = 0; j < arr.length - i - 1; j++) {// 相邻元素比较，较大的元素向后冒泡if (arr[j] > arr[j + 1]) {swap(arr, j, j + 1);flag = true; // 发生交换}}// 若没有发生交换，说明已排序完成，退出if (!flag) {break;}}}六、快速排序
6.1、算法思想
一种二叉树结构的交换排序法。现在序列中任选一个元素作为基准，经过一趟排序后，基准左边的元素都小于基准，基准右边的元素都大于基准。分别对左、右子序列重复上述过程，直到序列不可再分。
6.2、主逻辑代码实现
6.2.1、非递归版
/*** 快速排序，主逻辑* 时间复杂度：O(N*logN)* 最坏情况：O(N^2)，有序或逆序时* 空间复杂度：O(logN)* 最坏情况，O(N)* 稳定性：不稳定*/public static void quickSort(int[] arr) {quickSort(arr, 0, arr.length - 1);}public static void quickSort(int[] arr, int left, int right) {// 序列长度小于等于 1，结束递归if (left >= right) {return;}// 选取基准元素int divPosition = partitionHoare(arr, left, right);// 左子序列排序quickSort(arr, left, divPosition);// 右子序列排序quickSort(arr, divPosition + 1, right);}6.2.2、递归版
分析：模拟递归，首先想到栈，后进先出。过程：找到序列的划分后，得到基准下标。右子序列的 left 和 right 入栈，左子序列的 left 和 right 入栈，入栈条件是 left > right，才有必要继续划分。弹出栈顶的两个元素，即 left 和 right，继续划分。执行上述循环，直到栈空。
public static void quickSort2(int[] arr) {Stack<Integer> stack = new Stack<>(); // 栈，保存每个子序列的左右边界// 初始边界if (arr.length > 1) {stack.push(0);stack.push(arr.length - 1);} else {return;}// 栈为空，表示没有子序列需要划分while (!stack.isEmpty()) {int right = stack.pop();int left = stack.pop();// 划分子序列int divPosition = partitionHoare(arr, left, right);// 右子序列边界入栈if (divPosition > left) {stack.push(left);stack.push(divPosition);}// 左子序列边界入栈if (divPosition + 1 < right) {stack.push(divPosition + 1);stack.push(right);}}}6.3、按基准划分的方法
不同的划分方法，得到的划分结果也不同。
6.3.1、Hoare 法
思路：选取序列的第一个元素作为基准，left、right 分别指向首、尾元素，每趟交换前，right 直到找到小于基准的元素停止自减，left 直到找到大于基准的元素停止自增，自减自增过程中指针left 不能大于 right（① 可以防止指针越界。② 相遇时就表明序列已遍历完，并且它们指向的元素必定小于或等于基准）。最后，将左边的大元素与右边的小元素进行交换。重复寻找交换元素并交换的过程，直到 left 与 right 相遇。循环结束后，交换基准与 left 与 right 相遇时指向的元素。
private static int partitionHoare(int[] arr, int left, int right) {int div = left;while (left < right) {// 右指针向左移动，直到遇到小于基准元素的元素while (left < right && arr[right] >= arr[div]) {right--;}// 左指针向右移动，直到遇到大于基准元素的元素while (left < right && arr[left] <= arr[div]) {left++;}// 交换左右指针指向的元素，即将小于基准元素的元素放到左边，大于基准元素的元素放到右边swap(arr, left, right);}// 基准元素归位swap(arr, div, right);// 返回基准元素的索引return right;}① 为什么不能 left 先找：完成最后一次交换后，left 和 right 之间的序列已经划分好。如果 left 先找，必然是 left 自增遇到 right 停止自增，而 right 此时指向的位置必然是大于等于基准的，left = right 最后与基准交换就可能出现错误，让大于基准的数放到了左边。
② 为什么 arr[right] >= div，要包含等于：如果不包含等于，表明 left 或 right 遇到等于基准的元素会停止自增自减，然后触发交换。如果是序列 6……6，left 将始终指向首，right 始终指向尾，导致死循环。
6.3.2、挖坑法
思路：默认选序列首元素为基准，基准另外存在一个变量中，此时序列首位置 left 就是一个坑。right 找到小于基准的，就放到 left 的坑中，right 位置成为坑；left 找到大于基准的，就放到 right 的坑中，left 成为坑。重复上述循环，直到相遇，最后将基准放到 left=right 指向的坑中。
private static int partition2(int[] arr, int left, int right) {int div = arr[left];while (left < right) {// 右指针向左移动，直到遇到小于基准元素的元素，将小于基准元素的元素放到 left 位置的坑中while (left < right && arr[right] >= div) {right--;}arr[left] = arr[right];// 左指针向右移动，直到遇到大于基准元素的元素，将大于基准元素的元素放到 right 位置的坑中while (left < right && arr[left] <= div) {left++;}arr[right] = arr[left];}// 基准元素归位arr[left] = div;// 返回基准元素的索引return left;}6.3.3、前后指针法（了解）
思路：如果 cur 指向小于基准的元素，且 pre 的下一个是 cur，则同时自增（pre 与 cur 之间没有大于基准的的元素）；如果 cur 指向大于基准的元素，仅 cur 自增，pre 负责守着 pre 后 cur 前的大于基准的元素；如果 cur 再次指向小于基准的元素，且 pre 的下一个不是 cur（pre 和 cur 之间存在大于基准的元素），pre 就把下一个守着的大于基准的元素跟 cur 指向的小于基准的元素交换，实现小的在左边，大的在右边。
private static int partition3(int[] arr, int left, int right) {int pre = left; // 守着 pre 后 cur 前的大于基准的元素// 遇到大于等于基准的元素，就存在 pre 与 cur 之间（pre不自增），继续找// 遇到小于基准的元素，就判断 pre 与 cur 之间存没存大于等于基准的元素（pre要自增），存了就交换，实现大或等于的放左，小的放右，然后继续找；没存直接继续找int cur = left + 1;while (cur <= right) { // cur 不能越界if(arr[cur] < arr[left] && arr[++pre] != arr[cur]) {// cur 遇到小于基准的元素，pre 与 cur 之间存有大于等于基准的元素，pre 指向下一个大于基准的元素，然后交换swap(arr, pre, cur);}cur++; // 继续找}// 最后 pre 指向的位置就是基准元素的位置swap(arr, left, pre);return pre;}6.4、复杂度分析
时间复杂度：k=logn 层二叉树，每层都比较了 n 次（划分阶段，会遍历子序列的所有元素），总共 n*logn 次。O(N*logN)。
最坏时间复杂度：有序或逆序时，k个元素的子序列，k-1 个元素都排在基准的一边。最后 n 个元素的排列结果，二叉树有 n 层，每层都要比较 n 个元素（下图中，只有1个元素的划分未画出）。 O(N^2)。
空间复杂度：递归深入的层数就是二叉树的层数。左子序列递归完成后，会回收内存，继续递归右子序列，因此，使用的最大内存空间是二叉树的高度 O(logN)。
最坏空间复杂度：二叉树高度为N。O(N)。
6.5、快速排序递归版的优化
从 6.4 小节我们知道，当序列基本有序时，如果只是简单的将序列首元素作为基准划分，会导致空间复杂度高，达到 O(N)。当 N 较大时，就容易导致栈溢出，简单粗暴的解决办法就是在idea上设置栈内存大小。
另一种是用改进的算法，避免因划分的左右子序列大小极度不均，导致的空间复杂度过高。
6.5.1、三数取中
思路：将首、中、尾元素取中位数，作为基准元素，让划分更均匀。
public static void quickSort(int[] arr, int left, int right) {// 序列长度小于等于 1，结束递归if (left >= right) {return;}// 求中位数int div = median(arr, left, right);// 中位数作为基准swap(arr, left, div);// 选取基准元素
// int divPosition = partitionHoare(arr, left, right);
// int divPosition = partition2(arr, left, right);int divPosition = partition3(arr, left, right);// 左子序列排序quickSort(arr, left, divPosition);// 右子序列排序quickSort(arr, divPosition + 1, right);}/*** 三数取中*/public static int median(int[] arr, int left, int right) {int mid = (left + right) / 2;// left 和 right 中，较大值作为 leftleft = arr[left] > arr[right]? left : right;if(arr[mid] > arr[left]) {return left;} else if(arr[mid] < arr[right]) {return right;} else {return mid;}}6.5.2、结合插入排序
思路：快速排序时，当子序列越小越趋于有序。基本有序时，直接插入排序的效率高，时间复杂度为 O(N)。因此，可以当子序列小到一定范围时，改用直接插入排序，减少递归深度，并提高排序效率。
public static void quickSort(int[] arr, int left, int right) {// 序列长度小于等于 1，结束递归if (left >= right) {return;}// 子序列长度小于等于 10 时，改用直接插入排序if (right - left + 1 <= 10) {insertSort(arr, left, right);return;}// 求中位数
// int div = median(arr, left, right);// 中位数作为基准
// swap(arr, left, div);// 选取基准元素
// int divPosition = partitionHoare(arr, left, right);
// int divPosition = partition2(arr, left, right);int divPosition = partition3(arr, left, right);// 左子序列排序quickSort(arr, left, divPosition);// 右子序列排序quickSort(arr, divPosition + 1, right);}private static void insertSort(int[] arr, int left, int right) {for (int i = left + 1; i <= right; i++) {int temp = arr[i];int j = i - 1;while (j >= left && arr[j] > temp) {arr[j + 1] = arr[j];j--;}arr[j + 1] = temp;}}七、归并排序
7.1、算法思想
分治思想。先使子序列有序，再合并有序的子序列，得到有序的序列。如果是合并两个有序子序列，就叫二路归并。
合并思路：创建新的数组，存放合并后的结果。i，j 指针指向两个子序列的元素，更小的放入新数组，并指向下一个。一个子序列遍历完后，若另一个还没遍历完，就把另一个剩的元素直接加到新数组里。最后将合并后的数组复制到原数组对应位置。
7.2、代码实现
合并代码：
public static void merge(int[] arr, int left1, int right1, int left2, int right2) {int[] temp = new int[right2 - left1 + 1];int i = left1;int j = left2;int k = 0;while (i <= right1 && j <= right2) {if (arr[i] <= arr[j]) {temp[k++] = arr[i++];} else {temp[k++] = arr[j++];}}// 剩的复制到结尾while (i <= right1) {temp[k++] = arr[i++];}while (j <= right2) {temp[k++] = arr[j++];}// 复制回原数组for (i = left1; i <= right2; i++) {arr[i] = temp[i - left1];}}7.2.1、递归版
思路：先求中间位置，然后左、右子序列分别进行归并排序，再将两个有序的子序列合并。
public static void mergeSort(int[] arr) {mergeSort(arr, 0, arr.length - 1);}private static void mergeSort(int[] arr, int left, int right) {if (left >= right) {return;}int mid = (left + right) / 2;mergeSort(arr, left, mid);mergeSort(arr, mid + 1, right);merge(arr, left, mid, mid + 1, right);}7.2.2、非递归版
思路：初始 gap=1，每次增加 gap 的一倍，逐渐增加到 gap=n/2，相邻两个分组两两合并。
public static void mergeSort2(int[] arr) {for(int gap = 1; gap < arr.length; gap *= 2) {for(int i = 0; i < arr.length; i += gap * 2) { // 两两合并int mid = i + gap - 1;// 只够分一组的情况，不用合并if(mid >= arr.length - 1) {break;}int right = Math.min(mid + gap, arr.length - 1); // 防止越界merge(arr, i, mid, mid + 1, right);}}}7.3、复杂度分析
时间复杂度：每层每个子序列分裂为2组，有 logN 层，每层都会对比 N 次，时间复杂度 O(N*logN)。
空间复杂度：logN + N（存放合并后的序列），O(N)。
稳定性：稳定。
7.4、应用场景
当需要对大量数据进行排序时，需要进行外部排序（在外部磁盘中进行排序）。比如对 100 G 的数据进行排序，但是内存只有 1G 的情况。
首先将 100G的文件分为 200 份，每份 512M，选用任意一种排序算法，分别对每份文件在内存中进行排序。对每份文件进行合并时，在磁盘中用归并排序算法进行合并。
八、其它非基于比较的排序
8.1、计数排序
算法思想：计算待排序序列的最大值 max 和最小值 min，再创建一个计数数组 count，大小为 max-min+1。遍历原数组，将计数统计在 count 中，对应下标就是原数组的元素值。最后遍历 count 数组，对应 index 有多少计数，就在原数组中放置多少个 index。
使用场景：序列元素比较集中（连续）的情况。
代码实现：
public static void countSort(int[] arr) {int max = arr[0];int min = arr[0];// 找出最大值和最小值，O(N)for (int i = 1; i < arr.length; i++) {if (arr[i] > max) {max = arr[i];}if (arr[i] < min) {min = arr[i];}}int[] count = new int[max - min + 1];// 统计每个元素出现的次数，O(N)for (int j : arr) {count[j - min]++;}// 遍历计数数组，将每个元素复制到原数组，O(max-min+1)int index = 0;for (int i = 0; i < count.length; i++) {int temp = count[i];while (temp-- > 0) {arr[index++] = i + min;}}}时间复杂度：O(max(N, max-min+1))。
空间复杂度：count 数组的大小，O(max-min+1)。
稳定性：稳定。
8.2、基数排序
排序：125、336、789、453、268、319、69、229。
一位数范围 0~9，创建10个队列：
按个位数，放入队列中：
按 0~9 顺序依次取出，先进先出：
453、125、336、268、789、319、69、229。
按十位数，放入队列中：
319、125、229、336、453、268、69、789。
按百位数，放入队列中：
69、125、229、268、319、336、453、789。
8.3、桶排序
