排序算法示例说明文档
概述
本文档详细说明了排序算法示例的实现原理、性能特点和使用方法。
功能概要：提供各种排序算法的完整实现，包括基础排序算法和高级排序算法，帮助理解算法原理和性能特点
排序算法分类
1. 基础排序算法 (Basic Sorting Algorithms)
1.1 冒泡排序 (Bubble Sort)
- 算法思想：比较相邻的两个元素，如果第一个比第二个大，则交换它们
- 时间复杂度：O(n²)
- 空间复杂度：O(1)
- 稳定性：稳定
- 适用场景：小规模数据排序，教学演示
算法步骤：
- 比较相邻的两个元素，如果第一个比第二个大，则交换它们
- 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对
- 重复以上步骤，直到没有任何一对数字需要比较
优化点：
- 添加swapped标志，如果一轮比较中没有发生交换，说明数组已经有序，可以提前退出
/*** 冒泡排序算法* * 算法思想：通过相邻元素比较和交换，将最大的元素逐步"冒泡"到数组末尾* 具体逻辑：* 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 选择排序 (Selection Sort)
- 算法思想：在未排序序列中找到最小元素，存放到排序序列的起始位置
- 时间复杂度：O(n²)
- 空间复杂度：O(1)
- 稳定性：不稳定
- 适用场景：小规模数据排序，交换次数少
算法步骤：
- 在未排序序列中找到最小元素，存放到排序序列的起始位置
- 再从剩余未排序元素中继续寻找最小元素，然后放到已排序序列的末尾
- 重复第二步，直到所有元素均排序完毕
/*** 选择排序算法* * 算法思想：每次从未排序区间选择最小的元素，放到已排序区间的末尾* 具体逻辑：* 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.3 插入排序 (Insertion Sort)
- 算法思想：将第一个元素看做已排序序列，取出下一个元素，在已排序序列中从后向前扫描
- 时间复杂度：O(n²)
- 空间复杂度：O(1)
- 稳定性：稳定
- 适用场景：小规模数据排序，基本有序的数据
算法步骤：
- 将第一个元素看做已排序序列
- 取出下一个元素，在已排序序列中从后向前扫描
- 如果该元素大于新元素，将该元素移到下一位置
- 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
- 将新元素插入到该位置后
- 重复步骤2~5
/*** 插入排序算法* * 算法思想：将数组分为已排序和未排序两部分，逐个将未排序元素插入到已排序部分的正确位置* 具体逻辑：* 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.4 希尔排序 (Shell Sort)
- 算法思想：插入排序的改进版，通过设置不同的增量序列来提高效率
- 时间复杂度：O(n^1.3) 到 O(n²)
- 空间复杂度：O(1)
- 稳定性：不稳定
- 适用场景：中等规模数据排序
算法步骤：
- 选择一个初始的增量序列（通常为n/2, n/4, n/8…）
- 按照增量序列对数组进行分组
- 对每组使用插入排序
- 逐步减小增量，重复步骤2-3
- 当增量为1时，完成排序
/*** 希尔排序算法（改进的插入排序）* * 算法思想：通过设置不同的间隔序列，对数组进行分组插入排序，逐步减小间隔直到为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;}}}
2. 高级排序算法 (Advanced Sorting Algorithms)
2.1 快速排序 (Quick Sort)
- 算法思想：选择一个基准元素，将小于基准的元素放在左边，大于基准的元素放在右边
- 时间复杂度：平均O(n log n)，最坏O(n²)
- 空间复杂度：O(log n)
- 稳定性：不稳定
- 适用场景：大规模数据排序，实际应用中最常用的排序算法
算法步骤：
- 选择一个基准元素（pivot）
- 将小于基准的元素放在左边，大于基准的元素放在右边
- 对左右两个子序列递归执行快速排序
- 当子序列长度为1或0时，排序完成
优化点：
- 选择基准元素的方法（三数取中、随机选择等）
- 处理重复元素的优化
- 小数组使用插入排序
/*** 快速排序算法* * 算法思想：使用分治策略，选择一个基准元素（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;}
2.2 归并排序 (Merge Sort)
- 算法思想：将数组分成两个相等的子数组，递归地对两个子数组进行归并排序，然后合并
- 时间复杂度：O(n log n)
- 空间复杂度：O(n)
- 稳定性：稳定
- 适用场景：大规模数据排序，需要稳定排序的场景
算法步骤：
- 将数组分成两个相等的子数组
- 递归地对两个子数组进行归并排序
- 将两个已排序的子数组合并成一个有序数组
- 当子数组长度为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];}}
2.3 堆排序 (Heap Sort)
- 算法思想：利用堆这种数据结构所设计的排序算法
- 时间复杂度：O(n log n)
- 空间复杂度：O(1)
- 稳定性：不稳定
- 适用场景：大规模数据排序，原地排序
算法步骤：
- 构建最大堆（或最小堆）
- 将堆顶元素（最大值）与末尾元素交换
- 调整堆结构，使其重新成为最大堆
- 重复步骤2-3，直到堆中只有一个元素
特点：
- 原地排序，不需要额外空间
- 时间复杂度稳定
- 适合找出前k个最大/最小元素
/*** 堆排序算法* * 算法思想：利用堆这种数据结构进行排序，先将数组构建成最大堆，* 然后逐个取出堆顶元素（最大值），放到数组末尾，重复此过程直到堆为空* * 具体逻辑：* 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);}}
性能对比
时间复杂度对比
| 算法 | 最好情况 | 平均情况 | 最坏情况 |
|---|---|---|---|
| 冒泡排序 | 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)
- 推荐：快速排序
- 原因：平均情况下效率最高，实际应用中最常用
特殊需求
- 需要稳定排序：归并排序
- 原地排序：堆排序
- 外部排序：归并排序
扩展建议
- 添加更多排序算法：
- 计数排序、基数排序、桶排序等线性时间排序算法
- 外部排序算法
- 并行排序算法
- 性能优化：
- 混合排序算法（如Timsort）
- 针对特定数据分布的优化
- 多线程并行排序
- 可视化展示：
- 排序过程的可视化
- 性能对比图表
- 内存使用情况分析
注意事项
- 数据规模：选择合适的算法需要考虑数据规模
- 数据特征：考虑数据的分布特征（是否基本有序、重复元素等）
- 稳定性要求：某些应用场景要求排序算法是稳定的
- 空间限制：在内存受限的环境下，优先选择原地排序算法
相关资源
- 算法导论
- 数据结构与算法分析
- 可视化排序算法
公共代码
工具方法
/*** 交换数组中两个元素的位置* * @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("所有排序算法演示完成！");}
)
 | 自动化测试实战)
