全面掌握 Java 排序算法：从原理到代码实现

这篇文章介绍了全面掌握 Java 排序算法：从原理到代码实现，分享给大家做个参考，收藏Java资料网收获更多编程知识

全面掌握 Java 排序算法：从原理到代码实现

一、基本概念

排序算法用于将一组数据按指定顺序排列（通常是升序或降序）。在评估排序算法时，通常需要考虑以下几个方面：

1.1 什么是排序算法

排序算法是一种对数据集合按照某种特定顺序进行重新排列的过程，主要应用在数据处理、查找优化等场景。

1.2 排序算法的评估标准

• 时间复杂度：算法处理 n 个元素时所需的时间，例如 O ( n 2 ) O(n^2) O(n2) 表示随着输入量增长，处理时间呈平方增长。
• 空间复杂度：算法在执行过程中需要的额外内存使用量。
• 稳定性：相等的元素在排序后是否保持相对位置不变。

1.3 现实应用场景

• 插入排序：适用于少量数据或近乎有序的数据。
• 归并排序：适用于大规模数据的排序，尤其是外部排序。

二、插入排序

2.1 算法简介

插入排序通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到合适位置并插入。

2.2 算法步骤

1. 从第二个元素开始遍历数组。
2. 将当前元素与之前的元素进行比较，并将其插入到合适位置。

2.3 代码示例

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;
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key; // 插入元素
        }
    }
}

2.4 算法分析

• 时间复杂度： O ( n 2 ) O(n^2) O(n2)，在最坏情况下需要进行 n 2 n^2 n2 次比较。
• 空间复杂度：$O(1)$，只需常数级别的额外空间。
• 稳定性：稳定。

三、交换排序

3.1 冒泡排序

冒泡排序通过比较相邻元素并交换位置，将最大或最小元素逐步移动到序列的末尾。

3.2 代码示例

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 - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }
}

3.3 快速排序（QuickSort）

快速排序是一种基于分治思想的高效排序算法，通过选取一个基准元素，将数组分为较小和较大两部分递归排序。

3.4 代码示例

public class QuickSort {
    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);
        }
    }

    private 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++;
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;
        return i + 1;
    }
}

3.5 算法分析

• 时间复杂度：平均 $O(n\log n)$，最坏情况下退化为 O ( n 2 ) O(n^2) O(n2)。
• 空间复杂度：$O(\log n)$。
• 稳定性：不稳定。

四、选择排序

4.1 选择排序简介

选择排序通过在未排序部分中选择最小元素，将其放在已排序序列的末尾。

4.2 代码示例

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]) {
                    minIndex = j;
                }
            }
            int temp = arr[minIndex];
            arr[minIndex] = arr[i];
            arr[i] = temp;
        }
    }
}

4.3 算法分析

• 时间复杂度： O ( n 2 ) O(n^2) O(n2)。
• 空间复杂度：$O(1)$。
• 稳定性：不稳定。

4.4 扩展：堆排序

堆排序是一种基于二叉堆结构的选择排序，时间复杂度为 $O(n\log n)$。

五、归并排序

5.1 归并排序简介

归并排序采用分治法，将数组递归拆分为小数组，再将其合并为有序数组。

5.2 代码示例

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);
        }
    }

    private 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) {
            temp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
        }
        while (i <= mid) {
            temp[k++] = arr[i++];
        }
        while (j <= right) {
            temp[k++] = arr[j++];
        }
        System.arraycopy(temp, 0, arr, left, temp.length);
    }
}

5.3 算法分析

• 时间复杂度：$O(n\log n)$。
• 空间复杂度：$O(n)$。
• 稳定性：稳定。

---

六、 Java 排序算法底层实现解析

1. Java Arrays.sort() 内部实现机制

Arrays.sort() 是 Java 提供的用于排序数组的方法。根据数据类型的不同，其底层采用不同的排序算法。

1.1 基本数据类型（int[], double[], char[] 等）

• 算法：双轴快速排序（Dual-Pivot QuickSort）
• 时间复杂度：$O(n\log n)$
• 空间复杂度：$O(\log n)$（递归调用栈的深度）
• 稳定性：不稳定，相等元素的相对位置可能会发生变化。

什么是双轴快速排序？

双轴快速排序是经典快速排序的优化版本，由 Yaroslavskiy 提出并应用于 JDK 7 及更高版本。它通过选取两个基准点（pivot1 和 pivot2），将数组划分为三个区间：

1. 小于 pivot1 的元素区间
2. 介于 pivot1 和 pivot2 之间的元素区间
3. 大于 pivot2 的元素区间

