当前位置： 首页 > java >正文

深入解析十大经典排序算法原理与实现

java 2025/8/25 5:16:24

排序算法示例说明

概述

本文档详细说明了排序算法示例的实现原理、性能特点和使用方法。

功能概要：提供各种排序算法的完整实现，包括基础排序算法和高级排序算法，帮助理解算法原理和性能特点

排序算法分类

1. 基础排序算法 (Basic Sorting Algorithms)

1.1 冒泡排序 (Bubble Sort)
  • 算法思想：比较相邻的两个元素，如果第一个比第二个大，则交换它们
  • 时间复杂度：O(n²)
  • 空间复杂度：O(1)
  • 稳定性：稳定
  • 适用场景：小规模数据排序，教学演示

算法步骤：

  1. 比较相邻的两个元素，如果第一个比第二个大，则交换它们
  2. 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对
  3. 重复以上步骤，直到没有任何一对数字需要比较

优化点：

  • 添加swapped标志，如果一轮比较中没有发生交换，说明数组已经有序，可以提前退出
1.2 选择排序 (Selection Sort)
  • 算法思想：在未排序序列中找到最小元素，存放到排序序列的起始位置
  • 时间复杂度：O(n²)
  • 空间复杂度：O(1)
  • 稳定性：不稳定
  • 适用场景：小规模数据排序，交换次数少

算法步骤：

  1. 在未排序序列中找到最小元素，存放到排序序列的起始位置
  2. 再从剩余未排序元素中继续寻找最小元素，然后放到已排序序列的末尾
  3. 重复第二步，直到所有元素均排序完毕
1.3 插入排序 (Insertion Sort)
  • 算法思想：将第一个元素看做已排序序列，取出下一个元素，在已排序序列中从后向前扫描
  • 时间复杂度：O(n²)
  • 空间复杂度：O(1)
  • 稳定性：稳定
  • 适用场景：小规模数据排序，基本有序的数据

算法步骤：

  1. 将第一个元素看做已排序序列
  2. 取出下一个元素，在已排序序列中从后向前扫描
  3. 如果该元素大于新元素，将该元素移到下一位置
  4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
  5. 将新元素插入到该位置后
  6. 重复步骤2~5
1.4 希尔排序 (Shell Sort)
  • 算法思想：插入排序的改进版，通过设置不同的增量序列来提高效率
  • 时间复杂度：O(n^1.3) 到 O(n²)
  • 空间复杂度：O(1)
  • 稳定性：不稳定
  • 适用场景：中等规模数据排序

算法步骤：

  1. 选择一个初始的增量序列（通常为n/2, n/4, n/8…）
  2. 按照增量序列对数组进行分组
  3. 对每组使用插入排序
  4. 逐步减小增量，重复步骤2-3
  5. 当增量为1时，完成排序

2. 高级排序算法 (Advanced Sorting Algorithms)

2.1 快速排序 (Quick Sort)
  • 算法思想：选择一个基准元素，将小于基准的元素放在左边，大于基准的元素放在右边
  • 时间复杂度：平均O(n log n)，最坏O(n²)
  • 空间复杂度：O(log n)
  • 稳定性：不稳定
  • 适用场景：大规模数据排序，实际应用中最常用的排序算法

算法步骤：

  1. 选择一个基准元素（pivot）
  2. 将小于基准的元素放在左边，大于基准的元素放在右边
  3. 对左右两个子序列递归执行快速排序
  4. 当子序列长度为1或0时，排序完成

优化点：

  • 选择基准元素的方法（三数取中、随机选择等）
  • 处理重复元素的优化
  • 小数组使用插入排序
2.2 归并排序 (Merge Sort)
  • 算法思想：将数组分成两个相等的子数组，递归地对两个子数组进行归并排序，然后合并
  • 时间复杂度：O(n log n)
  • 空间复杂度：O(n)
  • 稳定性：稳定
  • 适用场景：大规模数据排序，需要稳定排序的场景

算法步骤：

  1. 将数组分成两个相等的子数组
  2. 递归地对两个子数组进行归并排序
  3. 将两个已排序的子数组合并成一个有序数组
  4. 当子数组长度为1时，开始合并

特点：

  • 时间复杂度稳定，不受数据分布影响
  • 需要额外的空间复杂度
  • 适合外部排序
