排序算法堆排序与计数

一、堆排序

1.1 核心思想

利用堆数据结构，每次将堆顶（最大/最小）元素放到正确位置。

1.2 实现

public 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--) {
        swap(arr, 0, i);      // 堆顶放到末尾
        heapify(arr, i, 0);   // 重新堆化
    }
}

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) {
        swap(arr, i, largest);
        heapify(arr, n, largest);
    }
}

1.3 复杂度分析

情况	时间	空间
最好	( O(n \log n) )	( O(1) )
最坏	( O(n \log n) )	( O(1) )
平均	( O(n \log n) )	( O(1) )
稳定性	不稳定

1.4 特点

• 原地排序：空间 ( O(1) )
• 不稳定性：跳跃交换
• 适合内存受限场景

二、计数排序

2.1 核心思想

统计每个值出现的次数，按顺序输出。

2.2 适用条件

• 数据范围较小且整数
• 知道数据的上下界

2.3 实现

public void countingSort(int[] arr, int maxVal) {
    int[] count = new int[maxVal + 1];
    
    // 统计
    for (int num : arr) {
        count[num]++;
    }
    
    // 输出
    int idx = 0;
    for (int i = 0; i <= maxVal; i++) {
        while (count[i]-- > 0) {
            arr[idx++] = i;
        }
    }
}

2.4 稳定版计数排序

public void countingSortStable(int[] arr, int maxVal) {
    int[] count = new int[maxVal + 1];
    int[] output = new int[arr.length];
    
    for (int num : arr) count[num]++;
    for (int i = 1; i <= maxVal; i++) count[i] += count[i - 1];
    
    // 从后往前保证稳定性
    for (int i = arr.length - 1; i >= 0; i--) {
        output[--count[arr[i]]] = arr[i];
    }
    
    System.arraycopy(output, 0, arr, 0, arr.length);
}

2.5 复杂度

情况	时间	空间
最好/最坏/平均	( O(n + k) )	( O(n + k) )

( k ) = 数据范围

三、基数排序

3.1 核心思想

按位数逐位排序，从低位到高位，每位用计数排序。

3.2 实现

public void radixSort(int[] arr) {
    int max = Arrays.stream(arr).max().getAsInt();
    
    for (int exp = 1; max / exp > 0; exp *= 10) {
        countingSortByDigit(arr, exp);
    }
}

void countingSortByDigit(int[] arr, int exp) {
    int[] count = new int[10];
    int[] output = new int[arr.length];
    
    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--) {
        int digit = (arr[i] / exp) % 10;
        output[--count[digit]] = arr[i];
    }
    
    System.arraycopy(output, 0, arr, 0, arr.length);
}

3.3 复杂度

( O(d(n + k)) )，( d ) = 位数，( k ) = 进制数

四、桶排序

4.1 核心思想

将数据分到多个桶，每个桶内分别排序。

public void bucketSort(float[] arr) {
    int n = arr.length;
    List<Float>[] buckets = new ArrayList[n];
    for (int i = 0; i < n; i++) buckets[i] = new ArrayList<>();
    
    // 入桶
    for (float num : arr) {
        int idx = (int) (num * n);
        buckets[idx].add(num);
    }
    
    // 桶内排序
    for (List<Float> bucket : buckets) {
        Collections.sort(bucket);
    }
    
    // 合并
    int idx = 0;
    for (List<Float> bucket : buckets) {
        for (float num : bucket) {
            arr[idx++] = num;
        }
    }
}

五、总结

排序	时间	空间	稳定性	适用场景
堆排序	( O(n \log n) )	( O(1) )	不稳定	内存受限
计数排序	( O(n + k) )	( O(n + k) )	稳定	小范围整数
基数排序	( O(d(n + k)) )	( O(n + k) )	稳定	固定位数整数
桶排序	( O(n) )平均	( O(n) )	稳定	数据均匀分布

线性排序算法突破了比较排序的 ( O(n \log n) ) 下界，但需要特定条件。堆排序是最实用的原地 ( O(n \log n) ) 排序之一。