privatestaticvoidmerge(int[] arr, int left, int mid, int right) { int[] temp = newint[right - left + 1]; inti= 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); }
适用场景:需稳定排序的大规模数据(如对象排序)。
堆排序
原理:构建最大堆,依次取堆顶元素并调整堆。
时间复杂度:O(n log n)(始终)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
publicstaticvoidheapSort(int[] arr) { for (inti= arr.length / 2 - 1; i >= 0; i--) heapify(arr, arr.length, i); for (inti= arr.length - 1; i > 0; i--) { swap(arr, 0, i); heapify(arr, i, 0); } }
privatestaticvoidheapify(int[] arr, int n, int i) { intlargest= 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); } }
适用场景:内存受限的大规模数据。
希尔排序
原理:分组插入排序,逐步缩小增量直至为1。
时间复杂度:O(n log n) ~ O(n²)(取决于增量序列)
1 2 3 4 5 6 7 8 9 10 11 12
publicstaticvoidshellSort(int[] arr) { for (intgap= arr.length / 2; gap > 0; gap /= 2) { for (inti= gap; i < arr.length; i++) { inttemp= arr[i], j = i; while (j >= gap && arr[j - gap] > temp) { arr[j] = arr[j - gap]; j -= gap; } arr[j] = temp; } } }
适用场景:中等规模数据,需避免最坏情况。
计数排序
原理:统计元素频次,按计数重建有序序列。
时间复杂度:O(n + k)(k为数据范围)
1 2 3 4 5 6 7 8 9
publicstaticvoidcountingSort(int[] arr) { intmax= Arrays.stream(arr).max().getAsInt(); int[] count = newint[max + 1]; for (int num : arr) count[num]++; intidx=0; for (inti=0; i <= max; i++) { while (count[i]-- > 0) arr[idx++] = i; } }
适用场景:小范围非负整数(如年龄排序)。
桶排序
原理:数据分桶,桶内排序后合并。
时间复杂度:O(n + k)(k为桶数)
1 2 3 4 5 6 7 8 9 10 11 12 13 14
publicstaticvoidbucketSort(int[] arr, int bucketSize) { intmin= Arrays.stream(arr).min().getAsInt(); intmax= Arrays.stream(arr).max().getAsInt(); List<List<Integer>> buckets = newArrayList<>(); for (inti=0; i <= (max - min) / bucketSize; i++) buckets.add(newArrayList<>()); for (int num : arr) buckets.get((num - min) / bucketSize).add(num); intidx=0; for (List<Integer> bucket : buckets) { Collections.sort(bucket); for (int num : bucket) arr[idx++] = num; } }
适用场景:数据均匀分布(如浮点数排序)。
基数排序
原理:按位数从低到高依次进行稳定排序。
时间复杂度:O(d(n + k))(d为最大位数)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
publicstaticvoidradixSort(int[] arr) { intmax= Arrays.stream(arr).max().getAsInt(); for (intexp=1; max / exp > 0; exp *= 10) { countingSortByDigit(arr, exp); } }
privatestaticvoidcountingSortByDigit(int[] arr, int exp) { int[] output = newint[arr.length]; int[] count = newint[10]; for (int num : arr) count[(num / exp) % 10]++; for (inti=1; i < 10; i++) count[i] += count[i - 1]; for (inti= 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); }