工作原理

1. 从数组中选取两个基准点 pivot1 和 pivot2，并确保 pivot1 <= pivot2。
2. 遍历数组，将元素根据值分配到三个子区间。
3. 对三个子数组递归调用双轴快速排序。

代码示例：简化版双轴快速排序

public class DualPivotQuickSort {
    public static void sort(int[] arr, int low, int high) {
        if (low < high) {
            int[] pivots = partition(arr, low, high);
            sort(arr, low, pivots[0] - 1);  // 对左部分排序
            sort(arr, pivots[0] + 1, pivots[1] - 1);  // 对中间部分排序
            sort(arr, pivots[1] + 1, high);  // 对右部分排序
        }
    }

    private static int[] partition(int[] arr, int low, int high) {
        if (arr[low] > arr[high]) {
            swap(arr, low, high);  // 确保 pivot1 <= pivot2
        }
        int pivot1 = arr[low], pivot2 = arr[high];
        int i = low + 1, j = high - 1, k = low + 1;

        while (k <= j) {
            if (arr[k] < pivot1) {
                swap(arr, k, i++);
            } else if (arr[k] > pivot2) {
                swap(arr, k, j--);
                k--;  // 重新比较当前位置
            }
            k++;
        }
        swap(arr, low, --i);
        swap(arr, high, ++j);
        return new int[]{i, j};
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

双轴快速排序优点

• 使用两个基准点减少了递归深度和比较次数，性能优于单轴快速排序。
• 实验表明，对于大多数输入，双轴快速排序的性能比单轴快速排序快约 10-30%。

---

1.2 对象类型（Integer[], String[], List<T> 等）

• 算法：TimSort（归并排序与插入排序的混合算法）。
• 时间复杂度：$O(n\log n)$。
• 空间复杂度：$O(n)$。
• 稳定性：稳定，相等元素的相对顺序保持不变。

---

2. Collections.sort() 内部实现机制

Collections.sort() 是用于排序 List 类型数据的静态方法，其内部实际上调用了 List 的 toArray 方法将 List 转换为数组，并调用 Arrays.sort()。因此，Collections.sort() 同样使用了 TimSort 算法。

---

3. TimSort 算法详解

3.1 TimSort 是什么？

TimSort 是一种基于归并排序和插入排序的优化算法，由 Tim Peters 于 2002 年提出。Java 和 Python 的内置排序方法都采用了 TimSort。它专为真实数据设计，能够识别并利用数组中的部分有序性。

3.2 工作原理

1. 划分最小运行段（Run）：将数组划分为若干小段（Run），这些小段要么升序要么降序。
2. 合并小段：将这些小段使用归并排序的方式进行合并，确保整体有序。

插入排序在 TimSort 中的作用

• 对于长度较小的段，TimSort 使用插入排序进行排序，因为插入排序在小数组中性能优异，开销低。

示意图

初始数组：[5, 1, 4, 7, 9, 2, 3]
→ Run 1：[5, 1]（长度小于阈值，使用插入排序）
→ Run 2：[4, 7, 9]（已排序段）
→ 合并 Run：[1, 5] 和 [4, 7, 9] → [1, 4, 5, 7, 9]
→ 最终排序完成：[1, 2, 3, 4, 5, 7, 9]

---

3.3 Java 示例

虽然 Arrays.sort() 封装了 TimSort 算法，但我们可以使用其 API 演示：

import java.util.Arrays;

public class TimSortExample {
    public static void main(String[] args) {
        int[] arr = {5, 3, 1, 4, 6, 2};
        Arrays.sort(arr);  // 内部使用 TimSort
        System.out.println(Arrays.toString(arr));  // 输出：[1, 2, 3, 4, 5, 6]
    }
}

---

4. TimSort 的优点与应用场景

• 部分有序优化：如果输入数组已部分有序，TimSort 可以检测并减少不必要的排序操作。
• 稳定性：TimSort 是稳定排序，适用于需要保持元素顺序的场景。

应用场景

• 需要稳定排序时使用 Collections.sort() 和 Arrays.sort()，如对 List<Employee> 按工资排序，若工资相同则保持原序。
• 适合包含部分有序数据的场景，如时间序列数据处理等。

---

总结

Java 的 Arrays.sort() 和 Collections.sort() 通过底层算法优化为大多数排序场景提供了高效解决方案。理解这些底层机制有助于我们在实际开发中根据数据特性选择合适的排序方法，提高程序的性能和可读性。

七、总结与比较

1. 排序算法性能概览

在实际开发中，不同排序算法在小规模和大规模数据集上的表现存在显著差异。为了直观地展示这些差异，可以通过图表和代码测试进行比较。

1.1 时间复杂度曲线说明

目标：帮助读者理解不同排序算法在不同数据规模下的性能表现。

• 横轴：数据集规模（元素数量）。
• 纵轴：执行时间（毫秒/ms）。
• 不同曲线：表示插入排序、快速排序、归并排序等算法的性能曲线。

示例曲线解读

1. 插入排序/冒泡排序（ O ( n 2 ) O(n^2) O(n2)）：表现为抛物线型上升，数据规模较大时性能急剧下降。
2. 快速排序（$O(n\log n)$）：呈现出对数线性增长曲线，处理大数据集时性能优于简单排序算法。
3. 归并排序（$O(n\log n)$）：在大多数情况下表现接近快速排序，但略低于优化后的快速排序。
4. TimSort：在部分有序数据集上性能表现更优。

1.2 折线图示意

数据规模 →  [100]  [500]  [1000]  [5000]  [10000]  [50000]  
执行时间 ↓
    |                *  快速排序
10ms|             *
    |       *       *
20ms| *   插入排序
    |  *
    |—————————————————————————

2. 实验数据与实现方式

通过实验测量各个算法在不同数据规模下的表现可以直观了解时间复杂度的影响。

2.1 Java 基准测试代码示例

以下示例代码生成随机数组，并分别使用不同排序算法对其排序，记录执行时间：

import java.util.Arrays;
import java.util.Random;

public class SortBenchmark {
    public static void main(String[] args) {
        int[] dataSizes = {100, 500, 1000, 5000, 10000, 50000};
        for (int size : dataSizes) {
            int[] arr = generateRandomArray(size);
            benchmarkSorts(arr);
        }
    }

    private static int[] generateRandomArray(int size) {
        Random random = new Random();
        int[] arr = new int[size];
        for (int i = 0; i < size; i++) {
            arr[i] = random.nextInt(size * 10);  // 随机生成数据
        }
        return arr;
    }

    private static void benchmarkSorts(int[] arr) {
        int[] arrCopy;

        arrCopy = Arrays.copyOf(arr, arr.length);
        System.out.println("数据集大小：" + arr.length);
        
        long start = System.nanoTime();
        InsertionSort.insertionSort(arrCopy);  // 插入排序
        System.out.println("插入排序耗时：" + (System.nanoTime() - start) / 1e6 + " ms");

        arrCopy = Arrays.copyOf(arr, arr.length);
        start = System.nanoTime();
        QuickSort.quickSort(arrCopy, 0, arrCopy.length - 1);  // 快速排序
        System.out.println("快速排序耗时：" + (System.nanoTime() - start) / 1e6 + " ms");

        arrCopy = Arrays.copyOf(arr, arr.length);
        start = System.nanoTime();
        Arrays.sort(arrCopy);  // TimSort
        System.out.println("TimSort 耗时：" + (System.nanoTime() - start) / 1e6 + " ms");

        System.out.println("---------------------------");
    }
}

3. 数据可视化示例

通过表格或图表展示实验结果，可以帮助读者直观理解各算法的表现。

3.1 小规模数据集（100-500 个元素）

排序算法	时间（ms）
插入排序	10 ms
冒泡排序	11 ms
快速排序	3 ms
TimSort	2.5 ms

解读：在小规模数据时，插入排序和冒泡排序的性能尚可，但明显不如快速排序和TimSort。

3.2 大规模数据集（10000 个元素）

排序算法	时间（ms）
插入排序	300 ms
冒泡排序	320 ms
快速排序	25 ms
TimSort	20 ms

解读：在大规模数据时，插入排序和冒泡排序的时间迅速增长，而快速排序和TimSort表现稳定。

4. 总结与建议

• 小数据集：插入排序和冒泡排序适用于少量元素排序，简单直接。
• 大数据集：快速排序和 TimSort 在大规模数据处理时表现优异。
• 对稳定性有要求：选择 TimSort。
• 部分有序数据：TimSort 可以识别并优化部分有序数组，避免不必要的排序操作。

通过合理选择合适的排序算法，可以大幅提升程序的性能。在实际项目中，应根据数据特性和排序需求进行综合选择。

文章来源:https://blog.csdn.net/qq_36534560/article/details/144910378
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系邮箱：jacktools123@163.com进行投诉反馈，一经查实，立即删除！