一：排序的概念及引入
1.1 排序的概念
1.1 排序的概念
- 排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
- 稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。
- 内部排序：数据元素全部放在内存中的排序。
- 外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。
1.2常见的排序算法
常见的排序算法有七种，分别是直接插入排序，希尔排序，选择排序，堆排序，冒泡排序，快速排序，归并排序
下面我们对这些排序进行一 一讲解。
二：插入排序
2.1 直接插入排序
直接插入排序是一种简单的插入排序法，其基本思想是：
把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列 。实际中我们玩扑克牌时，就用了插入排序的思想。
插入排序是一种简单直观的排序算法。它的原理是将待排序的元素逐个插入到已排序序列的适当位置，从而形成一个有序序列。
该算法的工作原理如下：
- 从第二个元素开始，将其与前面已排序的元素逐个比较，找到合适的位置插入。
- 将当前元素与前面已排序的元素进行比较，如果当前元素小于前面的元素，则将前面的元素后移一位，直到找到合适的位置。
- 插入当前元素到合适的位置后，继续比较并插入下一个元素。
- 重复上述步骤，直到所有元素都被插入到合适的位置。
动图如下：
下面是一个使用Java实现插入排序的示例代码：
public class InsertionSort { public static void insertionSort(int[] arr) { int n = arr.length; for (int i = 1; i < n; i++) { int key = arr[i]; // 当前要插入的元素 int j = i - 1; // 已经排好序的元素的最后一个索引 // 将比 key 大的元素向后移动 while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; // 向后移动元素 j--; // 向前遍历已经排好序的元素 } // 插入 key 到合适的位置 arr[j + 1] = key; // 将 key 插入到正确的位置 } } public static void main(String[] args) { int[] arr = {5, 2, 8, 9, 1, 3}; insertionSort(arr); // 使用插入排序算法对数组进行排序 System.out.println("排序后的数组："); for (int num : arr) { System.out.print(num + " "); // 输出排序后的数组 } } }
直接插入排序的特性总结：
- 元素集合越接近有序，直接插入排序算法的时间效率越高
- 时间复杂度：O(N^2)
- 空间复杂度：O(1)，它是一种稳定的排序算法
- 稳定性：稳定
2.2 希尔排序( 缩小增量排序 )
希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成多个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工作。当到达=1时，所有记录在统一组内排好序。
下面是希尔排序的工作原理：
- 选择一个增量序列，增量序列由一系列整数构成，通常是递减的，最后一个增量必须为1。
- 根据选定的增量序列，将待排序的数组分割成若干个子数组，每个子数组包含相同间隔的元素。
- 对每个子数组进行插入排序，即将每个子数组的元素依次与该子数组中的其他元素进行比较和交换，使得子数组中的元素逐渐有序。
- 重复以上步骤，缩小增量，直至增量为1。
- 最后进行一次完整的插入排序，以保证数组的最终有序性。
示图如下：
希尔排序的特性总结：
- 希尔排序是对直接插入排序的优化。
- 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很
快。这样整体而言，可以达到优化的效果。 - 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些树中给出的希尔排
序的时间复杂度都不固定
动图如下：
因为咋们的gap是按照Knuth提出的方式取值的，而且Knuth进行了大量的试验统计，我们暂时就按照：O（n1.25）到O（1.6 * n1.25） 来算。
下面是一个使用Java实现的希尔排序示例代码：
public class ShellSort { public static void shellSort(int[] arr) { int n = arr.length; // 初始化增量为数组长度的一半 int gap = n / 2; while (gap > 0) { for (int i = gap; i < n; i++) { int temp = arr[i]; int j = i; // 插入排序 while (j >= gap && arr[j - gap] > temp) { arr[j] = arr[j - gap]; j -= gap; } arr[j] = temp; } // 缩小增量 gap /= 2; } } public static void main(String[] args) { int[] arr = {9, 5, 2, 7, 1, 3, 6, 8, 4}; System.out.println("原始数组："); for (int num : arr) { System.out.print(num + " "); } System.out.println(); shellSort(arr); System.out.println("排序后的数组："); for (int num : arr) { System.out.print(num + " "); } } }
希尔排序稳定性：不稳定
三：选择排序
3.1直接选择排序
当我们需要对一个数组进行排序时，选择排序是一种简单而直观的算法。它的工作原理是选择数组中最小的元素，将它与数组的第一个元素交换位置。然后，选择剩余元素中最小的元素，将它与数组的第二个元素交换位置。以此类推，直到整个数组排序完成
动图如下：
public class SelectionSort { public static void main(String[] args) { // 创建一个整数数组 int[] arr = {64, 25, 12, 22, 11}; // 调用选择排序方法 selectionSort(arr); // 输出排序后的数组 System.out.println("排序后的数组："); for(int i=0; i < arr.length; i++){ System.out.print(arr[i] + " "); } } public static void selectionSort(int[] arr) { // 获取数组长度 int n = arr.length; // 遍历整个数组 for (int i = 0; i < n-1; i++) { // 假设当前索引为 i 的元素是最小值 int minIndex = i; // 在剩余的元素中寻找最小值的索引 for (int j = i+1; j < n; j++) { // 如果找到比当前最小值还小的值，则更新最小值的索引 if (arr[j] < arr[minIndex]) { minIndex = j; } } // 将最小值与当前位置交换 int temp = arr[minIndex]; arr[minIndex] = arr[i]; arr[i] = temp; } } }
【直接选择排序的特性总结】
- 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
- 时间复杂度：O(N^2)
- 空间复杂度：O(1)
- 稳定性：不稳定
3.2堆排序
堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。
堆排序具体的讲解可以查看这篇文章
【堆排序的特性总结】
- 堆排序使用堆来选数，效率就高了很多。
- 时间复杂度：O(N*logN)
- 空间复杂度：O(1)
- 稳定性：不稳定
四：交换排序
4.1冒泡排序
冒泡排序是一种简单但效率较低的排序算法。它的基本思想是通过不断比较相邻的两个元素并交换位置，从而将较大（或较小）的元素逐渐“冒泡”到数组的顶部（或底部）。这个过程会不断重复，直到数组中的所有元素都按照顺序排列。
下面是一个详细注释的 Java 示例代码：
public class BubbleSort { public static void bubbleSort(int[] arr) { int n = arr.length; // 外层循环控制比较的轮数，每轮比较后，最大的元素就会被冒泡到数组末尾 for (int i = 0; i < n - 1; i++) { // 内层循环用于比较相邻的元素并交换位置 // 每轮结束后，当前轮数已经排序完成的元素就会排在数组的最后 // 所以下一轮比较时，不需要再考虑这些元素 for (int j = 0; j < n - 1 - i; j++) { // 如果当前元素比下一个元素大，就交换它们的位置 if (arr[j] > arr[j + 1]) { int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } } } public static void main(String[] args) { int[] arr = {64, 34, 25, 12, 22, 11, 90}; System.out.println("原始数组："); for (int num : arr) { System.out.print(num + " "); } // 调用冒泡排序 bubbleSort(arr); System.out.println("\n排序后的数组："); for (int num : arr) { System.out.print(num + " "); } } }
动图如下：
【冒泡排序的特性总结】
- 冒泡排序是一种非常容易理解的排序
- 时间复杂度：O(N^2)
- 空间复杂度：O(1)
- 稳定性：稳定
4.2快速排序
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
4.2.1Hoare版
实现思路：
1: 首先，从数组的左端和右端分别设置一个指针，即i和j，以及选择一个基准值pivot。
2:通过循环，从数组的右端开始向左查找，找到第一个小于基准值的元素的下标，将该下标赋给j。然后从数组的左端开始向右查找，找到第一个大于基准值的元素的下标，将该下标赋给i。
3: 在找到两个元素的下标后，交换它们的位置，将小于基准值的元素移动到基准值的左边，大于基准值的元素移动到基准值的右边。然后继续循环，直到左指针i大于等于右指针j。
最后，将基准值放在正确的位置上，将其与左指针i所指向的元素进行交换。这样，基准值左边的元素都小于基准值，右边的元素都大于基准值。
需要注意的是：若选择最左边的数据作为key，则需要right先走；若选择最右边的数据作为key，则需要left先走
动图如下：
private static int partition(int[] array, int left, int right) { // 设置左右指针和基准值 int i = left; int j = right; int pivot = array[left]; // 在左指针小于右指针的条件下，进行循环 while (i < j) { // 从右往左找到第一个小于基准值的元素的下标 while (i < j && array[j] >= pivot) { j--; } // 从左往右找到第一个大于基准值的元素的下标 while (i < j && array[i] <= pivot) { i++; } // 交换找到的两个元素的位置 swap(array, i, j); } // 将基准值放在正确的位置上 swap(array, i, left); // 返回基准值的下标 return i; }
4.2.2挖坑法
实现思路：
1: 首先，在函数内部定义两个指针i和j，分别指向分区的左侧和右侧。初始时，将left作为基准元素的索引，即基准元素为array[left]。
2: 然后，通过循环，不断将大于基准元素的元素移动到右侧，将小于基准元素的元素移动到左侧。具体的操作是，先从右侧开始，找到小于或等于基准元素的元素，然后将该元素移动到左侧指针i的位置。
3: 接着，从左侧开始，找到大于或等于基准元素的元素，然后将该元素移动到右侧指针j的位置。如此反复进行，直到指针i和j相遇。
4: 最后，将基准元素放置到它最终的位置上，也就是指针i的位置。这样，基准元素左侧的元素都小于或等于它，右侧的元素都大于或等于它。
5: 最后返回基准元素的索引i，用于后续的分区。
注意：若在最左边挖坑，则需要R先走；若在最右边挖坑，则需要L先走
动图如下：
private static int partition(int[] array, int left, int right) { // 设置指针i和j分别指向分区的左侧和右侧 int i = left; int j = right; // 设置基准元素为分区的第一个元素 int pivot = array[left]; // 开始循环，直到指针i和j相遇 while (i < j) { // 从右侧开始，寻找小于或等于基准元素的元素 while (i < j && array[j] >= pivot) { j--; } // 找到后将该元素移动到左侧指针i的位置 array[i] = array[j]; // 从左侧开始，寻找大于或等于基准元素的元素 while (i < j && array[i] <= pivot) { i++; } // 找到后将该元素移动到右侧指针j的位置 array[j] = array[i]; } // 将基准元素放置到它最终的位置上 array[i] = pivot; // 返回基准元素的索引，用于后续的分区 return i; }
4.2.3前后指针
实现思路：
- 我们首先定义了两个变量
cur和prev，它们都指向数组的起始位置（cur = begin，prev = begin - 1）。 - 我们选择数组的最后一个元素作为基准元素，将其索引保存在变量
keyi中。 - 然后我们开始遍历数组，从头到尾比较每个元素与基准元素的大小。
- 如果当前元素小于基准元素，并且
prev不等于cur，则将当前元素与prev指向的元素交换位置。 - 随后，我们将
cur向后移动一位。 - 当遍历完整个数组后，我们将基准元素与
prev指向的元素交换位置，以确保基准元素的位置在整个数组中是正确的。 - 这样，数组被分成了两部分：左边是小于基准元素的部分，右边是大于基准元素的部分。基准元素的位置为
keyi。 - 接下来，我们对左半部分（
begin到keyi - 1）和右半部分（keyi + 1到end）分别进行递归调用。 - 重复以上步骤，直到子数组的长度为 1 或 0，即递归终止条件。
//快速排序法 前后指针版本 void QuickSort2(int* arr, int begin, int end) { if (begin >= end) return; int cur = begin, prev = begin - 1; int keyi = end; while (cur != keyi) { if (arr[cur] < arr[keyi] && ++prev != cur) { swap(&arr[cur], &arr[prev]); } ++cur; } swap(&arr[++prev],&arr[keyi]); keyi = prev; //[begin,keyi -1]keyi[keyi+1,end] QuickSort2(arr, begin, keyi - 1); QuickSort2(arr, keyi + 1, end); }
快速排序优化
- 三数取中法选key （三个数中取中间的数为基准）
- 递归到小的子区间时，可以考虑使用插入排序
快速排序总结：
- 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
- 时间复杂度：O(N*logN)
- 空间复杂度：O(logN)（特殊情况，如果数据本身有序或者逆序，那么时间复杂度为 O （N2））
- 稳定性：不稳定
时间复杂度示图：
五：归并排序
5.1 基本思想
归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide andConquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。 归并排序核心步骤：
动图：
归并排序总结：
- 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。
- 时间复杂度：O(N*logN)
- 空间复杂度：O(N)
- 稳定性：稳定
5.2 代码实现
public class MergeSort { // 归并排序入口函数 public int[] mergeSort(int[] array) { // 特殊情况处理：当数组为空或只有一个元素时，无需排序，直接返回 if (array == null || array.length <= 1) { return array; } // 调用归并排序算法进行排序 mergeSort(array, 0, array.length - 1); return array; } // 归并排序递归函数 private void mergeSort(int[] array, int start, int end) { // 当前排序范围只有一个元素，无需继续拆分 if (start >= end) { return; } // 找到当前排序范围的中间位置 int mid = start + (end - start) / 2; // 递归拆分左半部分 mergeSort(array, start, mid); // 递归拆分右半部分 mergeSort(array, mid + 1, end); // 合并左右两部分排序结果 merge(array, start, mid, end); } // 归并两个有序数组 private void merge(int[] array, int start, int mid, int end) { // 创建一个临时数组保存合并的结果 int[] temp = new int[end - start + 1]; int i = start; // 左半部分起始位置 int j = mid + 1; // 右半部分起始位置 int k = 0; // 临时数组的索引 // 遍历左右两部分数组，依次取出较小的元素放入临时数组中 while (i <= mid && j <= end) { if (array[i] < array[j]) { temp[k++] = array[i++]; } else { temp[k++] = array[j++]; } } // 处理剩余的元素 while (i <= mid) { temp[k++] = array[i++]; } while (j <= end) { temp[k++] = array[j++]; } // 将临时数组中的元素拷贝回原数组中 for (i = 0; i < temp.length; i++) { array[start + i] = temp[i]; } } }
下面对这段代码进行详细的讲解：
- 首先我们定义了一个公共类MergeSort，用于实现归并排序算法。
- mergeSort方法是入口函数，接收一个整型数组作为参数，并返回一个排序后的整型数组。在这个方法中，首先判断特殊情况，即当数组为空或只有一个元素时，无需排序，直接返回原数组；否则，调用归并排序算法进行排序。
- 归并排序的核心是递归拆分和合并两个有序数组。
- mergeSort方法是一个递归函数，接收一个整型数组array和两个整型变量start和end作为参数，表示当前排序范围的起始位置和结束位置。首先判断当前范围是否只有一个元素，如果是，则无需继续拆分；否则，找到当前范围的中间位置mid，分别递归拆分左半部分和右半部分，然后将拆分后的结果合并起来。
- merge方法用于合并两个有序数组。它接收一个整型数组array和三个整型变量start、mid和end作为参数，表示需要合并的两个有序数组在原数组中的位置。首先创建一个临时数组temp，用于保存合并的结果，长度为end-start+1。然后设置三个指针i、j和k，分别表示左半部分数组的起始位置、右半部分数组的起始位置和临时数组的索引。接下来，遍历左右两部分数组，依次取出较小的元素放入临时数组中，直到其中一个部分的元素取完。最后，如果左半部分数组还有剩余的元素，将其全部复制到临时数组中；如果右半部分数组还有剩余的元素，也将其全部复制到临时数组中。最后，将临时数组中的元素拷贝回原数组中，完成合并过程。
5.3海量数据的排序问题
外部排序：排序过程需要在磁盘等外部存储进行的排序
前提：内存只有 1G，需要排序的数据有 100G因为内存中因为无法把所有数据全部放下，所以需要外部排序，而归并排序是最常用的外部排序
- 先把文件切分成 200 份，每个 512 M
- 分别对 512 M 排序，因为内存已经可以放的下，所以任意排序方式都可以
- 进行 2路归并，同时对 200 份有序文件做归并过程，最终结果就有序了
六：排序总结
6.1排序算法复杂度及稳定性分析
6.2各个排序的比较
| 排序方法 | 最好 | 平均 | 最坏 | 空间复杂度 | 稳定性 |
| 冒泡排序 | O(n) | O(n2) | O(n2 ) | O(1) | 稳定 |
| 插入排序 | O(n) | O(n2) | O(n2) | O(1) | 稳定 |
| 选择排序 | O(n^2) | O(n2) | O(n2) | O(1) | 不稳定 |
| 希尔排序 | O(n) | O(n1.3) | O(n2) | 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(n2) | O(log n)~O(n) | 不稳定 |
| 归并排序 | O(n*log n) | O(n*log n) | O(n*log n) | O(n) | 稳定 |
