public static void quickSort(int[] arr, int low, int high) { if (low < high) { int pivot = partition(arr, low, high); quickSort(arr, low, pivot - 1); quickSort(arr, pivot + 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++; swap(arr, i, j); } } swap(arr, i + 1, high); return i + 1; }
优化：随机选择基准避免最坏情况。
适用场景：大规模通用数据。
5. 归并排序
原理：分治法，递归分割数组，合并有序子序列。
时间复杂度：O(n log n)（始终），空间复杂度：O(n)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
public static void mergeSort(int[] arr, int left, int right) { if (left >= right) return; 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); }
适用场景：需稳定排序的大规模数据（如对象排序）。
6. 堆排序
原理：构建最大堆，依次取堆顶元素并调整堆。
时间复杂度：O(n log n)（始终）
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
public static void heapSort(int[] arr) { for (int i = arr.length / 2 - 1; i >= 0; i--) heapify(arr, arr.length, i); for (int i = arr.length - 1; i > 0; i--) { swap(arr, 0, i); heapify(arr, i, 0); } }
private static void heapify(int[] arr, int n, int i) { int largest = i, left = 2 * i + 1, 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) { swap(arr, i, largest); heapify(arr, n, largest); } }
适用场景：内存受限的大规模数据。
7. 希尔排序
原理：分组插入排序，逐步缩小增量直至为1。
时间复杂度：O(n log n) ~ O(n²)（取决于增量序列）
1 2 3 4 5 6 7 8 9 10 11 12
public static void shellSort(int[] arr) { for (int gap = arr.length / 2; gap > 0; gap /= 2) { for (int i = gap; i < arr.length; i++) { int temp = arr[i], j = i; while (j >= gap && arr[j - gap] > temp) { arr[j] = arr[j - gap]; j -= gap; } arr[j] = temp; } } }
适用场景：中等规模数据，需避免最坏情况。
8. 计数排序
原理：统计元素频次，按计数重建有序序列。
时间复杂度：O(n + k)（k为数据范围）
1 2 3 4 5 6 7 8 9
public static void countingSort(int[] arr) { int max = Arrays.stream(arr).max().getAsInt(); int[] count = new int[max + 1]; for (int num : arr) count[num]++; int idx = 0; for (int i = 0; i <= max; i++) { while (count[i]-- > 0) arr[idx++] = i; } }
适用场景：小范围非负整数（如年龄排序）。
9. 桶排序
原理：数据分桶，桶内排序后合并。
时间复杂度：O(n + k)（k为桶数）
1 2 3 4 5 6 7 8 9 10 11 12 13 14
public static void bucketSort(int[] arr, int bucketSize) { int min = Arrays.stream(arr).min().getAsInt(); int max = Arrays.stream(arr).max().getAsInt(); List<List<Integer>> buckets = new ArrayList<>(); for (int i = 0; i <= (max - min) / bucketSize; i++) buckets.add(new ArrayList<>()); for (int num : arr) buckets.get((num - min) / bucketSize).add(num); int idx = 0; for (List<Integer> bucket : buckets) { Collections.sort(bucket); for (int num : bucket) arr[idx++] = num; } }
适用场景：数据均匀分布（如浮点数排序）。
10. 基数排序
原理：按位数从低到高依次进行稳定排序。
时间复杂度：O(d(n + k))（d为最大位数）
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
public static void radixSort(int[] arr) { int max = Arrays.stream(arr).max().getAsInt(); for (int exp = 1; max / exp > 0; exp *= 10) { countingSortByDigit(arr, exp); } }
private static void countingSortByDigit(int[] arr, int exp) { int[] output = new int[arr.length]; int[] count = new int[10]; for (int num : arr) count[(num / exp) % 10]++; for (int i = 1; i < 10; i++) count[i] += count[i - 1]; for (int i = arr.length - 1; i >= 0; i--) { output[count[(arr[i] / exp) % 10] - 1] = arr[i]; count[(arr[i] / exp) % 10]--; } System.arraycopy(output, 0, arr, 0, arr.length); }
