比较排序（Comparison-based Sorting）是一种基于元素之间比较操作的排序算法。这类算法通过比较数据之间的大小关系来确定数据的相对顺序，从而完成排序。在我们学习Java算法过程中是一个比较重要的一个排序算法，下面我讲从一些基础简单算法 它们不是最好的算法但是其中的核心思想和思维模式值得我们深入学习。
选择排序（Selection Sort）
选择排序（Selection Sort），是一种简单直观的排序算法。它的基本思想是：首先，在未排序序列中找到最小（或最大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（或最大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
这个过程中，每次选择未排序序列中的最小（或最大）元素，然后与未排序序列的起始元素进行交换，这就是选择排序中的“选择”与“交换”操作。
选择排序的主要优点在于它的实现简单，对于小规模的数据排序来说，效率是可接受的。然而，随着数据规模的增大，选择排序的效率会逐渐降低，因为它的时间复杂度为O(n^2)，在数据量很大时，这会是一个不可忽视的问题。
代码实现：
/** * 选择排序算法的通用实现 O(n^2) * 该方法使用函数式接口进行数据操作，实现了排序算法的核心逻辑<br/> * 缺点：<br/> * 1.效率低：选择排序的时间复杂度为O(n^2)，其中n是待排序元素的数量。这意味着当数据量较大时，选择排序的效率会非常低，不适合用于大规模数据的排序。<br/> * 2.不适合大数据集：由于选择排序的效率低下，当需要排序的数据集非常大时，使用选择排序会导致程序运行缓慢，甚至无法在规定的时间内完成排序任务。<br/> * 3.比较次数多：在排序过程中，选择排序需要进行大量的比较操作来确定最小（或最大）元素的位置。这些比较操作会增加算法的时间复杂度，降低排序效率。<br/> * * @param n 数据集的大小，即需要排序的元素数量 * @param getValue 一个函数，用于根据索引返回对应的元素值 * @param comparator 一个比较器，用于比较元素的大小 * @param callback 一个消费型双参数函数，用于在交换元素时进行回调 * @param <T> 元素的类型 */ private static <T> void select(int n, Function<Integer, T> getValue, Comparator<T> comparator, BiConsumer<Integer, Integer> callback) { // 参数有效性检查 if (getValue == null || comparator == null || callback == null) { throw new IllegalArgumentException("Arguments cannot be null"); } // 确保 n 不超过实际数据长度 if (n <= 0) { return; } // 主循环，遍历每一个元素 for (int i = 0; i < n; i++) { // 假设当前位置i是最小值的索引 int minIndex = i; // 从i+1位置开始遍历，找到真正的最小值索引 for (int j = i + 1; j < n; j++) { T currentValue = getValue.apply(j); T minValue = getValue.apply(minIndex); // 如果当前元素小于最小值，则更新最小值索引 if (comparator.compare(currentValue, minValue) < 0) { minIndex = j; } } // 如果最小值不是当前位置i的元素，则交换它们 if (minIndex != i) { callback.accept(i, minIndex); } } } /** * 对List进行选择排序 O(n^2) * * @param <T> List元素的类型 * @param list 要排序的List * @param comparator 用于比较List元素的Comparator */ public static <T> void selectSort(List<T> list, Comparator<T> comparator) { select(list.size() - 1,list::get, comparator, (currentIndex, minIndex) -> { T temp = list.get(currentIndex); list.set(currentIndex, list.get(minIndex)); list.set(minIndex, temp); }); } /** * 对数组进行选择排序 O(n^2) * * @param <T> 数组元素的类型 * @param array 要排序的数组 * @param comparator 用于比较数组元素的Comparator */ public static <T> void selectSort(T[] array, Comparator<T> comparator) { select(array.length - 1,i -> array[i], comparator, (currentIndex, minIndex) -> { T temp = array[currentIndex]; array[currentIndex] = array[minIndex]; array[minIndex] = temp; }); }
优点
- 实现简单：选择排序的算法逻辑清晰，容易理解和实现。它不需要额外的数据结构来辅助排序，代码量相对较少。
- 空间复杂度低：选择排序是原地排序算法，除了用于交换的临时变量外，不需要额外的存储空间，空间复杂度为O(1)。
- 稳定性要求不高：在某些场景下，如果数据的稳定性（即相等元素的相对顺序）不是主要考虑因素，选择排序是一个可行的选择。
- 适用于小规模数据：对于数据量非常小的情况（如n<5），选择排序的性能可能优于其他更复杂的排序算法。
缺点
- 效率低：选择排序的时间复杂度为O(n^2)，在处理大规模数据集时，其效率较低，不适合用于对性能要求较高的场景。
- 不稳定排序：选择排序是一种不稳定的排序算法，即相等的元素在排序后的相对位置可能会发生变化。
- 交换次数多：在排序过程中，选择排序需要进行多次元素交换，这在一定程度上增加了排序的开销。
适用场景
- 小规模数据集：当数据集规模较小时，选择排序由于其实现简单和空间复杂度低的特点，是一个不错的选择。
- 对稳定性要求不高：如果应用场景中对数据的稳定性要求不高，可以选择使用选择排序。
- 内存受限的环境：在内存资源有限的环境下，由于选择排序不需要额外的存储空间，因此是一个较为合适的选择。
插入排序（Insertion Sort）
插入排序的基本思想是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为O(n^2)。具体来说，就是将数组分为已排序区间和未排序区间，初始时，已排序区间只有一个元素，就是数组的第一个元素。然后，从第二个元素开始，依次将每个元素插入到已排序区间的适当位置，直到整个数组排序完成。
代码实现：
/** * 使用插入排序算法对任意类型的数据进行排序 * 该方法通过提供的函数和比较器，对数据进行操作，实现了通用的插入排序算法<br/> * 缺点：<br/> * 1.时间复杂度：插入排序的平均时间复杂度和最坏时间复杂度均为O(n^2)，其中n是数组的长度。 * 对于大规模数据集，插入排序的效率较低。特别是当数据规模接近或超过10,000个元素时，其性能不如快速排序、归并排序等更高效的算法.<br/> * 2.不适用于已部分排序的数据集：虽然插入排序在数据已经部分排序的情况下效率会比完全随机排序的数据集高一些，但其效率提升并不显著，而且仍然低于专门为此类数据集设计的排序算法（如希尔排序）。<br/> * 3.稳定性差：插入排序在相等的元素之间可能会改变它们的相对顺序，这取决于它们的初始位置和在排序过程中的处理方式。这可能会在一些需要保持元素原始顺序（即稳定性）的场景中引起问题。<br/> * 4.内存使用：虽然插入排序是原地排序算法（即它只需要使用常数级别的额外空间），但在处理大型数据集时，由于其较低的效率，可能会导致较长的执行时间和更高的CPU占用率，间接增加了对系统资源的消耗。<br/> * 5.不适用于链表等非线性数据结构：插入排序最自然的实现方式是在数组上，因为它需要频繁地访问元素的前一个和后一个位置。在链表等非线性数据结构上实现插入排序会变得更加复杂和低效，因为需要额外的时间来找到插入位置。 * * @param length 数据的长度，用于确定排序的范围 * @param getValue 一个函数，用于根据索引返回对应的值 * @param comparator 一个比较器，用于比较两个值的大小 * @param setValue 一个消费函数，用于根据索引和值，设置特定位置的值 * * @throws IllegalArgumentException 如果传入的函数或比较器为null，则抛出该异常 */ private static <T> void insertion(int length, Function<Integer, T> getValue, Comparator<T> comparator, BiConsumer<Integer, T> setValue) { // 空值检查 if (getValue == null || comparator == null || setValue == null) { throw new IllegalArgumentException("Arguments cannot be null"); } // 从第二个元素开始，逐步将元素插入到已排序的序列中 for (int i = 1; i < length; i++) { // 获取当前要插入的元素 T key = getValue.apply(i); // 初始化已排序序列中的最后一个元素的索引 int j = i - 1; // 将arr[i]插入到arr[0...i-1]中已排序的序列中的适当位置 // 为了找到这个适当位置，我们需要将arr[0...i-1]中比arr[i]大的元素都向后移动一位 while (j >= 0 && comparator.compare(getValue.apply(j), key) > 0) { // 向后移动元素 setValue.accept(j + 1, getValue.apply(j)); j--; } // 插入元素到正确的位置 setValue.accept(j + 1, key); } } /** * 对List中的元素进行插入排序 O(n^2) * @param list 需要排序的列表 * @param comparator 一个比较器，用于比较两个值的大小 * @param <T> 列表中元素的类型 */ public static <T extends Comparable<T>> void insertionSort(List<T> list, Comparator<T> comparator) { if (list == null || list.size() <= 1) { return; // 如果列表为空或只有一个元素，则无需排序 } insertion(list.size(),list::get, comparator, list::set); } /** * 对数组中的元素进行插入排序 O(n^2) * @param arr 需要排序的列表 * @param comparator 一个比较器，用于比较两个值的大小 * @param <T> 列表中元素的类型 */ public static <T> void insertionSort(T[] arr, Comparator<T> comparator) { if (arr == null || arr.length < 1) { return; } insertion(arr.length,index -> arr[index], comparator, (index, value) -> { arr[index] = value; }); }
工作原理
- 构建有序序列：初始时，将数组的第一个元素视为已排序序列，其余元素视为未排序序列。
- 逐个插入：从未排序序列中取出第一个元素，与已排序序列中的元素从后向前依次进行比较，找到该元素在已排序序列中的正确位置并插入。
- 重复操作：重复上述步骤，直到未排序序列为空，此时整个数组排序完成。
优点
- 实现简单：插入排序的算法逻辑清晰，代码实现简单。
- 稳定排序：在插入排序过程中，相等元素的相对位置不会改变，因此它是一种稳定排序算法。
- 适用于小规模数据：对于小规模数据或基本有序的数据，插入排序的效率较高。
缺点
- 时间复杂度较高：当数据规模较大时，插入排序的时间复杂度为O(n^2)，排序效率较低。
- 空间复杂度低：插入排序是原地排序算法，不需要额外的存储空间，空间复杂度为O(1)。
适用场景
插入排序不仅适用于算法领域，还可以应用于日常生活中的各种场景。例如，整理桌面上的文件、组织播放列表中的歌曲、规划旅行行程等，都可以运用插入排序的思想来进行排序和整理。
优化策略
- 减少交换次数：在插入过程中，可以通过暂存待插入元素，然后一次性将所有大于待插入元素的元素后移，最后再将待插入元素放入正确位置，从而减少交换次数。
- 使用二分查找：在插入过程中，可以利用二分查找来找到插入位置，而不是逐个比较，这样可以提高插入排序的效率。
- 希尔排序：希尔排序是插入排序的一种更高效的改进版本，它通过引入“增量”的概念，允许交换距离较远的元素，从而加快排序速度。
冒泡排序（Bubble Sort）
冒泡排序（Bubble Sort）是一种简单的排序算法。它的工作原理是通过重复地遍历要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。遍历数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小（或越大）的元素会经由交换慢慢“浮”到数列的顶端。
具体来说，冒泡排序算法会重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小（或越大）的元素会经由交换慢慢“浮”到数列的顶端，就如同水中的气泡一样上升到水面。
冒泡排序的平均时间复杂度和最坏时间复杂度都是O(n^2)，其中n是数组的长度。虽然它的效率不是非常高，但由于其实现简单，因此在数据量不是很大的情况下，或者作为其他排序算法的基准，仍然有一定的应用价值。
代码实现
/** * 泛型冒泡排序算法 O(n^2) * 该方法使用冒泡排序算法对给定的一组元素进行排序<br/> * 缺点：<br/> * 1.效率低：冒泡排序的时间复杂度为O(n^2)，在数据量较大时，其效率会非常低，不适合用于大规模数据的排序。<br/> * 2.不适合大数据集：由于冒泡排序的效率低下，当需要排序的数据集非常大时，其性能会成为瓶颈，严重影响程序的运行效率。<br/> * 3.没有利用数据特性：冒泡排序没有利用数据的任何特性（如已排序部分、逆序部分等），始终按照固定的模式进行遍历和比较，这在一定程度上浪费了计算资源<br/> * 4.比较和交换次数多：在最坏情况下，冒泡排序需要进行n*(n-1)/2次比较和交换操作，这会导致大量的计算开销。<br/> * 优点： 简单易懂算法逻辑简单，易于理解和实现 * * @param n 要排序的元素数量 * @param getValue 一个函数，用于根据索引返回元素的值 * @param comparator 一个比较器，用于比较元素的大小 * @param callback 一个回调函数，用于在元素交换位置时进行调用 * @param <T> 元素的类型 */ private static <T> void bubble(int n, Function<Integer, T> getValue, Comparator<T> comparator, BiConsumer<Integer, Integer> callback) { // 用于检测当前遍历中是否发生了元素交换 boolean swapped; // 检查 n 是否有效 if (n <= 0) { return; // 如果 n 不合法，直接返回 } try { // 外层循环控制遍历的轮数，每轮遍历后，最大的元素会冒泡到正确的位置 for (int i = 0; i < n - 1; i++) { swapped = false; // 内层循环用于遍历元素，并根据比较结果交换相邻元素的位置 for (int j = 0; j < n - i - 1; j++) { // 使用Comparator来比较元素 if (comparator.compare(getValue.apply(j), getValue.apply(j + 1)) > 0) { callback.accept(j, j + 1); swapped = true; } } // 如果在某次遍历中没有发生交换，说明数组已经有序，可以提前结束 if (!swapped) { break; } } } catch (Exception e) { // 异常处理 System.err.println("Error occurred while getting value: " + e.getMessage()); } } /** * 数组冒泡排序方法 O(n^2) * 使用Comparator接口进行元素比较 * * @param arr 待排序的数组 * @param comparator 元素比较器 * * @throws IllegalArgumentException 如果数组或比较器为null，则抛出此异常 */ public static <T> void bubbleSort(T[] arr, Comparator<T> comparator) { // 检查数组和比较器是否为null if (arr == null || comparator == null) { throw new IllegalArgumentException("Array or comparator cannot be null"); } bubble(arr.length, i -> arr[i], comparator, (currentIndex, nextIndex) -> { T value = arr[currentIndex]; arr[currentIndex] = arr[nextIndex]; arr[nextIndex] = value; }); } /** * 对List集合进行冒泡排序 O(n^2) * * @param <T> 元素的类型 * @param list 待排序的List集合 * @param comparator 用于比较元素的Comparator */ public static <T> void bubbleSort(List<T> list, Comparator<T> comparator) { // 检查数组和比较器是否为null if (list == null || comparator == null) { throw new IllegalArgumentException("List or comparator cannot be null"); } bubble(list.size(), list::get, comparator, (currentIndex, nextIndex) -> { T value = list.get(currentIndex); list.set(currentIndex, list.get(nextIndex)); list.set(nextIndex, value); }); }
优点
- 实现简单：冒泡排序的算法逻辑直观易懂，实现起来较为简单，是初学者学习排序算法的良好起点。
- 稳定性：冒泡排序是一种稳定的排序算法，即相等元素的相对顺序在排序前后保持不变。
- 空间复杂度低：冒泡排序是原地排序算法，只需要使用固定的额外空间来存储交换的元素，空间复杂度为O(1)。
- 适用于小规模数据：在数据量较小的情况下，冒泡排序的性能是可以接受的，甚至可能比其他复杂的排序算法更快。
缺点
- 时间复杂度高：冒泡排序的时间复杂度为O(n^2)，在处理大规模数据时效率较低，排序速度较慢。
- 不适用于大型数据集：由于其较高的时间复杂度，冒泡排序在处理大型数据集时可能会消耗大量的计算资源和时间。
- 排序效果依赖初始顺序：冒泡排序的性能在一定程度上受到初始数组顺序的影响。如果初始数组已经接近有序，排序的效率可能会提高；但如果初始数组完全无序，排序的效率会相对较低。
适用场景
冒泡排序适用于小规模数据的排序，特别是当数据量较小或者对排序稳定性有要求时。此外，由于其实现简单，冒泡排序也常用于教育目的或理论研究中。
优化策略
- 设置标志位：在每一轮遍历开始时，设置一个标志位来记录是否发生了元素交换。如果某一轮遍历中没有发生任何交换，说明数组已经完全有序，此时可以提前结束排序过程。
- 记录最后一轮交换的位置：在每一轮遍历中，记录最后一次发生交换的位置。在下一轮遍历时，只需要遍历到这个位置之前的元素即可，因为后面的元素已经是有序的了。
- 改进算法：对于大规模数据的排序，可以考虑使用更高效的排序算法，如快速排序、归并排序等。这些算法在时间复杂度上更优，能够更有效地处理大规模数据（就是别用这个算法啦）。
归并排序（Merge Sort）
归并排序（Merge Sort）是一种基于分治思想的经典排序算法，它通过递归的方式将一个大数组分割成多个小数组，分别对这些小数组进行排序，然后将排序好的小数组合并成一个大的有序数组。它的基本思路是分而治之（Divide and Conquer）。它首先将数组分成两半，对每半部分递归地应用归并排序 在递归的过程中，当区间被划分到只有一个或零个元素时，自然就已经“排序”好了。然后将两个有序的子区间合并成一个有序区间。然后将排序好的两半合并在一起，这个过程一直重复，直到整个数组被排序 合并两个有序数组的过程是归并排序的关键。通常使用双指针技术，在两个有序数组中进行比较和合并操作。
代码实现：
/** * 合并两个已排序的子数组 * * @param arr 数组，包含待合并的子数组 * @param left 左子数组的起始索引 * @param mid 左子数组的结束索引，也是右子数组的起始索引 * @param right 右子数组的结束索引 * @param comparator 元素比较器，用于确定排序顺序 */ private static <T> void merge(T[] arr, int left, int mid, int right, Comparator<T> comparator) { // 检查索引的有效性，确保它们按逻辑顺序 if (left > mid || mid > right) { throw new IllegalArgumentException("Invalid indices: left=" + left + ", mid=" + mid + ", right=" + right); } // 创建一个临时数组，用于存储合并后的子数组 T[] temp = (T[]) Array.newInstance(arr.getClass().getComponentType(), right - left + 1); // 初始化指针 i、j 和 k 分别指向左子数组、右子数组和临时数组的起始位置 int i = left, j = mid + 1, k = 0; // 合并两个已排序的部分 while (i <= mid && j <= right) { // 根据比较器的结果，决定从哪个子数组复制元素到临时数组 if (comparator.compare(arr[i], arr[j]) <= 0) { temp[k++] = arr[i++]; } else { temp[k++] = arr[j++]; } } // 复制左子数组中剩余的元素，如果有的话 while (i <= mid) { temp[k++] = arr[i++]; } // 复制右子数组中剩余的元素，如果有的话 while (j <= right) { temp[k++] = arr[j++]; } // 将排序后的元素从临时数组复制回原数组 for (i = left, k = 0; i <= right; i++, k++) { arr[i] = temp[k]; } } /** * 使用归并排序算法对数组进行排序 O(n) ～ O(n log n) * 归并排序是一种分而治之的算法，它将数组分成两半，分别排序，然后合并<br/> * 具体步骤可以细分为以下几步：<br/> * 1.分解：将数组分解成两个较小的子数组，直到子数组的大小为1，此时子数组自然是有序的。<br/> * 2.递归排序：递归地对每个子数组进行归并排序。<br/> * 3.合并：将两个已排序的子数组合并成一个有序的数组。这是归并排序中最关键的一步，需要比较两个子数组的元素，并依次将它们放入一个新的数组中，以保证合并后的数组是有序的。<br/> * 4.回溯：在合并过程中，随着子数组的不断合并，最终会形成一个完整的、有序的数组<br/> * 缺点： * 1.较高的空间复杂度：归并排序在合并过程中需要创建一个与原始数组大小相同的临时数组来存储中间结果。这意味着归并排序的空间复杂度是O(n)，其中n是数组的长度。如果考虑递归调用栈的空间，最坏情况下的空间复杂度将达到O(n log n)。 * 这种额外的空间需求在处理大规模数据集时可能会成为问题，尤其是当内存资源有限时。<br/> * 2.递归深度可能导致的栈溢出: 归并排序是一种递归算法，对于深度较大的递归调用，如果系统分配给递归调用的栈空间不足，可能会导致栈溢出错误。 * 虽然现代操作系统和编程语言通常提供了足够大的栈空间来避免这种情况，但在某些极端情况下或特定环境中，这仍然是一个潜在的问题。<br/> * 3.不适用于小数据集：对于非常小的数据集，归并排序的额外空间开销和递归调用开销可能会使得其性能不如一些简单的排序算法（如插入排序或选择排序）。在这些情况下，使用归并排序可能会浪费资源并降低效率。<br/> * 4.实现复杂度较高：相对于一些简单的排序算法，归并排序的实现较为复杂。它涉及到递归调用、数组分割和合并等多个步骤，需要较高的编程技巧和错误处理能力。因此，在需要快速实现排序功能的场景中，归并排序可能不是最佳选择。 * @param arr 数组，可以是任何类型 * @param left 数组左边界索引 * @param right 数组右边界索引 * @param comparator 用于比较数组元素的比较器 * @param <T> 泛型参数，表示数组元素的类型 */ public static <T> void mergeSort(T[] arr, int left, int right, Comparator<T> comparator) { // 检查数组和比较器是否为null if (arr == null || comparator == null) { throw new IllegalArgumentException("Array or comparator cannot be null"); } if (left < 0 || right > arr.length - 1) { throw new IllegalArgumentException("Invalid indices: left=" + left + ", right=" + right + ", arr length=" + arr.length); } // 检查左索引是否大于右索引 if (left > right) { throw new IllegalArgumentException("Left index cannot be greater than right index"); } // 如果左索引小于右索引，说明数组至少有两个元素，需要排序 if (left < right) { // 计算中间索引 int mid = left + (right - left) / 2; // 递归地对两半进行排序 mergeSort(arr, left, mid, comparator); mergeSort(arr, mid + 1, right, comparator); // 合并两半 merge(arr, left, mid, right, comparator); } } /** * 使用归并排序算法对数组进行排序 O(n) ～ O(n log n) * 归并排序是一种分而治之的算法，它将数组分成两半，分别排序，然后合并 * * @param arr 数组，可以是任何类型 * @param comparator 用于比较数组元素的比较器 * @param <T> 泛型参数，表示数组元素的类型 */ public static <T> void mergeSort(T[] arr, Comparator<T> comparator) { if (arr == null || comparator == null) { return; } mergeSort(arr, 0 ,arr.length - 1, comparator); }
优点
- 高效性：归并排序的时间复杂度为O(n log n)，这是基于比较的排序算法所能达到的理论最优时间复杂度，确保了算法的高效性。
- 稳定性：归并排序是一种稳定的排序算法，即相等元素的相对顺序在排序后保持不变。这一特性在某些需要保持元素原始顺序的场景中非常重要。
- 适用大数据量：由于归并排序的高效性和稳定性，它特别适用于处理大数据量的排序任务。
- 外部排序：归并排序也是常用的外部排序方法，当数据存储在外部存储器（如硬盘）上，且内存不足以一次性加载所有数据时，归并排序可以通过分批加载数据并进行排序合并的方式，有效地完成外部排序。
缺点
- 空间复杂度较高：归并排序需要额外的存储空间来存储合并过程中的临时数组，其空间复杂度为O(n)，这在内存资源有限的情况下可能会成为限制因素。
- 递归实现可能导致栈溢出：虽然归并排序的递归实现简洁易懂，但深层递归可能会导致栈溢出，特别是在处理极大规模数据时。
适用场景
归并排序适用于需要高效、稳定排序的场景，特别是当数据量较大时。它也被广泛应用于数据库管理系统、文件系统等需要处理大量数据的系统中。
可能遇到的问题
- 内存限制：在处理极大规模数据集时，归并排序所需的额外存储空间可能会超过系统的内存限制，导致性能下降或程序崩溃。
- 递归深度限制：在某些编程语言或环境中，递归深度可能受到限制，导致归并排序无法完成深层递归。
优化策略
- 迭代替代递归：为了避免递归带来的栈溢出问题，可以使用迭代版本的归并排序。迭代版本通过手动维护一个栈或使用其他数据结构来模拟递归过程，从而减少对系统栈的依赖。
- 减少内存使用：在内存资源有限的情况下，可以尝试优化归并排序的内存使用。例如，通过减小临时数组的大小或采用原地归并排序（虽然实现复杂且可能影响性能）来减少内存占用。
- 并行化：利用现代多核处理器的并行计算能力，可以将归并排序并行化以提高排序速度。通过将数据集分成多个块并并行排序这些块，然后在主线程中合并结果，可以显著减少排序所需的总时间。
堆排序（Heap Sort）
堆排序（Heap Sort）是一种利用堆这种数据结构所设计的排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质，即子节点的键值或索引总是小于（或大于）它的父节点。堆排序算法通过构建堆，并在堆的基础上进行排序操作，以达到将无序数组排序成有序数组的目的。
堆的定义与性质
- 堆：堆是一种特殊的完全二叉树结构，其中每个父节点的值都大于或等于（最大堆）或小于或等于（最小堆）其子节点的值。
- 性质：堆总是满足完全二叉树的性质，即除了最后一层外，每一层都被完全填满，且所有节点都尽可能地向左对齐。
堆排序的基本步骤
堆排序算法主要包括两个核心步骤：构建堆和排序调整。
- 构建堆：将无序的数组构造成一个堆（最大堆或最小堆），使得数组中的最大（或最小）元素位于堆顶（即数组的起始位置）。
- 排序调整：将堆顶元素（即当前最大或最小元素）与数组的末尾元素交换，然后减小堆的大小（即不考虑已排序的末尾元素），并重新调整剩余元素为堆。重复此过程，直到整个数组有序。
Java的
PriorityQueue类内部是基于堆（通常是最小堆）实现的，虽然不是直接使用堆排序算法进行排序，但其插入、删除和获取最大（或最小）元素的操作都依赖于堆的性质，这些操作在内部可能涉及到堆的调整，类似于堆排序中的建堆和调整堆的过程代码实现：
/** * 堆排序算法 O(n log n) * 使用最大堆进行排序，先构建最大堆，然后交换堆顶和末尾元素，逐步缩小堆的大小，直到整个数组有序<br/> * 优点: <br/> * 1.效率高：堆排序的时间复杂度为O(n log n)，这使得它在处理大规模数据集时具有较高的效率。 <br/> * 2.空间复杂度低：堆排序是原地排序，除了递归调用栈（如果使用递归实现的话）外，不需要额外的存储空间，空间复杂度为O(1)。 <br/> * 3.稳定性能：堆排序的性能稳定，无论数据的初始状态如何，其时间复杂度都能保持在O(n log n)。 <br/> * 4.支持并发执行：堆排序可以并行化，利用多线程来加速排序过程，适用于需要高性能排序的并发场景。 <br/> * 5.灵活性强：堆排序可以方便地通过调整堆（大顶堆或小顶堆）来实现升序或降序排序。 <br/> * 缺点：<br/> * 1.不稳定排序：堆排序是一种不稳定的排序算法，即相等的元素在排序后的相对位置可能会发生变化。 * 2.对小规模数据集不高效：对于小规模数据集或已经部分有序的数据集，堆排序可能不是最优选择，因为其他排序算法（如插入排序或快速排序）在这些情况下可能具有更好的性能。 * @param array 待排序的数组，可以是任意类型，但需要实现Comparable接口或传入Comparator * @param comparator 比较器，用于比较数组中的元素，可以是匿名内部类实现或lambda表达式 */ public static <T> void heapSort(T[] array, Comparator<T> comparator) { // 如果数组为空或只有一个元素，则不需要排序，直接返回 if (array == null || array.length <= 1) { return; } // 构建最大堆 // 从最后一个非叶子节点开始，自下而上，自右至左调整每个节点，确保以每个节点为根的子树都是最大堆 for (int i = array.length / 2 - 1; i >= 0; i--) { shiftDown(array, i, array.length, comparator); } // 一个个从堆顶取出元素，并重新调整堆 // 每次将堆顶元素（当前最大值）与末尾元素交换，然后重新调整剩余部分为最大堆 for (int i = array.length - 1; i > 0; i--) { // 交换堆顶和末尾元素 T temp = array[0]; array[0] = array[i]; array[i] = temp; // 重新调整剩余部分为最大堆 shiftDown(array, 0, i, comparator); } } /** * 将指定索引的元素在堆中向下调整，以满足堆属性 * * @param array 存储元素的数组，同时也是堆的表示 * @param index 需要向下调整的元素的索引 * @param heapSize 堆的大小，即参与调整的有效元素数量 * @param comparator 比较器，用于定制元素的比较规则 */ private static <T> void shiftDown(T[] array, int index, int heapSize, Comparator<T> comparator) { // 参数校验 if (array == null || comparator == null) { throw new IllegalArgumentException("Array and comparator cannot be null."); } // 根据 heapSize 选择使用递归还是迭代 if (heapSize > 100) { // 这里的 100 是一个示例阈值，可以根据实际情况调整 shiftDownIterative(array, index, heapSize, comparator); } else { shiftDownRecursive(array, index, heapSize, comparator); } } /** * 迭代实现的向下调整方法 * * @param array 存储元素的数组，同时也是堆的表示 * @param index 需要向下调整的元素的索引 * @param heapSize 堆的大小，即参与调整的有效元素数量 * @param comparator 比较器，用于定制元素的比较规则 */ private static <T> void shiftDownIterative(T[] array, int index, int heapSize, Comparator<T> comparator) { while (true) { int largest = index; int left = 2 * index + 1; int right = 2 * index + 2; // 如果左子节点大于根节点 if (left < heapSize && comparator.compare(array[left], array[largest]) > 0) { largest = left; } // 如果右子节点是最大的 if (right < heapSize && comparator.compare(array[right], array[largest]) > 0) { largest = right; } // 如果最大不是根节点，交换它们 if (largest != index) { T temp = array[index]; array[index] = array[largest]; array[largest] = temp; // 继续向下调整受影响的子树 index = largest; } else { // 如果当前节点已经是最大节点，停止调整 break; } } } /** * 递归实现的向下调整方法 * * @param array 存储元素的数组，同时也是堆的表示 * @param index 需要向下调整的元素的索引 * @param heapSize 堆的大小，即参与调整的有效元素数量 * @param comparator 比较器，用于定制元素的比较规则 */ private static <T> void shiftDownRecursive(T[] array, int index, int heapSize, Comparator<T> comparator) { int largest = index; int left = 2 * index + 1; int right = 2 * index + 2; // 如果左子节点大于根节点 if (left < heapSize && comparator.compare(array[left], array[largest]) > 0) { largest = left; } // 如果右子节点是最大的 if (right < heapSize && comparator.compare(array[right], array[largest]) > 0) { largest = right; } // 如果最大不是根节点，交换它们 if (largest != index) { T temp = array[index]; array[index] = array[largest]; array[largest] = temp; // 递归地堆化受影响的子树 shiftDownRecursive(array, largest, heapSize, comparator); } }
优点
- 时间效率高：堆排序的平均时间复杂度和最坏时间复杂度均为O(n log n)，其中n是数组的长度。这使得堆排序在处理大数据集时具有较高的效率。
- 空间复杂度低：堆排序是原地排序算法，除了几个临时变量外，不需要额外的存储空间。这使得堆排序在空间使用上非常高效。
- 适用性广：堆排序可以应用于各种数据类型，只要能够为这些数据类型定义合适的比较操作。
- 支持动态维护：堆排序可以高效地支持动态维护最大（或最小）元素，适用于需要频繁查询最大（或最小）元素的场景。
缺点
- 不稳定性：堆排序是一种不稳定的排序算法，即相等的元素在排序后可能会改变其相对顺序。这对于需要保持元素原始顺序的应用场景来说可能是一个缺点。
- 最坏情况性能：虽然平均时间复杂度为O(n log n)，但在最坏情况下（如输入数据完全逆序），堆排序的时间复杂度可能退化为O(n^2)。然而，在实际应用中，这种情况较为罕见。
适用场景
- 大数据集排序：堆排序在处理大数据集时具有较高的效率，适用于需要快速排序大量数据的场景。
- 优先队列：堆排序是构建优先队列的一种常用方法，可以高效地支持插入、删除和获取最大（或最小）元素的操作。
- 动态数据维护：在需要动态维护最大（或最小）元素的场景中，堆排序可以高效地实现这一功能。
可能遇到的问题
- 内存使用：虽然堆排序的空间复杂度较低，但在处理极大规模数据时，仍需注意内存使用情况，以避免内存溢出。
- 稳定性需求：对于需要保持元素原始顺序的应用场景，堆排序可能不是最佳选择。
优化策略
- 选择合适的堆类型：根据具体排序需求选择合适的堆类型（最大堆或最小堆），以提高算法效率。
- 减少比较次数：通过优化算法逻辑，减少不必要的比较操作，以降低时间复杂度。
- 使用多线程：在现代多核处理器上，可以通过多线程并行计算来进一步提高堆排序的性能。
- 外部排序：对于无法一次性加载到内存中的大数据集，可以采用外部排序算法，将数据分成多个小块进行排序，然后再合并这些有序块。
