Java数据结构与算法 - 排序算法详解
排序算法是计算机科学中最基础且重要的算法之一。不同的排序算法具有不同的时间复杂度和空间复杂度，适用于不同的场景。本文将详细介绍主要的排序算法及其Java实现。
基础排序算法实现
public class SortingAlgorithms { 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; } } } }}public static void selectionSort(int[] arr) { int n = arr.length; for (int i = 0; i < n - 1; i++) { int minIdx = i; for (int j = i + 1; j < n; j++) { if (arr[j] < arr[minIdx]) { minIdx = j; } } // 交换找到的最小元素和首位元素 int temp = arr[minIdx]; arr[minIdx] = arr[i]; arr[i] = temp; }}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; }}高级排序算法实现
public static void quickSort(int[] arr, int low, int high) { if (low < high) { int pi = partition(arr, low, high); quickSort(arr, low, pi - 1); quickSort(arr, pi + 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;}public static void mergeSort(int[] arr, int left, int right) { if (left < right) { int middle = (left + right) / 2; mergeSort(arr, left, middle); mergeSort(arr, middle + 1, right); merge(arr, left, middle, right); }}private static void merge(int[] arr, int left, int middle, int right) { int n1 = middle - left + 1; int n2 = right - middle; int[] L = new int[n1]; int[] R = new int[n2]; for (int i = 0; i < n1; i++) L[i] = arr[left + i]; for (int j = 0; j < n2; j++) R[j] = arr[middle + 1 + j]; int i = 0, j = 0, k = left; while (i < n1 && j < n2) { if (L[i] <= R[j]) { arr[k] = L[i]; i++; } else { arr[k] = R[j]; j++; } k++; } while (i < n1) { arr[k] = L[i]; i++; k++; } while (j < n2) { arr[k] = R[j]; j++; k++; }}public static void heapSort(int[] arr) { int n = arr.length; // 构建最大堆 for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i); // 从堆中逐个提取元素 for (int i = n - 1; i > 0; i--) { int temp = arr[0]; arr[0] = arr[i]; arr[i] = temp; heapify(arr, i, 0); }}private static void heapify(int[] arr, int n, int i) { int largest = i; int left = 2 * i + 1; int right = 2 * i + 2; if (left < n && arr[left] > arr[largest]) largest = left; if (right < n && arr[right] > arr[largest]) largest = right; if (largest != i) { int swap = arr[i]; arr[i] = arr[largest]; arr[largest] = swap; heapify(arr, n, largest); }}性能比较与分析
以下是各种排序算法的性能特征：
算法名称：冒泡排序
平均时间复杂度：O(n²)
最坏时间复杂度：O(n²)
空间复杂度：O(1)
稳定性：稳定
算法名称：选择排序
平均时间复杂度：O(n²)
最坏时间复杂度：O(n²)
空间复杂度：O(1)
稳定性：不稳定
算法名称：插入排序
平均时间复杂度：O(n²)
最坏时间复杂度：O(n²)
空间复杂度：O(1)
稳定性：稳定
算法名称：快速排序
平均时间复杂度：O(nlogn)
最坏时间复杂度：O(n²)
空间复杂度：O(logn)
稳定性：不稳定
算法名称：归并排序
平均时间复杂度：O(nlogn)
最坏时间复杂度：O(nlogn)
空间复杂度：O(n)
稳定性：稳定
算法名称：堆排序
平均时间复杂度：O(nlogn)
最坏时间复杂度：O(nlogn)
空间复杂度：O(1)
稳定性：不稳定
实际应用示例
public class SortingDemo { public static void main(String[] args) { // 创建测试数组 int[] arr = {64, 34, 25, 12, 22, 11, 90}; // 打印原始数组 System.out.println("原始数组: " + Arrays.toString(arr)); // 选择合适的排序算法 quickSort(arr, 0, arr.length - 1); // 打印排序后的数组 System.out.println("排序后数组: " + Arrays.toString(arr)); }}排序算法的选择建议
- 小规模数据集（n < 50）：推荐使用插入排序，实现简单，对接近有序的数组效率高。
- 中等规模数据集（50 ≤ n < 1000）：推荐使用快速排序，平均性能最好，实现相对简单。
- 大规模数据集（n ≥ 1000）：推荐使用归并排序或堆排序，稳定的O(nlogn)时间复杂度。如果内存受限，优先选择堆排序。
- 特殊场景：
需要稳定排序：使用归并排序。
内存受限：使用堆排序。
接近有序数据：使用插入排序。
并行处理：考虑归并排序。
优化建议
快速排序优化：
使用三数取中法选择枢轴。
对小规模子数组使用插入排序。
处理重复元素时使用三路快排。
归并排序优化：
小规模数组使用插入排序。
避免重复创建临时数组。
利用数组的局部有序性。
实际应用中的注意事项：
考虑数据的特征选择合适的算法。
注意算法的稳定性要求。
关注内存使用情况。
考虑并行化的可能性。