2.3 堆排序 (Heap Sort)
  • 算法思想：利用堆这种数据结构所设计的排序算法
  • 时间复杂度：O(n log n)
  • 空间复杂度：O(1)
  • 稳定性：不稳定
  • 适用场景：大规模数据排序，原地排序

算法步骤：

  1. 构建最大堆（或最小堆）
  2. 将堆顶元素（最大值）与末尾元素交换
  3. 调整堆结构，使其重新成为最大堆
  4. 重复步骤2-3，直到堆中只有一个元素

特点：

  • 原地排序，不需要额外空间
  • 时间复杂度稳定
  • 适合找出前k个最大/最小元素

性能对比

时间复杂度对比

算法最好情况平均情况最坏情况
冒泡排序O(n)O(n²)O(n²)
选择排序O(n²)O(n²)O(n²)
插入排序O(n)O(n²)O(n²)
希尔排序O(n log n)O(n^1.3)O(n²)
快速排序O(n log n)O(n log n)O(n²)
归并排序O(n log n)O(n log n)O(n log n)
堆排序O(n log n)O(n log n)O(n log n)

空间复杂度对比

算法空间复杂度是否原地排序
冒泡排序O(1)是
选择排序O(1)是
插入排序O(1)是
希尔排序O(1)是
快速排序O(log n)是
归并排序O(n)否
堆排序O(1)是

稳定性对比

算法稳定性
冒泡排序稳定
选择排序不稳定
插入排序稳定
希尔排序不稳定
快速排序不稳定
归并排序稳定
堆排序不稳定

使用方式

1. 直接调用静态方法

int[] arr = {64, 34, 25, 12, 22, 11, 90};// 使用基础排序算法
BasicSortingAlgorithms.bubbleSort(arr);
BasicSortingAlgorithms.selectionSort(arr);
BasicSortingAlgorithms.insertionSort(arr);
BasicSortingAlgorithms.shellSort(arr);// 使用高级排序算法
AdvancedSortingAlgorithms.quickSort(arr);
AdvancedSortingAlgorithms.mergeSort(arr);
AdvancedSortingAlgorithms.heapSort(arr);

2. 通过策略模式使用

SortContext context = new SortContext();// 设置不同的排序策略
context.setStrategy(new QuickSortStrategy());
int[] result1 = context.executeSort(testArray);context.setStrategy(new MergeSortStrategy());
int[] result2 = context.executeSort(testArray);

3. 运行示例程序

# 运行基础排序算法演示
java org.example.interview.algorithm.sorting.BasicSortingAlgorithms# 运行高级排序算法演示
java org.example.interview.algorithm.sorting.AdvancedSortingAlgorithms# 运行策略模式演示
java org.example.interview.algorithm.sorting.StrategyPattern

算法选择建议

小规模数据 (n < 50)

  • 推荐：插入排序
  • 原因：实现简单，对于小数据效率较高

中等规模数据 (50 ≤ n < 1000)

  • 推荐：希尔排序
  • 原因：比插入排序效率高，实现相对简单

大规模数据 (n ≥ 1000)

  • 推荐：快速排序
  • 原因：平均情况下效率最高，实际应用中最常用

特殊需求

  • 需要稳定排序：归并排序
  • 原地排序：堆排序
  • 外部排序：归并排序

扩展建议

  1. 添加更多排序算法：
    • 计数排序、基数排序、桶排序等线性时间排序算法
    • 外部排序算法
    • 并行排序算法
  2. 性能优化：
    • 混合排序算法（如Timsort）
    • 针对特定数据分布的优化
    • 多线程并行排序
  3. 可视化展示：
    • 排序过程的可视化
    • 性能对比图表
    • 内存使用情况分析

注意事项

  1. 数据规模：选择合适的算法需要考虑数据规模
  2. 数据特征：考虑数据的分布特征（是否基本有序、重复元素等）
  3. 稳定性要求：某些应用场景要求排序算法是稳定的
  4. 空间限制：在内存受限的环境下，优先选择原地排序算法

相关资源

  • 算法导论
  • 数据结构与算法分析
  • 可视化排序算法

相关代码

