java学习之数据结构：三、八大排序

主要介绍学过的各种排序算法

目录

1.插入排序

1.1直接插入排序

1.2希尔排序

2.选择排序

2.1直接选择排序

2.2堆排序

3.交换排序

3.1冒泡排序

3.2快速排序

4.归并排序

5.基数排序

---

1.插入排序

1.1直接插入排序

基本思想：就是将待排序的数据按照其元素值的大小注意插入到一个已经排好序的有序序列中，直到所有数据插完为止。

基本流程：

1. 初始化：从数组的第二个元素开始，将其当作第一个待插入的元素。
2. 遍历未排序元素：对数组从第二个元素到最后一个元素进行遍历，每次取一个未排序的元素作为待插入元素。
3. 寻找插入位置：把待插入元素存储在临时变量 temp 中，然后从已排序序列的末尾开始向前查找，只要已排序序列中的元素大于待插入元素，就将该元素向后移动一位。
4. 插入元素：当找到一个不大于待插入元素的位置或者已经遍历完已排序序列时，将待插入元素插入到该位置之后。
5. 重复步骤 2 - 4：持续重复上述操作，直至所有元素都被插入到合适的位置，此时数组完成排序。

代码如下：

    public static void insertSort(int[] arr) {for (int i = 1; i < arr.length; 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;}}

时间复杂度： 

最好的情况：最好的情况就是数组已经升序有序，只有最外面一层for循环遍历一次数组，里面的while循环每一次都是直接退出，因此最好的情况时间复杂度为O(N)

最坏的情况：最坏的情况就是数组是降序排序，里面while循环的时间复杂度为O(N)，因此最坏情况下，时间复杂度为O(N^2)

综上，直接插入法的时间复杂度为O(N^2)

1.2希尔排序

基本思想：对直接插入的优化。先选定一个整数gap，把待排序文件中所有记录分成数组，所有距离为gap的记录分在同一组内，并对每一组内的记录进行排序。然后缩小gap，重复上述步骤，当gap == 1时，所有记录在统一组内已经排好序。

基本流程：

1. 初始化间隔：把间隔 gap 设定为数组长度的一半。这个间隔用于将数组划分成多个子序列。
2. 分组排序：在 gap 大于 0 的条件下，开展如下操作：
   • 从 gap 位置开始遍历数组，对每个元素执行插入排序操作。
   • 把当前元素保存到临时变量 temp 里。
   • 从当前元素的前一个间隔位置开始，只要该位置的元素大于 temp，就将其向后移动间隔个位置。
   • 找到合适位置后，把 temp 插入进去。
3. 缩小间隔：每完成一轮分组排序后，将间隔 gap 缩小，一般是除以 2。
4. 重复操作：持续重复步骤 2 和 3，直至 gap 变为 0，此时数组排序完成。

代码如下：

    public static void shellSort(int[] arr) {int gap = arr.length / 2;while (gap > 0) {for (int i = gap; i < arr.length; i++) {int temp = arr[i];int j = i - gap;while (j >= 0 && arr[j] > temp) {arr[j + gap] = arr[j];j -= gap;}arr[j + gap] =temp;}}}

时间复杂度：希尔排序的时间复杂度为O(NLogN)

2.选择排序

2.1直接选择排序

基本思想：每一轮从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到全部待排序的数据元素排完

基本流程：

1. 外层循环遍历：使用变量 i 从数组的第一个元素开始，一直到倒数第二个元素（i 范围是 0 到 arr.length - 2）进行遍历。每一轮外层循环都对应着将一个未排序元素放到正确的位置。
2. 确定最小元素索引：
   • 每轮外层循环开始时，先假设当前 i 位置的元素是未排序部分中的最小元素，将其索引 i 赋值给 minIndex。
   • 开启内层循环，让变量 j 从 i + 1 开始，遍历到数组末尾（j 范围是 i + 1 到 arr.length - 1）。在内层循环中，逐个比较 arr[j] 和 arr[minIndex]，若 arr[j] 更小，就把 j 的值赋给 minIndex。内层循环结束后，minIndex 就指向了未排序部分里的最小元素。
3. 交换元素：
   • 检查 minIndex 是否和 i 不相等。若不相等，意味着未排序部分的最小元素不在 i 位置，需要交换它们。
   • 借助临时变量 temp 来完成交换，先把 arr[i] 的值存到 temp 中，再把 arr[minIndex] 的值赋给 arr[i]，最后把 temp（即原来 arr[i] 的值）赋给 arr[minIndex]。
4. 重复操作：外层循环不断推进，i 逐步增加，重复上述步骤，直到 i 达到 arr.length - 2，此时整个数组排序完成。

