排序算法归并与快速

一、分治思想

1.1 核心步骤

1. 分解：将问题拆分为子问题
2. 解决：递归解决子问题
3. 合并：将子问题的解合并

[ T(n) = aT(n/b) + f(n) ]

二、归并排序

2.1 核心思想

分而治之：将数组一分为二，分别排序后合并两个有序数组。

2.2 实现

public void mergeSort(int[] arr, int left, int right) {
    if (left >= right) return;
    
    int mid = left + (right - left) / 2;
    mergeSort(arr, left, mid);
    mergeSort(arr, mid + 1, right);
    merge(arr, left, mid, right);
}

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) {
        if (arr[i] <= arr[j]) temp[k++] = arr[i++];
        else temp[k++] = arr[j++];
    }
    
    while (i <= mid) temp[k++] = arr[i++];
    while (j <= right) temp[k++] = arr[j++];
    
    System.arraycopy(temp, 0, arr, left, temp.length);
}

2.3 复杂度分析

情况	时间复杂度	空间复杂度
最好	( O(n \log n) )	( O(n) )
最坏	( O(n \log n) )	( O(n) )
平均	( O(n \log n) )	( O(n) )
稳定性	稳定

2.4 稳定性证明

合并时取 <= 而非 <，保证相等元素先取左边的，相对位置不变。

三、快速排序

3.1 核心思想

选择一个基准值(pivot)，将数组分为两部分：小于pivot的放左边，大于的放右边，然后递归排序两部分。

3.2 基础实现

public void quickSort(int[] arr, int left, int right) {
    if (left >= right) return;
    
    int pivot = partition(arr, left, right);
    quickSort(arr, left, pivot - 1);
    quickSort(arr, pivot + 1, right);
}

int partition(int[] arr, int left, int right) {
    int pivot = arr[right];  // 选最后一个为基准
    int i = left;
    
    for (int j = left; j < right; j++) {
        if (arr[j] <= pivot) {
            swap(arr, i++, j);
        }
    }
    swap(arr, i, right);
    return i;
}

3.3 随机化优化

int partitionRandom(int[] arr, int left, int right) {
    int randomIdx = left + new Random().nextInt(right - left + 1);
    swap(arr, randomIdx, right);
    return partition(arr, left, right);
}

3.4 三数取中法

选择left、mid、right三个位置的中值作为pivot，避免极端情况。

3.5 双路快排（处理大量重复元素）

int partition2Way(int[] arr, int left, int right) {
    int pivot = arr[left];
    int i = left + 1, j = right;
    
    while (true) {
        while (i <= right && arr[i] < pivot) i++;
        while (j >= left + 1 && arr[j] > pivot) j--;
        if (i > j) break;
        swap(arr, i++, j--);
    }
    swap(arr, left, j);
    return j;
}

3.6 三路快排（大量重复元素最优）

void quickSort3Way(int[] arr, int left, int right) {
    if (left >= right) return;
    
    int pivot = arr[left];
    int lt = left, gt = right, i = left + 1;
    
    while (i <= gt) {
        if (arr[i] < pivot) swap(arr, i++, lt++);
        else if (arr[i] > pivot) swap(arr, i, gt--);
        else i++;
    }
    
    quickSort3Way(arr, left, lt - 1);
    quickSort3Way(arr, gt + 1, right);
}

3.7 复杂度分析

情况	时间复杂度	说明
最好	( O(n \log n) )	每次均匀划分
最坏	( O(n^2) )	已排序且选端点为pivot
平均	( O(n \log n) )	随机化后
空间	( O(\log n) )	递归栈
稳定性	不稳定	交换改变相对位置

四、归并 vs 快速排序

特性	归并排序	快速排序
最好时间	( O(n \log n) )	( O(n \log n) )
最坏时间	( O(n \log n) )	( O(n^2) )
平均时间	( O(n \log n) )	( O(n \log n) )
空间	( O(n) )	( O(\log n) )
稳定性	稳定	不稳定
适用	链表排序、外部排序	数组排序、通用
缓存友好	一般	较好

五、Java中的排序

// Arrays.sort() 对基本类型：Dual-Pivot Quicksort
// 对对象类型：Timsort（归并排序的优化版）
Arrays.sort(intArray);
Arrays.sort(objectArray);

// Collections.sort() 基于Timsort
Collections.sort(list);

对象类型用Timsort（稳定），基本类型用快排（更快，不稳定性无关）。

六、总结

归并排序和快速排序都是分治的经典应用。归并排序稳定且最坏情况有保证，但需要额外空间。快速排序原地排序、缓存友好，是实际中最常用的排序算法。理解两者差异，才能在不同场景做出正确选择。