排序

发表于 分类于

1)基本数据类型

int[] / long[] / double[] 这种原始类型数组:最简洁也最快

直接用:

  • Arrays.sort(arr);

这是原地排序(不额外开同等大小数组),底层对原始类型用的是 Dual-Pivot Quicksort(双轴快排)这类工程化实现,平均很快,刷题完全够用。

2)引用数据类型

Integer[] / String[] / 自定义对象[] 这种对象数组:需要比较器

最常见:

  • Arrays.sort(arr);(元素自己实现了 Comparable,比如 String/Integer)

  • Arrays.sort(arr, comparator);(你要自定义规则时)

对象数组底层通常是 TimSort(稳定排序),适合“部分有序”的数据,也很强。

注意一个刷题坑:int[] 不能直接传 comparator。想按自定义规则,你必须:

  • 要么转 Integer[]

  • 要么自己写排序逻辑(比如桶/计数/自定义 key 的间接排序)

3)list类

List<T>:一句话排序
List: ArrayList / LinkedList / Vector

  • list.sort(Comparator.naturalOrder())
  • list.sort(Comparator.reverseOrder())
  • list.sort((a,b)->Integer.compare(a,b))
  • Collections.sort(list) / Collections.sort(list, cmp)
  • list.sort(comparator);(更顺手)

刷题里我更爱 list.sort(...),因为读起来更“就地操作”。

4)其他

想要“更快”的排序:别指望 API,靠题型 🧠

当你说“最快”,很多时候真正的提速来自不用比较排序:

  • 值域小:计数排序 / 桶排序(O(n + V))

  • 只要 TopK:堆(PriorityQueue)或 quickselect(O(n) 平均)

  • 排序的是 0/1/2:三路 partition(荷兰国旗)

  • 排序的是“按 key 分组”:哈希 + 桶

这些往往能把 O(n log n) 直接打到 O(n) 或更贴题的复杂度,比任何 API 都“快”。

我给你的默认选择(刷题最省心版)

  • 原始数组:Arrays.sort(arr);
  • 对象数组 / 需要自定义规则:Arrays.sort(arr, (a,b)->...);
  • List:list.sort((a,b)->...);

基数排序

当值域小且是整数时,优先想计数/桶;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
private void sort(int[] nums) {
        int max=0;
        for(int x: nums) {
            max=Math.max(max, x);
        }
        
        int[] cnt=new int[max+1];
        for(int v: nums) {
            cnt[v]++;
        }
        int index=0;
        for(int i=1; i<=max; i++) {
            while(cnt[i]>0) {
                cnt[i]--;
                nums[index++]=i;
            }
        }
    }