代码如下：

   public static void selectSort(int[] arr) {for (int i = 0; i < arr.length - 1; i++) {int minIndex = i;for (int j = i + 1; j < arr.length; j++) {if (arr[j] < arr[minIndex]) {minIndex = j;}}if (minIndex != i) {int temp = arr[i];arr[i] = arr[minIndex];arr[minIndex] = temp;}}}

时间复杂度：由于使用了两层嵌套循环，无论数组初始状态如何，都需要进行大约 \(n(n - 1)/2\) 次比较，因此时间复杂度为O(n^2).

2.2堆排序

• 堆的逻辑结构是一棵完全二叉树

• 堆的物理结构是一个数组

• 即我们可以将堆看成是一棵完全二叉树的顺序存储

父子节点的关系：

• 我们可以通过数组的下标来确定父子节点的关系，结论如下

• leftchild = parent * 2 + 1

• rightchild = parent * 2 + 2

• parent = (child - 1) / 2

堆的两个特性：

结构性：用数组表示的完全二叉树

有序性：任意节点的关键值是其子树所有节点的最大值（或最小值）

”最大堆(MaxHeap)“，也叫”大顶堆“：最大值，即每棵子树的根节点的值都大等于于其子节点的值

”最小堆(MaxHeap)“，也叫”小顶堆“：最小值，即每棵子树的根节点的值都小于等于其子节点的值

基本思想：将待排序的序列构造成一个堆，使得堆顶元素（大根堆为最大值，小根堆为最小值）是序列中的最大（或最小）元素。然后将堆顶元素与堆的最后一个元素交换位置，此时堆顶元素就是已排序好的最大（或最小）元素，将其从堆中移除，剩下的元素重新调整为一个堆，重复上述过程，直到整个序列都被排序。

算法流程：

1. 构建初始大顶堆

• 大顶堆的特点是每个节点的值都大于或等于其子节点的值。从数组的最后一个非叶子节点开始调整，逐步向前，直到根节点。最后一个非叶子节点的索引为 arr.length / 2 - 1。
• 对于每个非叶子节点，调用 adjustHeap 方法进行调整，确保以该节点为根的子树满足大顶堆的性质。

2. 交换堆顶元素与末尾元素并调整堆

• 将堆顶元素（即最大值）与数组的最后一个元素交换位置。此时，最大值就被放到了数组的末尾，完成了一次排序。
• 缩小堆的范围（排除已经排好序的元素），并对新的堆顶元素调用 adjustHeap 方法，重新调整堆，使其满足大顶堆的性质。
• 重复这个过程，直到堆中只剩下一个元素，此时整个数组就完成了排序。

3. 输出排序结果

• 遍历排序好的数组并输出。

代码如下：

public class HeapSort {// 堆排序主方法public static void heapSort(int[] arr) {// 第一步：构建初始大顶堆// 从最后一个非叶子节点开始调整，最后一个非叶子节点的索引为 arr.length / 2 - 1for (int i = arr.length / 2 - 1; i >= 0; i--) {// 调用 adjustHeap 方法调整以 i 为根节点的子树，使其满足大顶堆的性质adjustHeap(arr, i, arr.length);}// 第二步：交换堆顶元素与末尾元素并调整堆// 从数组的最后一个元素开始，依次与堆顶元素交换for (int i = arr.length - 1; i > 0; i--) {// 交换堆顶元素（最大值）与当前末尾元素int temp = arr[i];arr[i] = arr[0];arr[0] = temp;// 交换后，对新的堆顶元素进行调整，此时堆的范围缩小为 iadjustHeap(arr, 0, i);}// 第三步：输出排序结果// 遍历排序好的数组并输出for (int i = 0; i < arr.length; i++) {System.out.print(arr[i] + " ");}}// 调整堆的方法，确保以 i 为根节点的子树满足大顶堆的性质public static void adjustHeap(int[] arr, int i, int length) {// 保存当前根节点的值int temp = arr[i];// 从当前节点的左子节点开始for (int k = i * 2 + 1; k < length; k = k * 2 + 1) {// 如果右子节点存在且右子节点的值大于左子节点的值if (k + 1 < length && arr[k] < arr[k + 1]) {// 则将 k 指向右子节点k++;}// 如果子节点的值大于保存的根节点的值if (arr[k] > temp) {// 将子节点的值赋给当前根节点arr[i] = arr[k];// 更新当前节点的索引为子节点的索引i = k;} else {// 如果子节点的值小于等于根节点的值，说明已经满足大顶堆的性质，退出循环break;}}// 将保存的根节点的值赋给最终的位置arr[i] = temp;}public static void main(String[] args) {int[] arr = {4, 6, 8, 5, 9};heapSort(arr);}
}

 时间复杂度：向下调整算法AdjustDown()的时间复杂度为O(logN)。自下而上建堆的时间复杂度为O(N)。建堆后排序的时间复杂度为O(NlogN)。因此整个堆排序的时间复杂度为O(NlogN)

