看到这句话的时候证明：此刻你我都在努力
加油陌生人
前言
今天就写一篇关于排序的文章，本文章包含了，如标题所写的八大排序。八大排序各有各的使用场景，在某个特定场景，那么可能有一个排序就非常适合，所以排序我们是多多益善。
直接插入排序（Straight Insertion Sort）
直接插入排序（Straight Insertion Sort）是一种简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
排序特点：
稳定性：直接插入排序是稳定的排序算法，因为相等的元素的相对顺序不会改变。
时间复杂度：在最好的情况下（数组已经是排序的），时间复杂度为O(n)；在最坏的情况下（数组是逆序的），时间复杂度为O(n^2)；平均时间复杂度为O(n^2)。
空间复杂度：由于直接插入排序是原地排序，不需要额外的存储空间，所以空间复杂度为O(1)。
排序适用场景：
数据规模较小：直接插入排序由于其简单性，适用于数据规模较小的情况。
部分已经排序：如果数组部分已经排序，直接插入排序的性能会比较好。
代码实现：
public static void insetSort(int[] array) { for (int i = 1; i < array.length; i++) { int tmp = array[i]; int j = i - 1; for (; j >= 0; j--) { if (array[j] > tmp) { array[j + 1] = array[j]; } else { break; } } array[j + 1] = tmp; } }
排序实现：
从第一个元素开始，该元素可以认为已经被排序。
取出下一个元素，在已经排序的元素序列中从后向前扫描。
如果该元素（已排序）大于新元素，将该元素移到下一位置。
重复步骤3，直到找到已排序的元素小于或者等于新元素的位置。
将新元素插入到该位置后，即挑出循环直接给array[j+1]赋值，然后重复步骤2~4。
对于所有的元素重复步骤1~5。
希尔排序（Shell Sort）
希尔排序（Shell Sort）是一种经典的排序算法，由Donald Shell在1959年提出。它是插入排序的一种改进版，也称为缩小增量排序。希尔排序的核心思想是将待排序的序列分割成若干子序列，对每个子序列进行插入排序，随着增量的逐渐减小，子序列逐渐合并，最终整个序列变得有序。
排序特点：
希尔排序是不稳定的排序算法，因为相同元素可能在排序过程中改变相对位置。
它的时间复杂度在最坏情况下为O(n^2)，但平均情况下通常为O(nlogn)到O(n^(3/2))，这取决于增量序列的选择。
希尔排序的空间复杂度为O(1)，因为它是一种原地排序算法。
适用场景：
希尔排序适用于中等规模的数据排序，因为它比简单的插入排序有更快的效率，但比快速排序和归并排序慢。在数据规模不是特别大的情况下，希尔排序可以作为一个不错的选择。
复杂度分析：
希尔排序的性能与增量序列的选择密切相关。一个好的增量序列可以使得算法在最坏情况下的时间复杂度接近O(nlogn)。然而，目前还没有找到一个通用的最优增量序列，这仍然是一个开放的数学问题。
代码实现：
public static void shellSort(int[] array) { int gap = array.length; while (gap > 1) { gap = gap / 2; shell(array, gap); } } private static void shell(int[] array, int gap) { for (int i = gap; i < array.length; i++) { int tmp = array[i]; int j = i - gap; for (; j >= 0; j -= gap) { if (array[j] > tmp) { array[j + gap] = array[j]; } else { break; } } array[j + gap] = tmp; } }
排序实现：
选择一个增量序列，常见的选择是将增量逐渐缩小，例如初始增量为gap/2，然后每次缩小一半，直到增量为1。
按照增量将待排序序列分割成若干子序列，每个子序列的元素在原序列中间隔增量个位置。
对每个子序列进行插入排序。
逐步缩小增量，重复步骤2和3，直到增量减小到1，此时对整个序列进行插入排序。
选择排序（Selection Sort）
选择排序（Selection Sort）是一种简单直观的比较排序算法。它的工作原理是每次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。
算法特点：
选择排序是一种不稳定的排序算法，因为相同的元素可能因为排序而改变顺序。
它的时间复杂度为O(n^2)，其中n是序列的长度。无论数组是否已经排序，选择排序的性能都是最差的。
选择排序的空间复杂度为O(1)，因为它是一种原地排序算法，不需要额外的存储空间。
适用场景：
选择排序由于其简单性，适用于数据规模较小的情况。在数据规模较大时，由于其时间复杂度较高，通常不推荐使用。
性能分析：
最好、最坏和平均时间复杂度都是O(n^2)。
空间复杂度为O(1)。
代码实现：
public static void selectSort2(int[] array) { for (int i = 0; i < array.length; i++) { int mindIndex = i; for (int j = i + 1; j < array.length; j++) { if (array[j] < array[mindIndex]) { mindIndex = j; } } swap(array, i, mindIndex); } } private static void swap(int[] array, int i, int j) { int tmp = array[i]; array[i] = array[j]; array[j] = tmp; }
排序实现：
找到最小值：从未排序的序列中找到最小（或最大）的元素。
交换：将找到的最小（或最大）元素与序列的起始位置交换。
重复查找：从剩余的未排序元素中继续寻找最小（或最大）元素，然后与下一个位置交换，重复这个过程。
结束：当所有元素都被排序时，算法结束。
我们也可以对这个排序进行优化，即：让数组两边都开始找，一边找最大值，一边找最小值。
优化后的选择排序：
public static void selectSort(int[] array) { int left = 0; int right = array.length - 1; while (left < right) { int minIndex = left; int maxIndex = left; for (int i = left + 1; i <= right; i++) { if (array[i] < array[minIndex]) { minIndex = i; } if (array[i] > array[maxIndex]) { maxIndex = i; } } swap(array, left, minIndex); //最大值正好是 left下标 此时 把最大值换到了minIndex的位置了 if (maxIndex == left) { maxIndex = minIndex; } swap(array, right, maxIndex); left++; right--; } }
冒泡排序（Bubble Sort）
冒泡排序（Bubble Sort）是一种简单的排序算法，它重复地遍历待排序的序列，比较每对相邻元素，如果它们的顺序错误就把它们交换过来，遍历序列的工作重复进行，直到没有再需要交换的元素，这表明序列已经排序完成。
排序特点：
冒泡排序是一种稳定的排序算法，因为它不会改变相同元素之间的顺序。
它的时间复杂度为O(n^2)，在所有情况下都是如此，无论是最好、最坏还是平均情况。
冒泡排序的空间复杂度为O(1)，因为它是原地排序，不需要额外的存储空间。
适用场景：
冒泡排序由于其简单性，适用于数据规模较小且要求稳定性的场景。在数据规模较大时，由于其时间复杂度较高，通常不推荐使用。
代码实现：
public static void bubbleSort(int[] array) { for (int i = 0; i < array.length - 1; i++) { boolean flg = false; for (int j = 0; j < array.length - 1 - i; j++) { if (array[j] > array[j + 1]) { swap(array, j, j + 1); flg = true; } } if (!flg) { break; } } }
排序步骤：
比较相邻的元素：从第一个元素开始，比较相邻的元素对，如果它们的顺序错误（即前一个比后一个大），就交换它们。
交换元素：对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在一趟遍历中，最大的元素会移动到它最终的位置。
重复遍历：针对所有的元素重复以上的步骤，除了最后一个已经排好的元素。
优化：在每次遍历中，最大的元素会移动到序列的末端，因此下一次遍历时可以忽略这个元素，即减少下一次遍历的序列长度。
堆排序（Heap Sort）
堆排序（Heap Sort）是一种高效的比较类排序算法，利用了二叉堆的数据结构来实现。堆是一个满足以下性质的完全二叉树：对于最大堆，父节点的值总是大于或等于它的子节点的值；对于最小堆，父节点的值总是小于或等于它的子节点的值。
排序特点：
堆排序是一种选择排序，它不改变相同元素之间的顺序，因此是一种稳定的排序算法。
它的时间复杂度为O(nlogn)，无论是最好、最坏还是平均情况。
堆排序的空间复杂度为O(1)，因为它是原地排序，不需要额外的存储空间。
适用场景：
堆排序适用于数据规模较大且对排序效率有一定要求的场景。由于其时间复杂度稳定，它在很多情况下都是一个不错的选择。
复杂度分析：
时间复杂度：O(nlogn)。
空间复杂度：O(1)。
代码实现：
public static void heapSort(int[] array) { createHeap(array); int end = array.length - 1; while (end > 0) { swap(array, 0, end); siftDown(array, 0, end); end--; } } private static void createHeap(int[] array) { for (int parent = (array.length - 1 - 1) / 2; parent >= 0; parent--) { siftDown(array, parent, array.length); } } private static void siftDown(int[] array, int parent, int length) { int child = 2 * parent + 1; while (child < length) { if (child + 1 < length && array[child] < array[child + 1]) { child++; } if (array[child] > array[parent]) { swap(array, parent, child); parent = child; child = 2 * parent + 1; } else { break; } } }
排序步骤：
建立最大堆：将待排序的序列构造成一个最大堆，即父节点的值总是大于或等于它的子节点的值。
交换并调整堆：将堆顶元素（最大值）与序列的最后一个元素交换，然后将序列的最后一个元素移除（即排序完成），并对交换后的堆进行调整，使其继续保持最大堆的性质。
重复交换和调整：重复步骤2，直到整个序列排序完成。
注意：这里我们将建堆和向下调整单独封装成单个私有函数。
快速排序（Quick Sort）
快速排序（Quick Sort）是一种高效的排序算法，由C. A. R. Hoare在1960年提出。它采用分治法（Divide and Conquer）的策略来对一个数组进行排序。但是他最坏的情况时间复杂度为O(n^2)，但是下面我们将用到三数取中法，范围内进行直接插入排序来优化快排，在一般情况下快排还是很高效的。
排序特点：
快速排序是一种分治法策略的应用，它将一个大问题分解成小问题解决。
它是一个原地排序（不需要额外存储空间）。
快速排序是非稳定的排序算法，相同元素的相对顺序可能会改变。
在平均状况下，快速排序的时间复杂度为O(nlogn)，但最坏情况下会退化到O(n^2)。
适用场景：
快速排序适用于大部分需要排序的场景，尤其是数据规模较大的情况。它通常比其他O(nlogn)算法更快，因为它的内部循环非常高效。
性能分析：
最佳和平均时间复杂度：O(nlogn)。
最坏时间复杂度：O(n^2)，当数据已经是有序或接近有序时（包括逆序）。
空间复杂度：O(logn)，递归栈的深度。
public static void quick(int[] array, int start, int end) { if (start >= end) { return; } if (end - start + 1 <= 7) { insertSortRange(array, start, end); return; } int midIndex = getMiddleNum(array, start, end); swap(array, start, midIndex); int pivot = partition(array, start, end); quick(array, start, pivot - 1); quick(array, pivot + 1, end); } private static void insertSortRange(int[] array, int start, int end) { for (int i = start + 1; i <= end; i++) { int tmp = array[i]; int j = i - 1; for (; j >= start; j--) { if (array[j] > tmp) { array[j + 1] = array[j]; } else { array[j + 1] = tmp; break; } } array[j + 1] = tmp; } } private static int getMiddleNum(int[] array, int left, int right) { int mid = (left + right) / 2; if (array[left] < array[right]) { if (array[mid] < array[left]) { return left; } else if (array[mid] > array[right]) { return right; } else { return mid; } } else { if (array[mid] > array[left]) { return left; } else if (array[mid] < array[right]) { return right; } else { return mid; } } } private static int partition(int[] array, int left, int right) { int tmp = array[left]; while (left < right) { while (left < right && array[right] >= tmp) { right--; } array[left] = array[right]; while (left < right && array[left] <= tmp) { left++; } array[right] = array[left]; } array[left] = tmp; return left; }
这里展示的是经过优化后的快排，这样的快排就不会那么容易出现时间复杂度为：O(n^2)的情况。
排序步骤：
选择基准值：在数据集之中，选择一个元素作为基准值（pivot）。
分区操作：重新排列数据集，比基准值小的元素摆放在基准前面，比基准值大的元素摆在基准后面，相等的则可以放到任一边。在这个分区退出之后，该基准就处于集合的中间位置。
递归排序：递归地将小于基准值的子数组和大于基准值的子数组排序。
然后就是优化部分：
首先我们在递归过程中如果此时子数组的长度小于等于7时，我们就对这个数组进行直接插入排序，因为这时数组其实已经趋于有序，这时使用直接插入排序的效率是比较高的。然后我们取基准值时我们尽量取数组中值比较中间得数作为基准值（pviot），这样也可以提高快排得效率。
归并排序（Merge Sort）
归并排序（Merge Sort）是一种高效的比较排序算法，采用分治法（Divide and Conquer）的一个典型应用。它将数组分成两半，对每一半递归地进行排序，然后将结果归并（合并）起来。
排序特点：
归并排序是稳定的排序算法，它保持相同元素的相对顺序不变。
它的时间复杂度为O(nlogn)，无论是最好、最坏还是平均情况。
归并排序的空间复杂度为O(n)，因为它需要额外的空间来存储合并后的数组。
适用场景：
归并排序适用于数据规模较大且需要稳定排序结果的场景。它在外部排序（数据太大，无法一次性加载到内存中）中特别有用。
复杂度分析：
时间复杂度：O(nlogn)。
空间复杂度：O(n)。
private static void mergeSortTmp(int[] array, int left, int right) { if (left >= right) { return; } int mid = (left + right) / 2; mergeSortTmp(array, left, mid); mergeSortTmp(array, mid + 1, right); //走到这里 全部分解完毕 // 合并 merge(array, left, mid, right); } private static void merge(int[] array, int left, int mid, int right) { int[] tmp = new int[right - left + 1]; int k = 0; int s1 = left; int s2 = mid + 1; while (s1 <= mid && s2 <= right) { if (array[s1] <= array[s2]) { tmp[k++] = array[s1++]; } else { tmp[k++] = array[s2++]; } } while (s1 <= mid) { tmp[k++] = array[s1++]; } while (s2 <= right) { tmp[k++] = array[s2++]; } //可以保证tmp数组 是有序的 for (int i = 0; i < k; i++) { array[i + left] = tmp[i]; } }
排序步骤：
- 分解：将当前序列从中间分成两个子序列。
- 递归排序：递归地对两个子序列进行归并排序。
- 合并：将两个排序好的子序列合并成一个最终的排序序列。
计数排序（Counting Sort）
计数排序一个不需要进行比较也能进行排序的排序方式，是不是觉得很神奇呢。那么下面我们就看看吧。
计数排序（Counting Sort）是一种非比较型整数排序算法，其核心思想是使用一个额外的数组（称为计数数组）来统计待排序数组中每个元素的出现次数，然后根据这些计数来确定每个元素在排序数组中的位置。
排序特点：
计数排序是一种稳定的排序算法，它不会改变相同元素之间的相对顺序。
它的时间复杂度为O(n+k)，其中n是待排序数组的长度，k是待排序数组中最大和最小值的差。
计数排序的空间复杂度为O(k)，因为需要额外的数组来存储计数信息。
适用场景：
计数排序适用于整数排序，特别是当整数的数值范围不是很大时。它在处理大量数据时非常高效，尤其是当数据分布比较均匀时。
性能分析：
- 时间复杂度：O(n+k)，n是数组长度，k是数值范围。
- 空间复杂度：O(k)。
public static void countSort(int[] array) { //1. 找最大值 和 最小值 来确定 计数数组的大小 int maxVal = array[0]; int minVal = array[0]; for (int i = 1; i < array.length; i++) { if (array[i] < minVal) { minVal = array[i]; } if (array[i] > maxVal) { maxVal = array[i]; } } int len = maxVal - minVal + 1; int[] count = new int[len]; //2. 遍历原来的数组array把 每个元素 放到对应的计数数组当中 进行计数 for (int i = 0; i < array.length; i++) { int index = array[i]; count[index - minVal]++; } //3.依次 遍历计数数组 O(范围) int index = 0; for (int i = 0; i < count.length; i++) { while (count[i] != 0) { array[index] = i + minVal; index++; count[i]--; } } }
排序步骤：
- 统计频次：创建一个计数数组，用于统计每个整数出现的次数。
- 计算前缀和：计算计数数组的前缀和，前缀和表示每个整数在排序后数组中的起始位置。
- 构建排序数组：根据计数数组构建排序数组，将每个整数放置到其在排序数组中的相应位置。
