目录
一、排序
二、插入排序
2.1 直接插入排序
2.2 希尔排序
三、选择排序
3.1 直接选择排序
3.2 堆排序
四、交换排序
4.1 冒泡排序
4.2 快速排序
五、归并排序
六、排序算法分析
总结
一、排序
排序：就是使一串记录序列，按照其中某个或某些关键字的大小，进行递增或递减的排列操作。
稳定性：假定在待排序的记录序列中，存在多个具有相同关键字的记录，若经过排序后，这些记录的相对次序保持不变，则称这种排序算法是稳定的；否则称为不稳定。
例如，在原序列中，r[i] = r[j]，且 r[i] 在 r[j] 之前，若排序后的序列中，r[i] 仍在 r[j] 之前，则排序算法稳定，反之即不稳定。
二、插入排序
2.1 直接插入排序
核心思想：从第二个元素开始遍历，每次遍历将该元素与其前方元素对比，做出相应交换。
public static void insertSort(int[] array) {//初始 i 下标指向第二个元素for (int i = 1; i < array.length; i++) {//将 i下标的值放入 temp 中int temp = array[i];//初始 j 下标指向 i 下标的前一位int j = i-1;for (; j >= 0; j--) {//若 j 下标的值比 temp 中的值大，则将其往后移一位if (array[j] > temp) {array[j+1] = array[j];} else {break;}}//循环结束将原本 i 的值放至 j 下标的后一位中array[j+1] = temp;}}【总结】
时间复杂度：
最坏情况下：O(n^2)
最好情况下：O(n)
空间复杂度：O(1)
稳定性：稳定
适用性：待排序序列接近有序
2.2 希尔排序
希尔排序也叫缩小增量排序，基本思想：选定一个整数 gap，将待排序序列分为 gap 组，所有距离为 gap 的元素为同一组，每组分别进行直接插入排序；然后缩小 gap，继续分组排序，直至 gap = 1 时，所有元素为一组，最后进行一次直接插入排序。
public static void shellSort(int[] array) {int gap = array.length;//gap>1 都属于预排序while (gap > 1) {//取 gap 为全部元素的一半gap /= 2;//每组排序shell(array, gap);}}private static void shell(int[] array, int gap) {//初始 i 下标指向 gap，即每组的第二个元素for (int i = gap; i < array.length; i++) {//将 i下标的值放入 temp 中int temp = array[i];//初始 j 下标指向 i 下标的前 1gap 位//j 每次往前 1gap 位int j = i-gap;for (; j >= 0; j-=gap) {//若 j 下标的值比 temp 中的值大，则将其往后移 1gap 位if (array[j] > temp) {array[j+gap] = array[j];} else {break;}}//循环结束将原本 i 的值放至 j 下标的后 1gap 位中array[j+gap] = temp;}}【总结】
1、希尔排序是对直接插入排序的优化。
2、当 gap>1 时，都是预排序，是为了让序列趋于有序。
3、稳定性：不稳定
三、选择排序
3.1 直接选择排序
核心思想：遍历每个元素，每次遍历确定一个最小值令其有序。
public static void selectSort(int[] array) {//遍历每个元素for (int i = 0; i < array.length; i++) {//初始化 minIndex 用于指向最小值int minIndex = i;//i 下标与后方每个元素对比for (int j = i+1; j < array.length; j++) {//确保 minIndex 指向 i 下标及其后方元素的最小值if (array[j] < array[minIndex]) {minIndex = j;}}//交换 i 下标与 minIndex 下标的值int temp = array[i];array[i] = array[minIndex];array[minIndex] = temp;}}【总结】
时间复杂度：O(n^2)
空间复杂度：O(1)
稳定性：不稳定
3.2 堆排序
① 创建大根堆，初始化 end = array.length-1，即 end 指向最后一个结点；
② 将栈顶元素交换至 end 下标。由于大根堆中栈顶元素最大，故交换一次，end--，保证每次交换后的栈顶元素位置不变；
③ 重新向下调整为大根堆；
④ 重复 ②、③ 操作，直至排序完成。
//创建大根堆private static void createHeap(int[] array) {//从最后一棵子树开始调整，依次往前，直至根结点//父亲结点 = (孩子结点-1) / 2//usedSize-1 是树中最后一个结点for (int parent = (array.length-1-1) / 2; parent >= 0; parent--) {//向下调整siftDown(array, parent,array.length);}}//堆排序public static void heapSort(int[] array) {//创建大根堆createHeap(array);int end = array.length-1;while (end > 0) {//将大根堆中栈顶元素交换至 endswap(array, 0, end);//向下调整为大根堆siftDown(array, 0, end);//保证每次调整的栈顶元素位置不变end--;}}//向下调整private static void siftDown(int[] array, int parent, int length) {//左孩子结点 = 父亲结点*2 + 1int child = parent*2 + 1;//首先保证该结点有左孩子结点while (child < length) {//再次确定该结点有右孩子结点，再进行比较//保证 child 引用指向孩子结点中最大值if ((child+1) < length && array[child] < array[child+1]) {//若右孩子的值大于左孩子，则 child 引用指向右孩子child = child + 1;}if (array[child] > array[parent]) {//若 child 比 parent 大，则交换元素swap(array, child, parent);//parent 指向 child 位置，向下调整至下方无子树parent = child;child = parent*2 + 1;} else {//子结点都比父结点小break;}}}//交换元素private static void swap(int[] array, int i, int j) {int temp = array[i];array[i] = array[j];array[j] = temp;}【总结】
时间复杂度：O(n*log n)
空间复杂度：O(1)
稳定性：不稳定
四、交换排序
4.1 冒泡排序
核心思想：进行 array.length-1 趟比较，每次确定一个最大值元素。
public static void bubbleSort(int[] array) {//i 表示趟数for (int i = 0; i < array.length-1; i++) {//设置一个标签，检测该趟是否发生交换boolean flag = false;//j 表示该趟比较次数for (int j = 0; j < array.length-1-i; j++) {//每趟确定一个最大值if (array[j] > array[j+1]) {int temp = array[j];array[j] = array[j+1];array[j+1] = temp;//若交换，则改变标签状态flag = true;}}//若标签状态未改变，则序列已经有序if (!flag) {break;}}}【总结】
时间复杂度：O(n^2)，若加上 flag 优化，则最好可以达到 O(n)
空间复杂度：O(1)
稳定性：稳定
4.2 快速排序
1、Hoare版
核心思想：以 0 下标元素为基准，保证每次排序后，基准左侧元素小于基准，右侧大于基准，分别在左序列与右序列进行递归排序。
public static void quickSort(int[] array) {quick(array, 0, array.length-1);}private static void quick(int[] array, int start, int end) {// start < end 时才需要排序if (start >= end) {return;}//找到基准的下标int pivot = partitionHoare(array, start, end);//左序列quick(array, start, pivot-1);//右序列quick(array, pivot+1, end);}private static int partitionHoare(int[] array, int left, int right) {//保存基准的值int temp = array[left];//保存基准的下标int index = left;while (left < right) {//在右侧找到比基准小的数while (left < right && array[right] >= temp) {right--;}//在左侧找到比基准小的数while (left < right && array[left] <= temp) {left++;}swap(array, left, right);}//保证基准左侧都比基准小，右侧都比基准大swap(array, index, left);//确定基准的位置时，left = rightreturn left;}2、挖坑版
核心思想：以 0 下标元素为基准，0 下标处为第一个坑位，从右侧开始遍历，找到比基准小的元素放至 left 下标 (初始即 0 下标) 处；然后从左侧遍历到比基准大的放至 right 下标处，循环至 left 与 right 相遇，将基准放入最后一个坑位。
public static void quickSort(int[] array) {quick(array, 0, array.length-1);}private static void quick(int[] array, int start, int end) {// start < end 时才需要排序if (start >= end) {return;}//找到基准的下标int pivot = partition(array, start, end);//左序列quick(array, start, pivot-1);//右序列quick(array, pivot+1, end);}private static int partition(int[] array, int left, int right) {//保存基准的值int temp = array[left];//保存基准的下标int index = left;while (left < right) {//在右侧找到比基准小的数while (left < right && array[right] >= temp) {right--;}//找到放置左边的坑位array[left] = array[right];//在左侧找到比基准小的数while (left < right && array[left] <= temp) {left++;}//找到放置右边的坑位array[right] = array[left];}//将基准值放入最后一个坑中array[left] = temp;//确定基准的位置时，left = rightreturn left;}【总结】
时间复杂度：O(n*log n)
空间复杂度：O(log n)
稳定性：不稳定
五、归并排序
将两个有序序列合并成一个有序序列的操作，称为二路归并。
核心步骤：先分解再合并。
public static void mergeSort(int[] array) {merge(array, 0, array.length-1);}private static void merge(int[] array, int start, int end) {// start < end 时才需要排序if (start >= end) {return;}//标记序列中间下标int mid = (start+end)/2;//左序列merge(array, start, mid);//右序列merge(array, mid+1, end);//排序, 合并mergeMethod(array, start, mid, end);}private static void mergeMethod(int[] array, int left,int mid, int right) {//指向左右序列最小值int min1 = left;int min2 = mid+1;//定义一个新的空间用于排序int[] sort = new int[right-left+1];//新空间的下标int k = 0;//保证左右序列都有元素while (min1 <= mid && min2 <= right) {//左右序列从最左侧(最小值)开始比较if (array[min1] <= array[min2]) {sort[k++] = array[min1++];} else {sort[k++] = array[min2++];}}//表示右序列中无元素，即左序列剩下元素比右序列都要大while (min1 <= mid) {sort[k++] = array[min1++];}//表示左序列中无元素，即右序列剩下元素比左序列都要大while (min2 <= right) {sort[k++] = array[min2++];}//将排序好的数组，拷贝回原数组for (int i = 0; i < sort.length; i++) {//利用 left 下标(每个序列起始下标) 保证右序列可以顺利拷贝array[i+left] = sort[i];}}【总结】
时间复杂度：O(n*log n)
空间复杂度：O(n)
稳定性：稳定
适用性：更多是在解决磁盘中的外排序问题
六、排序算法分析
| 排序方法 | 最好 | 平均 | 最坏 | 空间复杂度 | 稳定性 |
| 冒泡排序 | O(n) | O(n^2) | O(n^2) | O(1) | 稳定 |
| 插入排序 | O(n) | O(n^2) | O(n^2) | O(1) | 稳定 |
| 选择排序 | O(n^2) | O(n^2) | O(n^2) | O(1) | 不稳定 |
| 希尔排序 | O(n) | O(n^1.3) | O(n^2) | O(1) | 不稳定 |
| 堆排序 | O(n*log n) | O(n*log n) | O(n*log n) | O(1) | 不稳定 |
| 快速排序 | O(n*log n) | O(n*log n) | O(n^2) | O(log n) ~ O(n) | 不稳定 |
| 归并排序 | O(n*log n) | O(n*log n) | O(n*log n) | O(n) | 稳定 |
总结
1、希尔排序是对直接插入排序的优化。
2、直接选择排序效率不高，很少使用；堆排序效率高。
3、快速排序综合性能和使用场景都是比较好的。
4、归并排序更多是在解决磁盘中的外排序问题。