3.交换排序

3.1冒泡排序

算法思想：比较相邻元素，如果前面的比后面的元素大，则两元素交换位置。对每一对相邻元素进行比较，大的放后，这样最后的元素将是最大的元素。对越来越少的混乱元素重复上述步骤（最后的元素已经有序，不需比较），直到没有元素需要交换位置。

算法流程：

1. 外层循环控制排序轮数：外层循环使用变量 i 从 0 到 arr.length - 2 进行遍历。i 代表当前进行的排序轮数，总共需要进行 arr.length - 1 轮排序。因为经过 arr.length - 1 轮比较和交换后，数组就会完成排序。
2. 内层循环进行相邻元素比较和交换：
   • 内层循环使用变量 j 从 0 到 arr.length - 1 - i 进行遍历。每一轮排序中，随着 i 的增加，需要比较的元素范围逐渐缩小，因为每一轮排序都会将当前未排序部分的最大元素 “冒泡” 到末尾，所以后面已经排好序的元素不需要再参与比较。
   • 在内层循环中，比较相邻的两个元素 arr[j] 和 arr[j + 1]。如果 arr[j] 大于 arr[j + 1]，说明这两个元素的顺序不符合升序要求，需要进行交换。
   • 交换操作通过临时变量 temp 来完成，先将 arr[j] 的值赋给 temp，再将 arr[j + 1] 的值赋给 arr[j]，最后将 temp（即原来 arr[j] 的值）赋给 arr[j + 1]。
3. 重复操作直至排序完成：
   • 不断重复上述外层循环和内层循环的操作，每一轮排序都会使当前未排序部分的最大元素移动到未排序部分的末尾。经过 arr.length - 1 轮排序后，整个数组就会变成升序排列。

