插入排序
一、直接插入排序
1、 基本思想🍉
把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列。
步骤：每次从无序部分中取出一个元素，与有序部分中的元素从后向前依次进行比较，并找到合适的位置，将该元素插到有序组当中。可以看下面动画展示：
2、代码实现🍉
public class Main { public static void insertionSort(int[] arr) { if (arr == null || arr.length < 2) { return; } for (int i = 1; i < arr.length; i++) { for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) { swap(arr, j, j + 1); } } } public static void swap(int[] arr, int i, int j) { int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } public static void main(String[] args) { int[] arr={1,8,6,29,10,14,37,48};//排序结果为1,6,8,10,14,29,37,48 insertionSort(arr); } }
3、代码优化🍉
Ⅰ、🧁插入排序优化（二分）
将待排序的元素与有序部分的元素比较时，不再挨个比较，而是用二分折中的方式进行比较，去寻找到arr[i]的位置，加快了比较效率
public class Main { public static void insertionSort(int[] arr) { int j,left,mid,right,temp; for(int i = 1;i<arr.length;i++){ left = 0; right = i-1; temp = arr[i]; /*找到合适的插入位置right+1，如果中间位置元素 *比要插入元素大，则查找区域向低半区移动，否则向高半区移动 */ while(left <= right){ mid = (left+right)/2; if(arr[mid]>temp){ right = mid-1; }else{ left = mid+1; } } /*right+1后的元素后移*/ for(j = i-1;j >= right+1;j--) { arr[j+1] = arr[j]; } /*将元素插入到指定位置*/ arr[j+1] = temp; } } public static void main(String[] args) { int[] arr={1,8,6,29,10,14,37,48};//排序结果为1,6,8,10,14,29,37,48 insertionSort(arr); } }
Ⅱ、🧁插入排序优化
在直接插入排序中，每次插入都需要将待插入元素与已排序序列中的元素逐一比较，如果待插入元素比已排序序列中的元素小，就需要将已排序序列中的元素后移。这个过程可以使用赋值的方式来代替元素的移动，从而提高排序的效率。
public static void insertSort(int[] arr) { int len = arr.length; for (int i = 1; i < len; i++) { int temp = arr[i]; int j = i - 1; while (j >= 0 && arr[j] > temp) { arr[j + 1] = arr[j]; j--; } arr[j + 1] = temp; } }
4、优缺点🍉
在数据已经有序或基本有序的情况下，排序效率较高，甚至可以达到O(n)的时间复杂度。 但是在数据规模较大的情况下，排序效率较低，时间复杂度为O(n^2)；而且 对于逆序的数据，每次插入都需要将已排序序列中的所有元素后移一位，因此排序效率非常低；
5、总结🍉
直接插入排序的特性总结：
1. 元素集合越接近有序，直接插入排序算法的时间效率越高
2. 时间复杂度：最环情况：O(N²)。最好情况：O（N）
3. 空间复杂度：O(1)
4. 稳定性：稳定
5. 适用场景：待排序序列的元素个数不多时，且元素基本偏向有序。
二、希尔排序🍭
1、基本思路🍉
希尔排序法又称缩小增量法，该方法因 D.L.Shell 于 1959 年提出而得名。希尔排序法的基本思想是：首先取一个整数n（小于序列元素总数）作为间隔，把待排序数字中所有数分成几个组，所有间隔相同的数分在同一组内，并对每一组
内的数进行排序。缩小间隔n，重复上述分组和排序的工作。当达到n=1 时，所有记录统一在一组内排好序。
其实从上面的希尔排序的思想中也能看出希尔排序的实现步骤：
- 选n，划分逻辑分组，组内进行直接插入排序。
- 不断缩小n，继续组内进行插入排序。
直到n=1，在包含所有元素的序列内进行直接插入排序。
其中缩小间隔gap 的取法有多种。最初 Shell 提出取 gap =n/2，gop =gap/2，直到 gap =1。后来 Knuth 提出取 gap =gap/3 +1。还有人提出都为好有人提 gap 互质为好。无论哪一种主张都没有得到证明。
2、代码实现🍉
public class Main { public static void shellSort(int[] arr){ /*初始化划分增量*/ int n = arr.length; int temp; /*每次减小增量，直到n = 1*/ while (n > 1){ /*增量的取法之一：除2向下取整*/ n = n/2; /*对每个按gap划分后的逻辑分组，进行直接插入排序*/ for (int i = n; i < arr.length; ++i) { if (arr[i-n] > arr[i]) { temp = arr[i]; int j = i-n; while (j >= 0 && arr[j] > temp) { arr[j+n] = arr[j]; j -= n; } arr[j+n] = temp; } } } } public static void main(String[] args) { int[] arr={1,8,6,29,10,14,37,48};//排序结果为1,6,8,10,14,29,37,48 shellSort(arr); } }
3、代码优化🍉
Ⅰ、🧁希尔排序优化（二分）
由于希尔排序是基于插入排序的，所以在插入排序中也可运用直接插入排序中的优化方式，所有也可以以二分折中的方式来优化希尔排序。
public class Main { public static void shellSort(int[] arr) { int j, left, mid, right, temp; int n = arr.length; while (n > 1) { n /= 2; for (int i = n; i < arr.length; i++) { left = 0; right = i - 1; temp = arr[i]; while (left <= right) { mid = (left + right) / 2; if (arr[mid] > temp) { right = mid - 1; } else { left = mid + 1; } } for (j = i - n; j >= right + 1; j-=n) { arr[j + n] = arr[j]; } arr[j + n] = temp; } } } public static void main(String[] args) { int[] arr = {1, 8, 6, 29, 10, 14, 37, 48};//排序结果为1,6,8,10,14,29,37,48 shellSort(arr); } }
Ⅱ、🧁
我们首先计算出初始的间隔值gap，然后在每次循环中，将gap逐步减小，直到变为1。在每次循环中，对于每个间隔为gap的子序列，我们采用插入排序的方式进行排序。
public static void shellSort(int[] arr) { int n = arr.length; int h = 1; // 计算间隔值 while (h < n / 3) { h = 3 * h + 1; } while (h >= 1) { // 对每个子序列进行插入排序 for (int i = h; i < n; i++) { for (int j = i; j >= h && arr[j] < arr[j - h]; j -= h) { swap(arr, j, j - h); } } // 缩小间隔值 h /= 3; } } // 交换数组中两个元素的位置 private static void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; }
- 计算间隔值时，只需要计算一次，并使用while循环找到最大的合适值。
- 使用插入排序对每个子序列进行排序，因为插入排序对于小数组来说效率更高。
- 在插入排序中，使用间隔值h来代替常规的1。
4、优缺点🍉
🧁优点：
希尔排序的时间复杂度较低。在大多数情况下，其时间复杂度为O(n^1.3)，尤其适用于中等大小的数组。
希尔排序不像其他排序算法需要大量的额外空间，因此可以在内存有限的情况下使用。
希尔排序是一种稳定的排序算法，即相同元素在排序前和排序后的位置不会发生改变。
🧁缺点：
希尔排序的实现较为复杂。它涉及到多个子序列和间隔值的计算，这增加了程序的代码量和阅读难度。
希尔排序由于具有不确定性，因此很难预测其排序时间。在某些情况下，其时间复杂度可能会退化到O(n^2)或更高，导致性能下降。
希尔排序的间隔值选择对于排序时间的影响非常大。如果选择错误的间隔值，可能会导致排序时间变得非常长。
综上所述，希尔排序是一种高效的排序算法，但实现较为复杂，且对于间隔值选择敏感。在某些情况下，可能存在性能问题。因此，在实际应用中，需要根据具体情况来选择是否使用希尔排序。
5、总结🍉
- 希尔排序是对直接插入排序的优化。
- 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。
- 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些书中给出的希尔排序的时间复杂度都不固定。时间复杂度：平均情况：(nlogn)~ o(n²) 。最好情况：o(n¹˙³)。最环情况： o(n²) 。
- 空间复杂度：0(1)
- 稳定性：不稳定
- 适用场景：待排序序列元素较少时。
计数排序🍭
1、基本思想🍉
计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用，是一种非基于比较的排序算法。操作步骤：
- 统计相同元素出现次数
- 根据统计的结果将序列回收到原来的序列中
2、代码实现🍉
步骤：
- 找到数组中的最大值和最小值。
- 创建一个大小为(max-min+1)的桶，用于统计元素出现的次数。
- 遍历原数组，统计每个元素出现的次数，把它们放到对应的桶中
- 对桶进行顺序求和，bucket[i]存放的就是原数组中小于等于i的元素个数。
- 从后往前遍历原数组，根据桶中统计的元素个数，将每个元素放到正确的位置上。
- 把排好序的元素复制回原数组。
public static void countingSort(int[] arr) { if (arr == null || arr.length <= 1) return; // 找到数组中的最大值和最小值 int max = arr[0], min = arr[0]; for (int i = 1; i < arr.length; i++) { max = Math.max(max, arr[i]); min = Math.min(min, arr[i]); } int bucketSize = max - min + 1; // 桶的大小 int[] bucket = new int[bucketSize]; // 创建桶 // 统计每个元素出现的次数 for (int i = 0; i < arr.length; i++) { bucket[arr[i] - min]++; } //System.out.println(Arrays.toString(bucket));//[1, 1, 0, 0, 1, 0, 1, 0, 2] // 对桶进行顺序求和，bucket[i]存放的就是原数组中小于等于i的元素个数 for (int i = 1; i < bucketSize; i++) { bucket[i] += bucket[i - 1]; } //System.out.println(Arrays.toString(bucket));//[1, 2, 2, 2, 3, 3, 4, 4, 6] int[] temp = new int[arr.length]; // 创建临时数组 // 从后往前遍历原数组，根据桶中统计的元素个数，将每个元素放到正确的位置上 for (int i = arr.length - 1; i >= 0; i--) { temp[--bucket[arr[i] - min]] = arr[i]; } //System.out.println(Arrays.toString(temp));[1, 2, 5, 7, 9, 9] // 把排好序的元素复制回原数组 for (int i = 0; i < arr.length; i++) { arr[i] = temp[i]; } }
3、优缺点🍉
计数排序的主要优点是时间复杂度第，稳定性好，适用于范围小的整数数据。计数排序的主要缺点是需要额外的存储空间（当数据范围大时，这一缺点将会无限放大），无法处理浮点型数据排序等其他类型的数据。
4、算法分析🍉
下面n是待排序数组的长度，k是桶的大小
1、时间复杂度：O(n+k)。
因为不需要比较操作，只需要遍历一次原数组，并对桶进行顺序求和和遍历，所以它的时间复杂度是O(n+k)。由于k通常比n要小，因此计数排序的时间复杂度可以看作是线性的。
2、空间复杂度：O(n+k)。
计数排序需要创建一个足够大的桶来存储每个元素出现的次数，因此空间复杂度与桶的大小有关。如果待排序数组中的最大值和最小值之间差距很大，那么桶的数量会增加，导致空间复杂度变高。另外，由于计数排序不需要比较操作，因此它不需要额外的存储空间来存储比较结果，所以只需要考虑桶的大小对空间复杂度的影响。
3、稳定性：计数排序是一种稳定的排序算法。
因为它在统计每个元素出现次数时，使用了桶来存储每个元素的出现次数。当有多个元素值相同时，它们会被放到同一个桶里，并按照原始输入的顺序存储在桶中。在遍历桶时，我们按照桶内元素统计的顺序，将每个元素放到正确的位置上，从而保证了排序的稳定性。
5、应用场景🍉
适用于范围小的整数数据。（原因优缺点处已写）
归并排序🍭
1945年，约翰·冯·诺依曼（John von Neumann）发明了归并排序。归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
归并排序有两个基本的操作，一个是分，也就是把原数组划分成两个子数组的过程。另一个是治，它将两个有序数组合并成一个更大的有序数组。
1、基本思路🍉
将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。 归并排序核心步骤：
动画展示：
2、代码实现🍉
Ⅰ、🧁递归写法
public static void mergeSort(int[] arr, int left, int right) { if (left < right) { int mid = (left + right) / 2; mergeSort(arr, left, mid); mergeSort(arr, mid + 1, right); merge(arr, left, mid, right); } } public static void merge(int[] arr, int left, int mid, int right) { int[] temp = new int[right - left + 1]; int i = left, j = mid + 1, k = 0; while (i <= mid && j <= right) { if (arr[i] <= arr[j]) { temp[k++] = arr[i++]; } else { temp[k++] = arr[j++]; } } while (i <= mid) { temp[k++] = arr[i++]; } while (j <= right) { temp[k++] = arr[j++]; } for (int p = 0; p < temp.length; p++) { arr[left + p] = temp[p]; } }
Ⅱ、🧁迭代写法
public static void mergeSort(int[] arr) { int n = arr.length; int[] temp = new int[n]; for (int gap = 1; gap < n; gap *= 2) { for (int i = 0; i < n - gap; i += gap * 2) { int left = i; int mid = i + gap - 1; int right = Math.min(i + 2 * gap - 1, n - 1); merge(arr, left, mid, right, temp); } } } public static void merge(int[] arr, int left, int mid, int right, int[] temp) { int i = left, j = mid + 1, k = 0; while (i <= mid && j <= right) { if (arr[i] <= arr[j]) { temp[k++] = arr[i++]; } else { temp[k++] = arr[j++]; } } while (i <= mid) { temp[k++] = arr[i++]; } while (j <= right) { temp[k++] = arr[j++]; } for (int p = 0; p < k; p++) { arr[left + p] = temp[p]; } }
迭代实现方式相对于递归实现方式，可以减少递归调用的开销，从而提高排序的效率。在迭代实现方式中，我们首先定义一个临时数组temp，然后将原始数组按照一定的间隔值gap分成若干个子数组，对每个子数组进行排序，并将排好序的子数组合并成一个有序数组。在合并的过程中，我们同样需要借助一个临时数组来存储排好序的元素。
3、代码优化🍉
Ⅰ、🧁对于短数组使用插入排序
虽然归并排序在大型数组上的表现很好，但它在小型数组上会变得较慢。对于长度小于或等于某个阈值的子数组，插入排序比归并排序要快得多。所以我们可以在代码中添加一个判断条件，在数组长度小于某个值时使用插入排序。
public static void mergeSort(int[] arr, int l, int r) { if (l >= r) { return; } if (r - l <= 15) { insertSort(arr, l, r); return; } int mid = (l + r) / 2; mergeSort(arr, l, mid); mergeSort(arr, mid + 1, r); merge(arr, l, mid, r); } public static void insertSort(int[] arr, int l, int r) { for (int i = l + 1; i <= r; i++) { int temp = arr[i]; int j = i - 1; for (; j >= l && arr[j] > temp; j--) { arr[j + 1] = arr[j]; } arr[j + 1] = temp; } }
总结🍉
1. 归并的缺点在于需要O(N)的空间复杂度，但是其速度仅次于快速排序
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(N)
4. 稳定性：稳定
5.适用场景：待排序序列中元素较多，并且要求较快的排序速度时。
🧁归并排序解决海量数据的排序问题
外部排序：排序过程需要在磁盘等外部存储进行的排序
前提：内存只有 1G，需要排序的数据有 100G
因为内存中因为无法把所有数据全部放下，所以需要外部排序，而归并排序是最常用的外部排序
1. 先把文件切分成 200 份，每个 512 M
2. 分别对 512 M 排序，因为内存已经可以放的下，所以任意排序方式都可以
3. 进行 2路归并，同时对 200 份有序文件做归并过程，最终结果就有序了。
八大排序总结
1、初始数据集的排列顺序对算法的性能无影响的有:
- 堆排序
- 归并排序
- 选择排序
2、每一次排序之后都能确定至少一个元素位置的排序方法包括：
- 选择排序：每次将最大的数放到最后。所以最大的数排一次序后位置就确定了。
- 冒泡排序：同选择排序。每一次排序最大的值位置确定
- 快排：每一次排序pivot的位置确定。
- 堆排序：每一次排序时，都是将堆顶的元素和最后一个节点互换，然后调整堆，再将堆大小减1。所以每一次排序堆顶元素确定。
3、不能至少确定一个元素的位置的方法包括：
- 插入排序：不到最后一步求的都是相对位置。
- shell排序：对简单插入排序的改进。不到最后一步，是无法确定每个元素位置的。
- 归并排序：局部有序，并不能确定任一元素在全局的位置。
- 基数排序，计数排序：利用桶排序的思路，不是基于比较的排序，也无法在一次排序中确定某个元素的位置。因为每一次排序都是整体处理。
4、请简单介绍一下冒泡排序的原理和实现方式：
冒泡排序的基本原理是依次比较相邻的元素，如果顺序不对则交换，每一轮都会确定一个数的位置。实现方式可以使用双重循环遍历数组，外层控制轮数，内层控制比较和交换。
5、请介绍快速排序的实现方式以及时间复杂度
快速排序采用分治法，通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可以分别对这两部分记录继续进行快速排序，以达到整个序列有序。实现方式类似冒泡排序，也是基于双重循环递归实现的，但是需要选取一个pivot来进行划分。时间复杂度为 O(n log n)。
6、请介绍堆排序的原理和实现方式。
堆排序的基本原理是将待排序元素构建成堆，逐步将堆顶元素和堆底元素交换，然后重新调整堆，重复此过程直至所有元素排序完毕。实现过程中需要先构建堆，然后依次将堆顶元素取出并调整堆。时间复杂度为 O(n log n)。
7、插入排序和选择排序的区别是什么？
插入排序和选择排序都属于简单排序算法，区别在于插入排序是将待排序元素插入到已排序数列中的合适位置，而选择排序则是在待排序元素中选择最小（或最大）的元素放到已排序的数列末尾。另外，插入排序比选择排序更适用于基本有序序列的排序。
8、请介绍归并排序的实现方式以及时间复杂度。
归并排序采用分治法，将待排序序列不断拆分为两个子序列，直至每个子序列只有一个元素，然后将两个有序子序列合并成一个有序序列。实现方式可以使用递归实现，也可以使用迭代实现。时间复杂度为 O(n log n)。