冒泡排序

		/*** 冒泡排序算法* * 算法思想：通过相邻元素比较和交换，将最大的元素逐步"冒泡"到数组末尾* 具体逻辑：* 1. 外层循环控制排序轮数，每轮将当前范围内最大的元素放到末尾* 2. 内层循环比较相邻元素，如果前一个大于后一个则交换* 3. 使用swapped标志优化：如果一轮中没有发生交换，说明数组已有序，可以提前退出* * 时间复杂度：O(n²) - 最坏情况下需要n-1轮，每轮比较n-i-1次* 空间复杂度：O(1) - 只使用常数个额外变量* 稳定性：稳定 - 相等元素不会改变相对位置* * @param arr 待排序的整数数组*/public static void bubbleSort(int[] arr) {// 边界条件检查：空数组或长度为1的数组无需排序if (arr == null || arr.length <= 1) {return;}int n = arr.length;// 优化标志：如果一轮中没有发生交换，说明数组已经有序boolean swapped;// 外层循环：控制排序轮数，每轮将当前范围内最大的元素放到末尾for (int i = 0; i < n - 1; i++) {// 初始化交换标志为falseswapped = false;// 内层循环：比较相邻元素，范围是[0, n-1-i)// 每轮结束后，最后i个元素已经有序，无需再比较for (int j = 0; j < n - 1 - i; j++) {// 如果前一个元素大于后一个元素，则交换它们if (arr[j] > arr[j + 1]) {swap(arr, j, j + 1);// 标记发生了交换swapped = true;}}// 优化：如果一轮中没有发生交换，说明数组已经有序，可以提前退出if (!swapped) {break;}}}
选择排序
		/*** 选择排序算法* * 算法思想：每次从未排序区间选择最小的元素，放到已排序区间的末尾* 具体逻辑：* 1. 外层循环控制已排序区间的边界，初始时已排序区间为空* 2. 内层循环在未排序区间中寻找最小元素的下标* 3. 将找到的最小元素与未排序区间的第一个元素交换，扩大已排序区间* 4. 重复上述过程，直到所有元素都进入已排序区间* * 时间复杂度：O(n²) - 需要n-1轮选择，每轮在n-i个元素中找最小值* 空间复杂度：O(1) - 只使用常数个额外变量* 稳定性：不稳定 - 相等元素可能改变相对位置（如[3,3,1]排序后变成[1,3,3]）* * @param arr 待排序的整数数组*/public static void selectionSort(int[] arr) {// 边界条件检查：空数组或长度为1的数组无需排序if (arr == null || arr.length <= 1) {return;}int n = arr.length;// 外层循环：控制已排序区间的边界，初始时已排序区间为空for (int i = 0; i < n - 1; i++) {// 假设当前位置i的元素是最小的int minIndex = i;// 内层循环：在未排序区间[i+1, n)中寻找真正的最小元素for (int j = i + 1; j < n; j++) {// 如果发现更小的元素，更新最小元素的下标if (arr[j] < arr[minIndex]) {minIndex = j;}}// 如果找到的最小元素不在位置i，则交换它们// 这样就将最小元素放到了已排序区间的末尾if (minIndex != i) {swap(arr, i, minIndex);}}}
插入排序算法
		/*** 插入排序算法* * 算法思想：将数组分为已排序和未排序两部分，逐个将未排序元素插入到已排序部分的正确位置* 具体逻辑：* 1. 初始时，第一个元素视为已排序，其余元素为未排序* 2. 从未排序区间取第一个元素，在已排序区间中寻找合适的插入位置* 3. 插入过程中，将大于该元素的已排序元素向后移动，为插入腾出空间* 4. 将元素插入到正确位置，扩大已排序区间* 5. 重复上述过程，直到所有元素都进入已排序区间* * 时间复杂度：O(n²) - 最坏情况下需要移动大量元素* 空间复杂度：O(1) - 只使用常数个额外变量* 稳定性：稳定 - 相等元素不会改变相对位置* 特点：对于接近有序的数组，插入排序效率很高，接近O(n)* * @param arr 待排序的整数数组*/public static void insertionSort(int[] arr) {// 边界条件检查：空数组或长度为1的数组无需排序if (arr == null || arr.length <= 1) {return;}int n = arr.length;// 从第二个元素开始，逐个将未排序元素插入到已排序部分for (int i = 1; i < n; i++) {// 保存当前要插入的元素int key = arr[i];// j指向已排序区间的最后一个元素int j = i - 1;// 在已排序区间中寻找key的插入位置// 将大于key的元素向后移动，为key腾出插入空间while (j >= 0 && arr[j] > key) {// 将大于key的元素向后移动一位arr[j + 1] = arr[j];// 继续向前查找j--;}// 找到插入位置，将key插入到arr[j+1]位置// 此时arr[j] <= key，所以key应该放在arr[j+1]arr[j + 1] = key;}}
希尔排序
    /*** 希尔排序算法（改进的插入排序）* * 算法思想：通过设置不同的间隔序列，对数组进行分组插入排序，逐步减小间隔直到为1* 具体逻辑：* 1. 选择一个初始间隔gap（通常为n/2），将数组分成gap个子序列* 2. 对每个子序列分别进行插入排序，但使用gap作为步长* 3. 减小间隔（通常为gap/2），重复上述过程* 4. 当间隔为1时，进行最后一次插入排序，此时数组已经基本有序* 5. 由于数组基本有序，最后的插入排序效率很高* * 时间复杂度：O(n^1.3) - 比插入排序快，但具体复杂度取决于间隔序列的选择* 空间复杂度：O(1) - 只使用常数个额外变量* 稳定性：不稳定 - 相等元素可能改变相对位置* 特点：希尔排序是插入排序的改进版本，对于中等大小的数组效率较高* * @param arr 待排序的整数数组*/public static void shellSort(int[] arr) {// 边界条件检查：空数组或长度为1的数组无需排序if (arr == null || arr.length <= 1) {return;}int n = arr.length;// 外层循环：控制间隔序列，从n/2开始，逐步减小到1for (int gap = n / 2; gap > 0; gap /= 2) {// 对每个子序列进行插入排序// 从第gap个元素开始，因为前gap个元素分别作为各个子序列的第一个元素for (int i = gap; i < n; i++) {// 保存当前要插入的元素int key = arr[i];// j指向当前元素在子序列中的前一个位置int j = i;// 在子序列中寻找key的插入位置// 将大于key的元素向后移动gap个位置while (j >= gap && arr[j - gap] > key) {// 将大于key的元素向后移动gap个位置arr[j] = arr[j - gap];// 在子序列中向前查找j -= gap;}// 找到插入位置，将key插入到arr[j]位置arr[j] = key;}}}
快速排序
    /*** 快速排序算法* * 算法思想：使用分治策略，选择一个基准元素（pivot），将数组分为两部分，* 左边部分都小于等于基准元素，右边部分都大于基准元素，然后递归排序两部分* * 具体逻辑：* 1. 选择基准元素（这里选择最后一个元素作为pivot）* 2. 通过partition方法将数组分为两部分* 3. 递归对左半部分和右半部分进行快速排序* 4. 当子数组长度小于等于1时，递归结束* * 时间复杂度：平均O(n log n)，最坏O(n²)（当数组已经有序时）* 空间复杂度：O(log n) - 递归调用栈的深度* 稳定性：不稳定 - 相等元素可能改变相对位置* 特点：实际应用中效率很高，是很多编程语言内置排序算法的选择* * @param arr 待排序的整数数组*/public static void quickSort(int[] arr) {// 边界条件检查：空数组或长度为1的数组无需排序if (arr == null || arr.length <= 1) {return;}// 调用递归版本的快速排序，初始范围为整个数组quickSort(arr, 0, arr.length - 1);}/*** 快速排序的递归实现* * @param arr 待排序的数组* @param low 当前排序范围的起始索引* @param high 当前排序范围的结束索引*/private static void quickSort(int[] arr, int low, int high) {// 递归终止条件：当子数组长度小于等于1时if (low < high) {// 选择基准元素并分区，返回基准元素的最终位置int pivotIndex = partition(arr, low, high);// 递归排序左半部分（小于基准元素的部分）quickSort(arr, low, pivotIndex - 1);// 递归排序右半部分（大于基准元素的部分）quickSort(arr, pivotIndex + 1, high);}}/*** 分区方法：将数组分为两部分，左边都小于等于pivot，右边都大于pivot* * 具体逻辑：* 1. 选择最后一个元素作为基准元素（pivot）* 2. 使用双指针技术：i指向小于等于pivot的区域的最后一个位置* 3. 遍历数组，将小于等于pivot的元素放到左边区域* 4. 最后将pivot放到正确位置，返回pivot的索引* * @param arr 待分区的数组* @param low 分区范围的起始索引* @param high 分区范围的结束索引（pivot的位置）* @return 基准元素的最终位置*/private static int partition(int[] arr, int low, int high) {// 选择最后一个元素作为基准元素int pivot = arr[high];// i指向小于等于pivot的区域的最后一个位置，初始为low-1int i = low - 1;// 遍历数组，将小于等于pivot的元素放到左边区域for (int j = low; j < high; j++) {// 如果当前元素小于等于pivotif (arr[j] <= pivot) {// 扩展左边区域i++;// 将当前元素交换到左边区域swap(arr, i, j);}}// 将pivot放到正确位置（左边区域的后面）swap(arr, i + 1, high);// 返回pivot的最终位置return i + 1;}
归并排序
    /*** 归并排序算法* * 算法思想：使用分治策略，将数组递归地分成两半，分别排序后再合并* 具体逻辑：* 1. 将数组分成两个大致相等的子数组* 2. 递归地对两个子数组进行归并排序* 3. 将两个已排序的子数组合并成一个有序数组* 4. 当子数组长度为1时，递归结束* * 时间复杂度：O(n log n) - 稳定，不受数据分布影响* 空间复杂度：O(n) - 需要额外的临时数组来存储合并结果* 稳定性：稳定 - 相等元素不会改变相对位置* 特点：时间复杂度稳定，但需要额外空间，适合外部排序* * @param arr 待排序的整数数组*/public static void mergeSort(int[] arr) {// 边界条件检查：空数组或长度为1的数组无需排序if (arr == null || arr.length <= 1) {return;}int n = arr.length;// 创建临时数组，用于存储合并过程中的结果int[] temp = new int[n];// 调用递归版本的归并排序，初始范围为整个数组mergeSort(arr, 0, n - 1, temp);}/*** 归并排序的递归实现* * @param arr 待排序的数组* @param left 当前排序范围的左边界* @param right 当前排序范围的右边界* @param temp 临时数组，用于存储合并结果*/private static void mergeSort(int[] arr, int left, int right, int[] temp) {// 递归终止条件：当子数组长度小于等于1时if (left < right) {// 计算中间位置，将数组分成两半int mid = (left + right) / 2;// 递归排序左半部分mergeSort(arr, left, mid, temp);// 递归排序右半部分mergeSort(arr, mid + 1, right, temp);// 合并两个已排序的子数组merge(arr, left, mid, right, temp);}}/*** 合并两个已排序的子数组* * 具体逻辑：* 1. 使用三个指针：i指向左半部分，j指向右半部分，k指向临时数组* 2. 比较两个子数组的元素，将较小的放入临时数组* 3. 当一个子数组遍历完后，将另一个子数组的剩余元素全部放入临时数组* 4. 最后将临时数组的结果复制回原数组* * @param arr 原数组* @param left 左半部分的起始位置* @param mid 左半部分的结束位置* @param right 右半部分的结束位置* @param temp 临时数组*/private static void merge(int[] arr, int left, int mid, int right, int[] temp) {// 初始化三个指针int i = left;      // 左半部分的指针int j = mid + 1;   // 右半部分的指针int k = left;      // 临时数组的指针// 比较两个子数组的元素，将较小的放入临时数组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 = left; m <= right; m++) {arr[m] = temp[m];}}
堆排序
    /*** 堆排序算法* * 算法思想：利用堆这种数据结构进行排序，先将数组构建成最大堆，* 然后逐个取出堆顶元素（最大值），放到数组末尾，重复此过程直到堆为空* * 具体逻辑：* 1. 构建最大堆：从最后一个非叶子节点开始，自底向上调整每个节点* 2. 堆排序：重复执行以下操作直到堆为空*    a. 将堆顶元素（最大值）与堆的最后一个元素交换*    b. 堆的大小减1*    c. 对新的堆顶元素进行下沉操作，重新构建最大堆* 3. 最终得到升序排列的数组* * 时间复杂度：O(n log n) - 构建堆O(n)，每次调整O(log n)，共n-1次* 空间复杂度：O(1) - 原地排序，只使用常数个额外变量* 稳定性：不稳定 - 相等元素可能改变相对位置* 特点：原地排序，空间效率高，适合大数据量排序* * @param arr 待排序的整数数组*/public static void heapSort(int[] arr) {// 边界条件检查：空数组或长度为1的数组无需排序if (arr == null || arr.length <= 1) {return;}int n = arr.length;// 第一步：构建最大堆// 从最后一个非叶子节点开始，自底向上调整每个节点// 最后一个非叶子节点的索引是 n/2 - 1for (int i = n / 2 - 1; i >= 0; i--) {heapify(arr, n, i);}// 第二步：逐个从堆中取出元素// 从数组末尾开始，每次将堆顶元素（最大值）放到当前位置for (int i = n - 1; i > 0; i--) {// 将堆顶元素（最大值）与堆的最后一个元素交换swap(arr, 0, i);// 对新的堆顶元素进行下沉操作，重新构建最大堆// 注意：此时堆的大小已经减1，所以传入i而不是nheapify(arr, i, 0);}}/*** 堆化操作：将以节点i为根的子树调整为最大堆* * 具体逻辑：* 1. 假设节点i是最大的，比较节点i与其左右子节点* 2. 如果左子节点或右子节点更大，则更新largest指针* 3. 如果largest不等于i，说明需要交换，然后递归调整被交换的子树* 4. 这个过程称为"下沉"操作，确保父节点总是大于等于其子节点* * @param arr 数组（表示堆）* @param n 堆的当前大小* @param i 要调整的节点索引*/private static void heapify(int[] arr, int n, int i) {// 假设当前节点i是最大的int largest = i;// 计算左子节点的索引int left = 2 * i + 1;// 计算右子节点的索引int right = 2 * i + 2;// 如果左子节点存在且大于当前节点，更新largest指针if (left < n && arr[left] > arr[largest]) {largest = left;}// 如果右子节点存在且大于当前最大值，更新largest指针if (right < n && arr[right] > arr[largest]) {largest = right;}// 如果largest不等于i，说明需要交换if (largest != i) {// 交换当前节点与最大子节点swap(arr, i, largest);// 递归调整被交换的子树，确保整个子树都满足最大堆性质heapify(arr, n, largest);}}
工具方法
    /*** 交换数组中两个元素的位置* * @param arr 目标数组* @param i 第一个元素的索引* @param j 第二个元素的索引*/private static void swap(int[] arr, int i, int j) {// 使用临时变量保存第一个元素int temp = arr[i];// 将第二个元素放到第一个位置arr[i] = arr[j];// 将第一个元素放到第二个位置arr[j] = temp;}/*** 打印数组内容，用于调试和演示* * @param arr 要打印的数组* @param message 打印前的说明信息*/public static void printArray(int[] arr, String message) {// 输出消息和数组开始符号System.out.print(message + ": [");// 遍历数组的每个元素for (int i = 0; i < arr.length; i++) {// 输出当前元素System.out.print(arr[i]);// 如果不是最后一个元素，添加分隔符if (i < arr.length - 1) {System.out.print(", ");}}// 输出数组结束符号并换行System.out.println("]");}/*** 检查数组是否已经排序（升序）* * @param arr 要检查的数组* @return true表示数组已排序，false表示数组未排序*/public static boolean isSorted(int[] arr) {// 空数组或长度为1的数组认为是有序的if (arr == null || arr.length <= 1) {return true;}// 检查每个元素是否大于等于前一个元素for (int i = 1; i < arr.length; i++) {// 如果发现逆序，返回falseif (arr[i] < arr[i - 1]) {return false;}}// 所有元素都满足升序条件return true;}/*** 复制数组，创建数组的深拷贝* * @param arr 要复制的原数组* @return 新的数组副本，如果原数组为null则返回null*/public static int[] copyArray(int[] arr) {// 如果原数组为null，直接返回nullif (arr == null) {return null;}// 创建新数组，长度与原数组相同int[] copy = new int[arr.length];// 使用系统方法复制数组内容，效率最高System.arraycopy(arr, 0, copy, 0, arr.length);return copy;}/*** 生成指定大小的随机数组，用于测试排序算法* * @param size 数组大小* @param max 随机数的最大值（不包含）* @return 包含随机整数的数组*/public static int[] generateRandomArray(int size, int max) {// 创建指定大小的数组int[] arr = new int[size];// 为每个位置生成随机数for (int i = 0; i < size; i++) {// 生成[0, max)范围内的随机整数arr[i] = (int) (Math.random() * max);}return arr;}
性能测试
    /*** 测试所有排序算法的性能* * 测试流程：* 1. 分别测试基础排序算法和高级排序算法* 2. 每个算法使用相同的测试数据，确保公平比较* 3. 记录每个算法的执行时间* 4. 验证排序结果的正确性* * @param arr 用于测试的原始数组*/public static void testAllAlgorithms(int[] arr) {// 输出测试标题和基本信息System.out.println("\n=== 所有排序算法性能测试 ===");System.out.println("测试数组大小：" + arr.length);// 第一阶段：测试基础排序算法（时间复杂度O(n²)）testBasicAlgorithms(arr);// 第二阶段：测试高级排序算法（时间复杂度O(n log n)）testAdvancedAlgorithms(arr);}/*** 测试基础排序算法的性能* * 测试算法：* - 冒泡排序：O(n²)，稳定，适合小数据量* - 选择排序：O(n²)，不稳定，交换次数少* - 插入排序：O(n²)，稳定，对接近有序的数组效率高* - 希尔排序：O(n^1.3)，不稳定，插入排序的改进版本* * @param arr 用于测试的原始数组*/private static void testBasicAlgorithms(int[] arr) {System.out.println("\n--- 基础排序算法 ---");// 测试冒泡排序int[] arr1 = copyArray(arr);long startTime = System.currentTimeMillis();bubbleSort(arr1);long endTime = System.currentTimeMillis();System.out.println("冒泡排序：" + (endTime - startTime) + " 毫秒，结果：" + (isSorted(arr1) ? "成功" : "失败"));// 测试选择排序int[] arr2 = copyArray(arr);startTime = System.currentTimeMillis();selectionSort(arr2);endTime = System.currentTimeMillis();System.out.println("选择排序：" + (endTime - startTime) + " 毫秒，结果：" + (isSorted(arr2) ? "成功" : "失败"));// 测试插入排序int[] arr3 = copyArray(arr);startTime = System.currentTimeMillis();insertionSort(arr3);endTime = System.currentTimeMillis();System.out.println("插入排序：" + (endTime - startTime) + " 毫秒，结果：" + (isSorted(arr3) ? "成功" : "失败"));// 测试希尔排序int[] arr4 = copyArray(arr);startTime = System.currentTimeMillis();shellSort(arr4);endTime = System.currentTimeMillis();System.out.println("希尔排序：" + (endTime - startTime) + " 毫秒，结果：" + (isSorted(arr4) ? "成功" : "失败"));}/*** 测试高级排序算法的性能* * 测试算法：* - 快速排序：平均O(n log n)，不稳定，实际应用中效率最高* - 归并排序：O(n log n)，稳定，时间复杂度稳定但需要额外空间* - 堆排序：O(n log n)，不稳定，原地排序空间效率高* * 预期结果：这些算法在大数据量时应该比基础排序算法快很多* * @param arr 用于测试的原始数组*/private static void testAdvancedAlgorithms(int[] arr) {System.out.println("\n--- 高级排序算法 ---");// 测试快速排序int[] arr1 = copyArray(arr);long startTime = System.currentTimeMillis();quickSort(arr1);long endTime = System.currentTimeMillis();System.out.println("快速排序：" + (endTime - startTime) + " 毫秒，结果：" + (isSorted(arr1) ? "成功" : "失败"));// 测试归并排序int[] arr2 = copyArray(arr);startTime = System.currentTimeMillis();mergeSort(arr2);endTime = System.currentTimeMillis();System.out.println("归并排序：" + (endTime - startTime) + " 毫秒，结果：" + (isSorted(arr2) ? "成功" : "失败"));// 测试堆排序int[] arr3 = copyArray(arr);startTime = System.currentTimeMillis();heapSort(arr3);endTime = System.currentTimeMillis();System.out.println("堆排序：" + (endTime - startTime) + " 毫秒，结果：" + (isSorted(arr3) ? "成功" : "失败"));}
主方法
    /*** 主方法：演示所有排序算法的功能和性能* * 演示内容：* 1. 小规模数据排序：展示各种算法的排序过程和结果* 2. 大规模数据性能测试：比较不同算法的执行效率* 3. 验证排序结果的正确性* * @param args 命令行参数（未使用）*/public static void main(String[] args) {// 打印演示标题InterviewUtils.printTitle("所有排序算法演示");// 第一阶段：小规模数据排序演示// 使用固定的测试数据，便于观察排序过程int[] smallArray = {64, 34, 25, 12, 22, 11, 90, 88, 76, 54};System.out.println("小规模测试数据：");printArray(smallArray, "原始数组");// 依次测试各种排序算法，展示排序结果System.out.println("\n=== 小规模数据排序测试 ===");// 测试冒泡排序int[] arr1 = copyArray(smallArray);bubbleSort(arr1);printArray(arr1, "冒泡排序后");// 测试选择排序int[] arr2 = copyArray(smallArray);selectionSort(arr2);printArray(arr2, "选择排序后");// 测试插入排序int[] arr3 = copyArray(smallArray);insertionSort(arr3);printArray(arr3, "插入排序后");// 测试希尔排序int[] arr4 = copyArray(smallArray);shellSort(arr4);printArray(arr4, "希尔排序后");// 测试快速排序int[] arr5 = copyArray(smallArray);quickSort(arr5);printArray(arr5, "快速排序后");// 测试归并排序int[] arr6 = copyArray(smallArray);mergeSort(arr6);printArray(arr6, "归并排序后");// 测试堆排序int[] arr7 = copyArray(smallArray);heapSort(arr7);printArray(arr7, "堆排序后");// 第二阶段：大规模数据性能测试// 生成5000个随机数进行性能对比System.out.println("\n=== 大规模数据性能测试 ===");int[] largeArray = generateRandomArray(5000, 100000);testAllAlgorithms(largeArray);// 打印分隔线和完成信息InterviewUtils.printSeparator(50);System.out.println("所有排序算法演示完成！");}

备注： 详细代码可以私信博主获取。

http://www.xdnf.cn/news/18646.html

相关文章：

  • 室联人形机器人：家政服务任务结构化、技术要点、深入应用FPGA的控制系统框架设计（整合版A）
  • 【运维进阶】高可用和负载均衡技术
  • Django的Serializers与 fastapi 的Pydantic
  • 【R语言】R语言中 rbind() 与 merge() 的区别详解
  • 网络编程-创建TCP协议服务器
  • 疏老师-python训练营-Day54Inception网络及其思考
  • 屏幕类型与信号接口
  • 【KO】前端面试一
  • LLaMA-Factory 中配置文件或命令行里各个参数的含义
  • 如何利用 DeepSeek 提升工作效率
  • 10.Shell脚本修炼手册---脚本的条件测试与比较
  • 国家自然科学基金（国自然基金）申请技巧详解
  • 深度学习入门：神经网络
  • 【2025CVPR-目标检测方向】UniMamba：基于激光雷达的3D目标检测，采用分组高效曼巴语进行统一空间信道表示学习
  • Q/DR/CX7.2-2020 是中国企业标准体系中
  • 一个备份、去除、新增k8s的node标签脚本
  • `strdup` 字符串复制函数
  • 【JVM内存结构系列】二、线程私有区域详解：程序计数器、虚拟机栈、本地方法栈——搞懂栈溢出与线程隔离
  • 奇怪的前端面试题
  • 智能系统与未来生态演进初步思考
  • LangChain4j中集成Redis向量数据库实现Rag
  • 2-4.Python 编码基础 - 流程控制（判断语句、循环语句、break 语句与 continue 语句）
  • 【Python】新手入门：Python标准库有哪些常用模块？
  • 容器安全实践（二）：实践篇 - 从 `Dockerfile` 到 Pod 的权限深耕
  • 美食菜谱数据集（13943条）收集 | 智能体知识库 | AI大模型训练
  • 自学嵌入式第二十六天：数据结构-哈希表、内核链表
  • 从0开始学习Java+AI知识点总结-23.web实战案例（班级和学生增删改查、信息统计）
  • 【Prometheus】Prometheus监控Docker实战
  • C++编程语言：标准库：第36章——字符串类(Bjarne Stroustrup)
  • 【C语言16天强化训练】从基础入门到进阶：Day 8