- 1java 中序列化NotSerializableException问题解决办法_org.spiderflow.core.expression.expressionerror$tem
- 2【24年五一建模比赛A题】_24五一建模a
- 3leetcode在线编程【树专题】_leetcode网页编译
- 4大数据伪分布式安装hadoop、hbase、hive等_基于伪分布hadoop部署hive和hbase
- 5MYSQL 的WITH用法_mysql with
- 6K-means对地震数据进行处理_地震数据聚类分析
- 7零基础入门网络安全学习路线+学习方法（超详细）
- 8带3090显卡的Linux服务器上部署SDWebui_linux安装sdwebui
- 9数据结构实验-顺序表的查找_实验9-1:实现顺序查找的算法 目的:领会顺序查找的过程和算法设计。 内容:编写一个
- 10Typora安装&配置图床工具(picgo)，让你优雅高效的写博客_typora配置图床
基于Java实现的常见排序算法_java计数排序
赞
踩
Java中常见的排序算法包括以下几种：
- 冒泡排序（Bubble Sort）
- 选择排序（Selection Sort）
- 插入排序（Insertion Sort）
- 希尔排序（Shell Sort）
- 快速排序（Quick Sort）
- 归并排序（Merge Sort）
- 堆排序（Heap Sort）
- 计数排序（Counting Sort）
- 桶排序（Bucket Sort）
- 基数排序（Radix Sort）
在面试中，通常会要求候选人对这些排序算法进行简单介绍，并能够手写其中几种排序算法的实现代码，并解释时间复杂度和空间复杂度。另外，面试官还可能会要求候选人分析排序算法的优劣、应用场景等方面的知识。
一：冒泡排序
1.思想
冒泡排序核心思想是重复遍历待排序的数列，每次比较相邻的两个元素，不断交换相邻元素的位置来将最大（或最小）的元素移动到数列的末尾，不断重复这个过程直到整个数列都排好序为止，是一种时间复杂度较高的排序算法。
具体来说，冒泡排序会从数列的起始位置开始，比较第一个元素和第二个元素的大小，如果第一个元素大于第二个元素，就将它们的位置交换；然后继续比较第二个元素和第三个元素的大小，如果第二个元素大于第三个元素，就将它们的位置交换；以此类推，重复这个过程直到最后一个元素，这样一次遍历后，最大的元素就会被移到数列的末尾。接下来，再对剩余的元素进行遍历，重复上述过程，直到整个数列都排好序。
2.使用场景
虽然冒泡排序算法时间复杂度较高，但在某些特定的业务场景中，冒泡排序仍然可以发挥很好的作用。一般来说，当需要对少量元素进行排序时，冒泡排序可以是一个很好的选择。另外，如果输入序列已经接近有序或是部分有序，冒泡排序的效率也可以提高。
以下是一些冒泡排序在业务上的使用场景：
- 对于小规模数据的排序。在数据量较小的情况下，冒泡排序的优势在于代码实现简单，易于理解和调试，而且常数项较小。
- 对于部分有序的数据排序。由于冒泡排序是一种稳定的排序算法，因此当输入序列部分有序时，冒泡排序可以通过减少比较和交换操作来提高效率。
- 在排序过程中需要交换相邻元素的位置。冒泡排序正是通过交换相邻元素的位置来实现排序的，因此在某些业务场景中，需要进行相邻元素位置交换的操作时，冒泡排序可以是一个很好的选择。
3.示例
public class BubbleSort { /** * 时间复杂度：O(n^2) * 空间复杂度：O(1) */ 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; j++) { //这里可以进行优化，由于经过i次之后，最后的的i的元素肯定是已经是有序的，无需在进行对比 for (int j = 0; j < n - 1 - i; j++) { if (arr[j] > arr[j + 1]) { int temp = arr[j + 1]; arr[j + 1] = arr[j]; arr[j] = temp; } } } } /** * 使用了一个swapped变量来记录上一轮是否有交换发生。如果在某一轮中没有任何交换发生，那么说明数组已经有序，排序就可以提前结束了。 * 这个算法的时间复杂度是O(n^2)，但是通过这种方式进行优化，可以使得算法在最优情况下的时间复杂度降为O(n) */ public static void bubbleSort1(int[] arr) { int n = arr.length; boolean swapped = true; for (int i = 0; i < n - 1 && swapped; i++) { swapped = false; for (int j = 0; j < n - 1 - i; j++) { if (arr[j] > arr[j + 1]) { int temp = arr[j + 1]; arr[j + 1] = arr[j]; arr[j] = temp; swapped = true; } } } } private static void print(int[] data) { for (int datum : data) { System.out.print(" " + datum); } System.out.println(); } public static void main(String[] args) { int data[] = new int[]{5, 2, 3, 4, 1, 6, 10, 121, 8}; System.out.println("排序前："); print(data); long startTime = System.nanoTime(); bubbleSort(data); long endTime = System.nanoTime(); System.out.println(String.format("useTime=%d,排序后：", endTime - startTime)); print(data); int data1[] = new int[]{2, 3, 4, 5, 8}; System.out.println("（优化版）排序前："); print(data1); startTime = System.nanoTime(); bubbleSort1(data1); endTime = System.nanoTime(); System.out.println(String.format("useTime=%d,（优化版）排序后：", endTime - startTime)); print(data1); } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
二：选择排序
1.思想
选择排序的基本思想是从未排序的数据中选择最小（或最大）的元素放到已排序的末尾，依次重复，直到所有元素都排序完成。
具体来说，选择排序分为两个步骤：
选择：遍历待排序的数组，每次选择未排序部分的最小值（或最大值），并将其与未排序部分的第一个元素交换位置。
排序：经过一次选择操作后，已排序部分会增加一个元素，未排序部分会减少一个元素。重复进行选择操作，直到未排序部分为空，所有元素都被排序完成。
因为每次选择操作只涉及未排序部分，所以选择排序算法的时间复杂度为 O(n^2)，其中 n 是待排序数组的长度。同时，由于选择排序只需要常数级别的额外空间，因此其空间复杂度为 O(1)。
2.使用场景
选择排序的时间复杂度为 O(n^2)，比起其他排序算法，如快速排序、归并排序等，效率相对较低。因此，对于大规模数据的排序，选择排序并不是最优的选择。但选择排序的实现比较简单，且不需要额外的空间开销，因此在以下场景中，选择排序仍然有着一定的应用价值：
- 小规模数据排序：对于小规模的数据排序，选择排序的时间复杂度相对于其他排序算法并没有太大的优势劣势，但是选择排序的实现比较简单，因此在一些小规模数据排序的场景下，选择排序仍然是一个不错的选择。
- 部分有序的数组：对于部分有序的数组，选择排序的性能要好于随机数组的排序，因为选择排序每次都会选择未排序部分的最小值（或最大值），因此对于部分有序的数组，选择排序可以减少比较的次数和数据的交换次数。
- 内存有限的环境：选择排序不需要额外的空间开销，所以在内存有限的环境中，选择排序可以更好地满足内存限制的要求。
需要注意的是，选择排序不适用于对稳定性有要求的排序场景。因为选择排序每次选择最小（或最大）元素并进行交换，会破坏相同元素的原有顺序，从而导致排序不稳定。
3.示例
/** * <p>Class: SelectionSort</p> * <p>Description: 选择排序</p> * * @author zhouyi * @version 1.0 * @date 2021/1/20 */ public class SelectionSort { public static void selectionSort(int[] arr) { int n = arr.length; //遍历数组，依次取出最小的元素 for (int i = 0; i < n - 1; i++) { //假设当前位置为下标的数组元素是最小的 int minIndex = i; //从当前位置下标的下一下开始对比 for (int j = i + 1; j < n; j++) { if (arr[j] < arr[minIndex]) { //j对应的元素是至今为止最小的元素，因此记住下标位置 minIndex = j; } } //当一轮对比完成以后，已经找到了最小的元素，交换当前位置和最小元素的位置 int temp = arr[minIndex]; arr[minIndex] = arr[i]; arr[i] = temp; } } public static void main(String[] args) { int[] arr = {64, 25, 12, 22, 11}; System.out.println("Original array: " + Arrays.toString(arr)); selectionSort(arr); System.out.println("Sorted array: " + Arrays.toString(arr)); } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
补充：冒泡排序和选择排序的区别？
选择排序和冒泡排序都属于简单排序算法，它们的时间复杂度均为 O(n^2)，但它们的思路和具体实现方式有所不同。
选择排序的核心思想是：每次从未排序的元素中找到最小的元素，将其放到已排序的末尾。具体实现方式为：从第一个元素开始，依次比较未排序的元素，找到其中的最小值，将其与当前位置的元素进行交换。这样，每一次循环结束后，已排序的元素个数加一。
冒泡排序的核心思想是：依次比较相邻的两个元素，将较大（或较小）的元素交换到后面，直到所有的元素都排好序。具体实现方式为：从第一个元素开始，依次比较相邻的两个元素，如果当前元素比下一个元素大（或小），则交换这两个元素的位置。这样，每一次循环结束后，最大（或最小）的元素就会被放到了最后。
因此，选择排序和冒泡排序的主要区别在于选择排序每次找到未排序部分的最小值（或最大值）进行交换，而冒泡排序每次找到相邻的两个元素进行比较和交换。这样选择排序可以更快地将未排序部分的最小值（或最大值）放到已排序部分的末尾，而冒泡排序需要多次比较和交换才能将最大（或最小）值放到正确的位置。
另外，选择排序和冒泡排序都是比较简单的排序算法，但在排序过程中需要频繁地交换元素的位置，因此它们的效率相对较低。对于大规模数据的排序，选择排序和冒泡排序都不是最优的选择。
三：插入排序
1.思想
插入排序的核心思想是将待排序的数组或列表分为已排序区间和未排序区间，依次将未排序区间的元素插入到已排序区间的适当位置，最终完成排序。具体地，插入排序的过程如下：
将第一个元素看作已排序区间，将其余元素看作未排序区间。从未排序区间取出第一个元素，插入到已排序区间的适当位置。
重复第2步，直到未排序区间为空。在插入一个元素时，首先将该元素与已排序区间的最后一个元素进行比较，如果该元素比最后一个元素小（或大），则将最后一个元素后移一位，直到该元素大于（或小于）已排序区间的某一个元素，然后将该元素插入到该元素的后面。
插入排序是一种稳定的排序算法，适用于小规模数据或基本有序的数据。其时间复杂度为 O(n^2)，空间复杂度为 O(1)。
2.使用场景
插入排序的优点是：
- 对于小规模的数据排序表现良好；
- 稳定，不会改变相同元素的相对顺序；
- 在大部分元素已经有序的情况下，排序效率较高。
插入排序的缺点是：
- 时间复杂度较高，对于大规模数据排序效率较低；
- 插入排序的实现比较复杂，需要多次移动元素的位置。
在实际业务场景中，插入排序适用于数据规模较小的排序场景，比如对几十个或者几百个元素进行排序的场景，而对于数据规模较大的排序场景，则需要使用更高效的排序算法。
3.示例
/** * <p>Class: InsertionSort</p> * <p>Description: 插入排序</p> * * @author zhouyi * @version 1.0 * @date 2021/1/20 */ public class InsertionSort { /** * 插入排序 * * @param arr 待排序数组 */ public static void insertionSort(int[] arr) { int n = arr.length; for (int i = 1; i < n; ++i) { // 从第二个元素开始遍历 int key = arr[i]; // 将当前元素存储到 key 中 int j = i - 1; // 已排序元素的最后一个位置 while (j >= 0 && arr[j] > key) { // 将大于 key 的元素向后移动一位 arr[j + 1] = arr[j]; j = j - 1; } arr[j + 1] = key; // 插入 key 到正确位置 } } public static void main(String[] args) { int[] arr = {4, 2, 9, 6, 23, 12, 34, 0, 1}; insertionSort(arr); System.out.println(Arrays.toString(arr)); } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
插入排序的时间复杂度有点高，主要表现在元素的移动和对比，我们可以采用希尔排序对插入排序进行优化。简单了解一下希尔排序和插入排序在思想和算法上的区别：
希尔排序是一种改进的插入排序算法，它的主要思想是将原始数组分割成若干个子序列，对每个子序列进行插入排序，然后逐步缩小子序列的范围，直到整个数组有序为止。希尔排序的特点是能够在一定程度上减少插入排序的元素移动次数，从而提高排序效率。
而插入排序是一种简单直观的排序算法，其主要思想是将一个待排序的数组分成两部分，一部分是已经排序好的数组，另一部分是未排序的数组，然后依次将未排序的数组中的元素插入到已排序的数组中的适当位置，直到整个数组有序为止。插入排序的优点是代码简单易懂，缺点是对于大规模的数据排序效率较低。
总的来说，希尔排序的优点是排序效率比插入排序高，缺点是实现比较复杂。而插入排序的优点是实现简单易懂，缺点是对于大规模数据排序效率较低。根据实际应用的需求，可以选择使用希尔排序或插入排序。
四：希尔排序
1.思想
希尔排序（Shell Sort）是一种改进的插入排序算法，也称为缩小增量排序（Diminishing Increment Sort）。
基本思想：将待排序的数据元素按下标进行分组，分成多个子序列，对每个子序列进行直接插入排序，随着增量逐渐减少，子序列包含的元素越来越多，当增量减至1时，整个序列被分成一组，排序完成。
核心思想：利用插入排序对近乎有序的数据排序时效率高的特点，通过先对间隔较大的元素进行插入排序，然后逐步减小间隔，在每次间隔变小时都对所有元素进行插入排序，最终实现对整个序列的排序。
与插入排序相比，希尔排序的时间复杂度较低，在最坏情况下的时间复杂度为O(n^2)，但在大多数情况下可以达到O(nlogn)的时间复杂度，因此在处理大规模数据时，希尔排序有很好的表现。希尔排序的空间复杂度为O(1)。
2.使用场景
希尔排序是一种时间复杂度较优的排序算法，适用于大量数据的排序，尤其是在内存较小的情况下。它在排序过程中采用逐步分组的策略，通过逐步减小组数，最终使得整个数组可以完成排序。因此，适用于需要排序的数据量较大，但内存较小的情况下，例如排序海量日志数据、数据压缩等场景。
3.示例
/** * <p>Class: ShellSort</p> * <p>Description: 希尔排序</p> * * @author zhouyi * @version 1.0 * @date 2021/1/20 */ public class ShellSort { public static void main(String[] args) { //数组长度是奇数的情况 int[] arr = {12, 34, 54, 2, 3}; System.out.println("原始数组: " + Arrays.toString(arr)); shellSort(arr); System.out.println("希尔排序后的数组: " + Arrays.toString(arr)); //数组长度是偶数的情况 int[] arr1 = {12, 34, 54, 2, 3, 44}; System.out.println("原始数组: " + Arrays.toString(arr1)); shellSort(arr1); System.out.println("希尔排序后的数组: " + Arrays.toString(arr1)); } public static void shellSort(int[] arr) { int n = arr.length; // 初始化 gap，第一次一般是数组长度的一般，可以由我们自己定义 int gap = n / 2; // gap > 0 即n/2>0，因为gap是整数，即n=2 、gap=1时，即gap 缩小到 1 之前，不断进行分组处理，当等于1时最后一轮要进行插入排序 while (gap > 0) { for (int i = gap; i < n; i++) { int temp = arr[i]; int j; for (j = i - gap; j >= 0 && arr[j] > temp; j = j - gap) { arr[j + gap] = arr[j]; } arr[j + gap] = temp; } // 缩小 gap 的值 gap = gap / 2; } } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
注意：
希尔排序主要是在大数据量排序的场景下使用，当数据量很少时，采用希尔排序的性能可能还没插入排序性能好。
五：快速排序
1.思想
快速排序（Quicksort）是一种分治法（Divide and Conquer）的排序算法。它采用了递归的思想，将原始序列分成较小和较大的两个子序列，然后递归地排序两个子序列。具体来说，快速排序的步骤如下：
- 选择一个基准元素（pivot）；
- 将序列中小于基准元素的放到基准元素的左边，大于基准元素的放到基准元素的右边，相同的放到任意一边；
- 对左右两个子序列分别重复步骤1和步骤2，直到子序列的长度为1或0，停止递归。
快速排序的关键是选择一个合适的基准元素，一般可以选择序列的第一个元素或随机选择一个元素作为基准元素。在每次分治过程中，通过比较和交换元素，将序列分成两部分，然后对这两部分分别进行递归排序，最终得到一个有序序列。
快速排序是一种高效的排序算法，因为它的平均时间复杂度为O(nlogn)，且空间复杂度为O(logn)，是内部排序算法中最优秀的算法之一。同时，它也是一种不稳定的排序算法，即相同元素可能在排序后的位置发生变化。
2.使用场景
快速排序在各种排序算法中被广泛应用。由于其快速的执行速度和高效性，它通常被用来在大型数据集上进行排序。快速排序的实现也被用来作为其他算法的组成部分，例如搜索和图形算法。具体应用场景包括排序数据库中的记录、排序大量的日志数据、排序网络中的数据包等等。
3.示例
/** * <p>Class: QuickSort</p> * <p>Description: 快速排序</p> * * @author zhouyi * @version 1.0 * @date 2021/1/20 */ public class QuickSort { public static void main(String[] args) { int[] arr = {10, 7, 8, 9, 1, 5}; int n = arr.length; System.out.println("Original array: " + Arrays.toString(arr)); quickSort(arr, 0, n - 1); System.out.println("Sorted array:" + Arrays.toString(arr)); } public static void quickSort(int[] arr, int low, int high) { if (low < high) { // 按照基准元素将数组分成两部分 int pivotIndex = partition(arr, low, high); // 递归排序左半部分 quickSort(arr, low, pivotIndex - 1); // 递归排序右半部分 quickSort(arr, pivotIndex + 1, high); } } public static int partition(int[] arr, int low, int high) { // 选取最后一个元素作为基准元素 int pivot = arr[high]; // 记录基准元素在排完序后的位置 int i = low - 1; // 遍历数组并将小于基准元素的元素移动到数组的左侧 for (int j = low; j < high; j++) { if (arr[j] < pivot) { i++; swap(arr, i, j); } } // 将基准元素移动到排完序后的位置 swap(arr, i + 1, high); // 返回基准元素在排完序后的位置 return i + 1; } public static void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
六：归并排序
1.思想
归并排序的思想是将待排序数组分为若干个子数组，对每个子数组进行排序，然后合并这些子数组，最终得到完整有序的数组。具体来说，归并排序的实现通常有两种方法：自上而下的递归和自下而上的迭代。
- 自上而下：其核心思想是将待排序数组分成两个子数组，对每个子数组进行排序，然后将两个有序子数组合并成一个有序数组。递归过程中，当子数组的长度小于等于1时，即认为该子数组是有序的，递归到最底层后再逐层合并，最终得到完整有序的数组。
- 自下而上：自下而上的迭代归并排序，与自上而下的递归归并排序的思想相似，也是将待排序数组分成若干个子数组，对每个子数组进行排序，然后合并这些子数组。不同之处在于，自下而上的迭代归并排序是从单个元素开始，先两两合并，再四四合并，以此类推，直到整个数组都被合并为止。
2.使用场景
归并排序适用于对大量数据进行排序的场景，比如在大规模数据的搜索引擎中，需要对大量的搜索结果按照相关性进行排序。此外，在需要稳定排序的场景下，归并排序也是一个很好的选择。但是在数据量比较小的时候，归并排序可能会带来一些额外的开销，如函数调用的开销、内存占用等，从而导致相对于其他排序算法来说，表现不如其他算法。
3.示例
public class MergeSort { // 归并排序的主函数 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 m = 0; m < temp.length; m++) { arr[left + m] = temp[m]; } } // 测试归并排序 public static void main(String[] args) { int[] arr = { 5, 1, 6, 2, 4, 3 }; System.out.println("Original array: " + Arrays.toString(arr)); mergeSort(arr, 0, arr.length - 1); System.out.println("Sorted array:" + Arrays.toString(arr)); } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
可以进一步的优化归并排序算法，采用Tim算法来优化归并排序算法。Tim排序是一种基于归并排序和插入排序的混合排序算法，它可以利用插入排序的优势，针对小规模子序列进行排序，同时利用归并排序的优势，对于大规模序列进行排序。下面是采用Tim算法来优化归并排序的示例代码。
public class TimSort { private static final int MIN_MERGE = 32; private int[] arr; public TimSort(int[] arr) { this.arr = arr; } public void sort() { int n = arr.length; int[] buffer = new int[n / 2 + 1]; int minRun = minRunLength(n); for (int i = 0; i < n; i += minRun) { int end = Math.min(i + minRun - 1, n - 1); insertionSort(i, end); } for (int size = minRun; size < n; size = size << 1) { for (int left = 0; left < n; left += size << 1) { int mid = left + size - 1; int right = Math.min(left + (size << 1) - 1, n - 1); if (mid >= right) { continue; } merge(left, mid, right, buffer); } } } private void merge(int left, int mid, int right, int[] buffer) { int i = left; int j = mid + 1; int k = 0; while (i <= mid && j <= right) { if (arr[i] <= arr[j]) { buffer[k++] = arr[i++]; } else { buffer[k++] = arr[j++]; } } while (i <= mid) { buffer[k++] = arr[i++]; } while (j <= right) { buffer[k++] = arr[j++]; } System.arraycopy(buffer, 0, arr, left, k); } private void insertionSort(int left, int right) { for (int i = left + 1; i <= right; i++) { int temp = arr[i]; int j = i - 1; while (j >= left && arr[j] > temp) { arr[j + 1] = arr[j]; j--; } arr[j + 1] = temp; } } private int minRunLength(int n) { int r = 0; while (n >= MIN_MERGE) { r |= n & 1; n >>= 1; } return n + r; } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
七：堆排序
1.思想
堆排序的思想是将待排序序列看成是一颗完全二叉树，满足堆的性质，即父节点的值总是大于或小于其子节点的值。通过构建一个最大堆或最小堆，将堆顶元素与最后一个元素交换，然后对除去最后一个元素的剩余序列重新构建堆，重复上述步骤直到整个序列有序。
2.使用场景
堆排序适用于需要排序的数据量较大，并且不适合使用其他排序算法（例如快速排序，归并排序等）的情况下。由于堆排序的时间复杂度为 O(nlogn)，空间复杂度O(1)。而且不受输入数据的影响，因此对于大规模数据的排序，堆排序具有很好的效率。
堆排序还适用于需要在排序过程中动态添加和删除元素的场景。由于堆是一个完全二叉树，并且具有“堆性质”，可以通过对堆的操作来实现元素的动态添加和删除。具体来说，可以将要添加或删除的元素插入或删除堆的末尾，并根据需要进行调整，以保证堆的性质不受影响。
在实际应用中，堆排序常常被用于高性能的排序库中，例如 Java 中的 PriorityQueue 类。此外，堆排序还被广泛应用于数据压缩、图像处理等领域。
3.示例
public class HeapSort { public static void main(String[] args) { int[] arr = {4, 6, 8, 5, 9}; System.out.println("Original array: " + Arrays.toString(arr)); heapSort(arr); System.out.println("Sorted array:" + Arrays.toString(arr)); } public static void heapSort(int[] arr) { int temp = 0; // 1.将无序序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆 for (int i = arr.length / 2 - 1; i >= 0; i--) { adjustHeap(arr, i, arr.length); } // 2.将堆顶元素与末尾元素进行交换，将最大元素“沉”到数组末端 // 3.重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。 for (int j = arr.length - 1; j > 0; j--) { // 交换 temp = arr[j]; arr[j] = arr[0]; arr[0] = temp; adjustHeap(arr, 0, j); } } /** * 将以 i 对应的非叶子节点的树调整为大顶堆 * * @param arr 待调整的数组 * @param i 表示非叶子节点在数组中索引 * @param length 表示对多少个元素继续调整，length 是在逐渐减少的 */ public static void adjustHeap(int[] arr, int i, int length) { int temp = arr[i]; // k = i * 2 + 1 k 是 i 节点的左子节点 for (int k = i * 2 + 1; k < length; k = k * 2 + 1) { //说明左子节点的值小于右子节点的值 if (k + 1 < length && arr[k] < arr[k + 1]) { k++; } // 如果子节点大于父节点 if (arr[k] > temp) { arr[i] = arr[k];//把较大的值赋给当前节点 i = k;//!!! i 指向 k,继续循环比较 } else { break;//因为是从下至上调整，所以一旦出现已经比较完毕，就可以直接 break } } // 当 for 循环结束后，我们已经将以 i 为父节点的树的最大值，放在了最顶(局部) arr[i] = temp;//将temp值放到调整后的位置 } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
除了上面的代码实现，还有一种使用PriorityQueue（优先队列）实现堆排序的方式，代码如下：
public class HeapSort1 { public static void main(String[] args) { int[] arr = {4, 1, 6, 3, 8, 5, 7, 2}; System.out.println("Before sorting: " + Arrays.toString(arr)); heapSort(arr); System.out.println("After sorting: " + Arrays.toString(arr)); } public static void heapSort(int[] arr) { PriorityQueue<Integer> pq = new PriorityQueue<>(); for (int num : arr) { pq.offer(num); } for (int i = 0; i < arr.length; i++) { arr[i] = pq.poll(); } } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
这种方式的实现比较简单，只需要创建一个PriorityQueue对象，将数组中的元素全部添加进去，再依次从PriorityQueue中取出元素即可。但是需要注意的是，由于PriorityQueue底层实现是堆。此外，还有二叉堆和斐波那契堆等方法均可实现。
需要注意的是，堆排序的时间复杂度虽然与归并排序相同，但在实际应用中，由于堆排序只需要一个固定大小的辅助空间，因此常数项比归并排序小，因而实际效率可能更高。同时，堆排序也是一种不稳定排序算法，因为交换的元素可能会破坏原本相等的元素之间的相对顺序。
八：计数排序
1.思想
计数排序是一种非比较排序算法，它通过确定每个元素在输入序列中的位置来对序列进行排序。计数排序的基本思想是对每个输入元素x，确定小于x的元素个数。有了这个信息，就可以将x直接放在它在输出序列中的位置上了。
具体来说，计数排序的过程如下：
1.找出待排序的数组中最大和最小的元素；
2.统计数组中每个值为i的元素出现的次数，存入数组C的第i项；
3.对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；
4.反向填充目标数组：将每个元素i放在新数组的第C[i]项，每放一个元素就将C[i]减去1。
计数排序的时间复杂度是O(n+k)，其中n是待排序数组的长度，k是待排序数组中元素的范围（最大值和最小值之差加1）。计数排序的空间复杂度也是O(n+k)，需要额外的计数数组C和输出数组B。当k较大时，计数排序的空间复杂度较高，不适合使用。计数排序的稳定性较好，不需要进行元素的比较，因此适用于对于范围确定的整数进行排序。
注意：
计数排序的时间复杂度是O(n+k)，其中n为待排序元素个数，k为元素取值范围。在元素取值范围不大的情况下，k可以看作是一个常数，此时计数排序的时间复杂度可以近似看作O(n)。但当k非常大时，计数排序的时间复杂度会受到影响，变得较高。
2.使用场景
适用于对于范围确定且数据范围较小的元素排序
3.示例
public class CountingSort { public static void countingSort(int[] arr) { int max = Arrays.stream(arr).max().getAsInt(); // 找到数组中的最大值 int min = Arrays.stream(arr).min().getAsInt(); // 找到数组中的最小值 int[] countArray = new int[max - min + 1]; // 定义计数数组，大小为最大值和最小值的差加1 for (int i = 0; i < arr.length; i++) { countArray[arr[i] - min]++; // 统计元素出现次数 } int z = 0; for (int i = min; i <= max; i++) { while (countArray[i - min] > 0) { // 遍历计数数组，输出结果 arr[z++] = i; countArray[i - min]--; } } } public static void main(String[] args) { int[] arr = {2, 5, 3, 0, 2, 3, 0, 3}; // 待排序数组 countingSort(arr); // 排序 System.out.println(Arrays.toString(arr)); // 输出结果 } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
注：以上代码实现了基本的计数排序，当数组中的最大值和最小值差值较大时，计数数组会浪费很多空间，可以通过优化减小计数数组的空间复杂度。
如何对计数数组进行空间的优化？
public class CountingSort1 { public static void countingSort(int[] array) { if (array.length == 0) { return; } // 1.找到数组中最大值和最小值 int max = array[0], min = array[0]; for (int i = 1; i < array.length; i++) { if (array[i] > max) { max = array[i]; } if (array[i] < min) { min = array[i]; } } // 2.创建桶，记录每个元素出现的次数 int[] bucket = new int[max - min + 1]; Arrays.fill(bucket, 0); for (int i = 0; i < array.length; i++) { bucket[array[i] - min]++; } // 3.对桶中元素进行累加 int sum = 0; for (int i = 0; i < bucket.length; i++) { sum += bucket[i]; bucket[i] = sum; } // 4.创建临时数组，存储排序后的结果 int[] temp = new int[array.length]; for (int i = array.length - 1; i >= 0; i--) { temp[--bucket[array[i] - min]] = array[i]; } // 5.将排序后的结果赋值给原数组 for (int i = 0; i < array.length; i++) { array[i] = temp[i]; } } public static void main(String[] args) { int[] arr = {5, 4, 3, 2, 1}; System.out.println("Before sorting: " + Arrays.toString(arr)); countingSort(arr); System.out.println("After sorting: " + Arrays.toString(arr)); } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
九：桶排序
1.思想
桶排序是一种排序算法，它通过将待排序数据分割成多个“桶”（bucket），将每个“桶”中的数据排序，最后依次将每个“桶”中的数据按顺序合并起来，从而达到排序的目的。
桶排序的基本思想是将要排序的数据分到几个有序的桶里，每个桶里的数据再单独进行排序，最后将每个桶里的数据按照顺序依次取出，组成新的有序序列。
桶排序的过程可以分为以下几步：
1.找到待排序数据中的最大值和最小值，并计算出它们之间的差值，确定桶的数量；
2.根据差值和桶的数量，确定每个桶的数值范围，把待排序数据分别放到对应的桶中；
3.对每个桶中的数据进行排序；
4.将每个桶中的数据按照顺序依次取出，组成新的有序序列。
桶排序和计数排序区别？
桶排序和计数排序都属于线性排序的一种，它们的思想都是将输入的数据分为有限个桶，从而使得每个桶里面的数据都具有相同的特征，再对每个桶的数据进行排序。但是，它们的实现方式略有不同：
计数排序：对每个元素x，统计小于x的元素个数num[x]，然后根据这个统计量将x放到正确的位置上。计数排序只能用在数据范围不大的场景，如果数据范围k比要排序的数据n大很多，就不适用于计数排序了。
桶排序：将区间[0, 1)划分成n个相同的小区间，称为桶，然后将n个输入数分别放到各自的桶中，再对每个桶中的数进行排序。可以理解为将数据映射到桶中，每个桶内部使用快速排序等排序算法排序，然后依次输出。
因此，计数排序适用于元素的取值范围较小，而桶排序适用于元素的取值范围较大，且元素均匀分布的情况。
2.使用场景
桶排序的优点是时间复杂度为O(n)，是一种非常快速的排序算法。但桶排序需要占用较大的内存空间，因此只适用于排序数据较小的情况。
3.示例
public class BucketSort { public static void main(String[] args) { double[] arr = {0.897, 0.565, 0.656, 0.1234, 0.665, 0.3434}; int n = arr.length; System.out.println("Before sorting: " + Arrays.toString(arr)); sort(arr, n); System.out.println("After sorting: " + Arrays.toString(arr)); } public static void sort(double[] arr, int n) { if (n <= 0) { return; } // 创建桶并且初始化 ArrayList<Double>[] bucket = new ArrayList[n]; for (int i = 0; i < n; i++) { bucket[i] = new ArrayList<>(); } // 将数组中元素分配到各个桶中 for (int i = 0; i < n; i++) { int bucketIndex = (int) (arr[i] * n); bucket[bucketIndex].add(arr[i]); } // 对每个桶进行排序 for (int i = 0; i < n; i++) { Collections.sort((bucket[i])); } // 将排好序的桶中元素写回原数组 int index = 0; for (int i = 0; i < n; i++) { for (int j = 0, size = bucket[i].size(); j < size; j++) { arr[index++] = bucket[i].get(j); } } } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
桶排序的主要步骤包括：
1.创建桶并且初始化。
2.将数组中元素分配到各个桶中。
3.对每个桶中的元素进行排序。
4.将排好序的桶中元素写回原数组。
在上面的实现中，我们使用了 ArrayList 来作为桶，因为 ArrayList 可以动态扩展大小，更加灵活。
需要注意的是，桶排序的时间复杂度取决于每个桶中的元素个数和排序算法的时间复杂度，最好的情况是每个桶中只有一个元素，时间复杂度为 O(n)，最坏的情况是所有元素都在一个桶中，时间复杂度为 O(nlogn)。
十：基数排序
1.思想
基数排序是一种非比较型整数排序算法，它的核心思想是将整数按照位数切割成不同的数字，然后按照每个位数分别进行比较排序，最终得到排序结果。
例如，对于一组无序整数数组 [53, 89, 150, 36, 633, 233, 930, 654, 456]，基数排序的步骤如下：
1.找到数组中最大的数，确定需要排序的最大位数
最大数为 930，需要排序的最大位数为 3（个位、十位、百位）
2.根据个位数的大小将所有数分配到 0 到 9 这 10 个桶中
桶 0：无数
桶 1：无数
桶 2：1 个数（233）
桶 3：1 个数（53）
桶 4：1 个数（456）
桶 5：无数
桶 6：2 个数（36, 654）
桶 7：无数
桶 8：1 个数（89）
桶 9：2 个数（150, 930）
3.将所有桶中的数按照顺序依次取出，得到新的一组无序数组
[233, 53, 456, 36, 654, 89, 150, 930]
4.根据十位数的大小将所有数分配到 0 到 9 这 10 个桶中
桶 0：1 个数（36）
桶 1：1 个数（150）
桶 2：2 个数（53, 654）
桶 3：1 个数（233）
桶 4：1 个数（456）
桶 5：无数
桶 6：无数
桶 7：1 个数（930）
桶 8：1 个数（89）
桶 9：无数
5.将所有桶中的数按照顺序依次取出，得到新的一组无序数组
[36, 150, 53, 654, 233, 456, 930, 89]
6.根据百位数的大小将所有数分配到 0 到 9 这 10 个桶中
桶 0：无数
桶 1：1 个数（36）
桶 2：1 个数（53）
桶 3：1 个数（89）
桶 4：1 个数（150）
桶 5：1 个数（233）
桶 6：1 个数（456）
桶 7：无数
桶 8：无数
桶 9：1
2.使用场景
数据范围比较小：基数排序需要根据每个数位来排序，因此对于数据范围比较大的数据，可能需要非常多的桶才能完成排序，导致空间复杂度较高。
1.数据位数比较小：对于每个数据，基数排序需要按照每个位上的数字进行排序，如果数据位数比较大，那么时间复杂度会增加，反之则会减少。
2.数据分布比较均匀：如果数据分布比较均匀，那么基数排序的效率会更高，反之则会变得更低。
3.稳定性要求较高：基数排序是一种稳定排序算法，可以保证相同值的元素排序前后的相对位置不变。
综上所述，基数排序适用于数据范围较小、位数较少、数据分布均匀且稳定性要求较高的场景。
3.示例
/** * <p>Class: RadixSort</p> * <p>Description: 基数排序</p> * * @author zhouyi * @version 1.0 * @date 2020/1/20 */ public class RadixSort { // 获取数组中最大的数 public static int getMax(int[] arr) { int max = arr[0]; for (int i = 1; i < arr.length; i++) { if (arr[i] > max) { max = arr[i]; } } return max; } // 基数排序方法 public static void radixSort(int[] arr) { int max = getMax(arr); // 获取数组中最大的数 // 从个位开始，对数组arr按照"指数"进行排序 for (int exp = 1; max / exp > 0; exp *= 10) { int[] output = new int[arr.length]; // 存储"被排序数据"的临时数组 int[] buckets = new int[10]; // 初始化桶数组 // 将数据出现的次数存储在buckets[]中 for (int i = 0; i < arr.length; i++) { int index = (arr[i] / exp) % 10; buckets[index]++; } // 更改buckets[i]，目的是让更改后的buckets[i]的值，是该数据在output[]中的位置。 for (int i = 1; i < 10; i++) { buckets[i] += buckets[i - 1]; } // 将数据存储到临时数组output[]中 for (int i = arr.length - 1; i >= 0; i--) { int index = (arr[i] / exp) % 10; output[buckets[index] - 1] = arr[i]; buckets[index]--; } // 将排序好的数据赋值给a[] for (int i = 0; i < arr.length; i++) { arr[i] = output[i]; } } } // 测试方法 public static void main(String[] args) { int[] arr = { 53, 3, 542, 748, 14, 214, 154, 63, 616 }; System.out.println("排序前： " + Arrays.toString(arr)); radixSort(arr); System.out.println("排序后： " + Arrays.toString(arr)); }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
基数排序的时间复杂度取决于数据的位数和基数的大小，为O(d(n+k))，其中d是数据的位数，n是数据个数，k是基数的大小。空间复杂度取决于桶的个数，为O(n+k)。通常情况下，基数排序的时间复杂度和空间复杂度都比较稳定，不受数据分布的影响。
上面的代码还可以进一步优化，可以从减少桶的数量、采用位运算的方式来减少内存占用等等。