代码如下：

    public static void bubbleSort(int[] arr) {for (int i = 0; i < arr.length - 1; i++) {for (int j = 0; j < arr.length - 1 - i; j++) {if (arr[j] > arr[j + 1]) {int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}}}

时间复杂度：冒泡排序的时间复杂度为O(N^2)

3.2快速排序

基本思想：任取待排序元素序列中的某个元素作为基准值，按照该排序码将待排序集合分割成两个子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

算法流程：

1. 基准条件判断：若 left 小于 right，说明当前子数组元素数量多于 1，需要进行排序；反之则无需排序。
2. 初始化变量：
   • i 初始化为 left，作为左指针。
   • j 初始化为 right，作为右指针。
   • 选取 arr[left] 作为基准值 temp。
3. 分区操作：
   • 当 i 小于 j 时，开展以下操作：
     • 从右向左移动右指针 j，只要 arr[j] 大于等于基准值 temp，就将 j 减 1，直至找到一个小于基准值的元素，然后把该元素赋值给 arr[i]。
     • 从左向右移动左指针 i，只要 arr[i] 小于等于基准值 temp，就将 i 加 1，直至找到一个大于基准值的元素，然后把该元素赋值给 arr[j]。
4. 放置基准值：当 i 与 j 相遇时，把基准值 temp 放到 arr[i] 位置。此时，基准值左边的元素都小于等于它，右边的元素都大于等于它。
5. 递归排序：
   • 对基准值左边的子数组 arr[left] 到 arr[i - 1] 递归调用 quickSort 方法进行排序。
   • 对基准值右边的子数组 arr[i + 1] 到 arr[right] 递归调用 quickSort 方法进行排序。

代码如下：

    public static void quickSort(int[] arr, int left, int right) {if (left < right) {int i = left;int j = right;int temp = arr[left];while (i < j) {while (i < j && arr[j] >= temp) {j--;}arr[i] = arr[j];while (i < j && arr[i] <= temp) {i++;}arr[j] = arr[i];}arr[i] = temp;quickSort(arr, left, i - 1);quickSort(arr, i + 1, right);}}

时间复杂度：平均情况下为 (O(nlogn))，最坏情况下为 (O(n^2))。

4.归并排序

基本思想：归并排序是建立在归并操作上的一种有效的排序算法，该算法是采用分治法的一个非常典型的应用：将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。

• 归并排序首先要对待排序列不断二分，直到分成不可分割的子序列（即只有一个元素的序列，相当于有序）

• 然后，再对有序的子序列不断进行归并操作，最后得到完全有序的序列。

算法流程：

mergeSort 方法（递归分解）

1. 基准条件判断：检查 left 是否小于 right，如果不满足该条件，说明当前子数组只有一个元素或者为空，无需排序，直接返回。
2. 计算中间位置：计算中间索引 mid，将数组分为左右两部分，即 [left, mid] 和 [mid + 1, right]。
3. 递归分解：
   • 对左半部分数组 [left, mid] 递归调用 mergeSort 方法进行排序。
   • 对右半部分数组 [mid + 1, right] 递归调用 mergeSort 方法进行排序。
4. 合并操作：当左右两部分子数组都递归排序完成后，调用 merge 方法将这两个已排序的子数组合并成一个有序数组。

merge 方法（合并子数组）

1. 创建临时数组：创建一个长度为 right - left + 1 的临时数组 temp，用于存储合并后的结果。
2. 初始化索引：
   • i 初始化为 left，表示左子数组的起始索引。
   • j 初始化为 mid + 1，表示右子数组的起始索引。
   • k 初始化为 0，表示临时数组的索引。
3. 比较并合并元素：
   • 使用 while 循环，只要 i 不超过 mid 且 j 不超过 right，就比较 arr[i] 和 arr[j] 的大小。
   • 如果 arr[i] 小于等于 arr[j]，将 arr[i] 放入临时数组 temp 中，并将 i 和 k 分别加 1；否则，将 arr[j] 放入临时数组 temp 中，并将 j 和 k 分别加 1。
4. 处理剩余元素：
   • 当左子数组还有剩余元素时，使用 while 循环将剩余元素依次放入临时数组 temp 中。
   • 当右子数组还有剩余元素时，使用 while 循环将剩余元素依次放入临时数组 temp 中。
5. 复制回原数组：将临时数组 temp 中的元素复制回原数组 arr 中，从索引 left 开始。

代码如下：

// 归并排序主方法，用于递归分解数组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;// 右子数组的起始索引int j = mid + 1;// 临时数组的索引int 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 m = 0; m < temp.length; m++) {arr[left + m] = temp[m];}}

时间复杂度：归并排序的时间复杂度为O(NlogN)

5.基数排序

基本思想：是对于给定的输入序列中的每一个元素x，确定该序列中值小于x的元素的个数（此处并非比较各元素的大小，而是通过对元素值的计数和计数值的累加来确定）。一旦有了这个信息，就可以将x直接存放到最终的输出序列的正确位置上。

算法流程：

1. 找出最大值：遍历数组，找出数组中的最大值 max。这一步是为了确定排序需要进行的轮数，因为需要根据最大值的位数来决定要对每一位进行排序的次数。

2. 确定排序轮数：根据最大值 max 的位数确定排序的轮数。可以通过不断除以 10 来计算位数，例如，如果最大值是 123，那么需要进行 3 轮排序，分别对个位、十位、百位进行排序。

3. 按位排序：从最低位（个位）开始，依次对每一位进行排序，直到最高位。

每一轮排序的具体步骤如下：

初始化计数数组：创建一个长度为 10 的计数数组 count，用于统计每个数字（0 - 9）在当前位上出现的次数。

统计当前位数字的出现次数：遍历数组，对于每个元素，取出其当前位上的数字，将计数数组中对应位置的计数加 1。

计算前缀和：对计数数组进行前缀和计算，即 count[i] = count[i] + count[i - 1]。这样做的目的是为了确定每个数字在排序后数组中的最终位置。

排序元素：创建一个与原数组长度相同的临时数组 result，从后往前遍历原数组，根据当前位上的数字和计数数组，将元素放入临时数组的正确位置，并更新计数数组。

更新原数组：将临时数组 result 中的元素复制回原数组 arr，完成当前位的排序。

代码如下：

public static void radixSort(int[] arr) {// 找出数组中的最大值int max = arr[0];for (int i = 1; i < arr.length; i++) {if (arr[i] > max) {max = arr[i];}}// 对每一位进行排序for (int exp = 1; max / exp > 0; exp *= 10) {countingSort(arr, exp);}}private static void countingSort(int[] arr, int exp) {int[] count = new int[10];int[] result = new int[arr.length];// 统计当前位数字的出现次数for (int i = 0; i < arr.length; i++) {int digit = (arr[i] / exp) % 10;count[digit]++;}// 计算前缀和for (int i = 1; i < 10; i++) {count[i] += count[i - 1];}// 排序元素for (int i = arr.length - 1; i >= 0; i--) {int digit = (arr[i] / exp) % 10;result[count[digit] - 1] = arr[i];count[digit]--;}// 更新原数组for (int i = 0; i < arr.length; i++) {arr[i] = result[i];}}

时间复杂度： 基数排序的时间复杂度为 (O(d * (n + k)))，其中 d 是最大值的位数，n 是数组的长度，k 是基数10.