CodeWalk

快速排序与归并排序的Java实现对比

作者：孤独的心 · 2026-05-30 12:55

请用Java实现快速排序（Quick Sort）和归并排序（Merge Sort），对比它们的原理、时间复杂度和空间复杂度。快速排序的最坏情况是什么？如何优化（三数取中、随机化、插入排序混合）？归并排序的稳定性和空间开销是怎样的？在大数据量下应该如何选择？

回答

孤独的心

快速排序实现

public class QuickSort {
    
    public static void sort(int[] arr) {
        quickSort(arr, 0, arr.length - 1);
    }
    
    private static void quickSort(int[] arr, int left, int right) {
        if (left >= right) return;
        
        // 优化1：三数取中（避免最坏情况）
        int mid = left + (right - left) / 2;
        if (arr[left] > arr[mid]) swap(arr, left, mid);
        if (arr[mid] > arr[right]) swap(arr, mid, right);
        if (arr[left] > arr[mid]) swap(arr, left, mid);
        
        int pivot = partition(arr, left, right);
        quickSort(arr, left, pivot - 1);
        quickSort(arr, pivot + 1, right);
    }
    
    private static int partition(int[] arr, int left, int right) {
        int pivot = arr[right];  // 取最右为基准
        int i = left - 1;
        for (int j = left; j < right; j++) {
            if (arr[j] <= pivot) {
                i++;
                swap(arr, i, j);
            }
        }
        swap(arr, i + 1, right);
        return i + 1;
    }
    
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;
    }
}

归并排序实现

public class MergeSort {
    
    public static void sort(int[] arr) {
        mergeSort(arr, 0, arr.length - 1, new int[arr.length]);
    }
    
    private static void mergeSort(int[] arr, int left, int right, int[] temp) {
        if (left >= right) return;
        
        int mid = left + (right - left) / 2;
        mergeSort(arr, left, mid, temp);
        mergeSort(arr, mid + 1, right, temp);
        merge(arr, left, mid, right, temp);
    }
    
    private static void merge(int[] arr, int left, int mid, int right, int[] temp) {
        System.arraycopy(arr, left, temp, left, right - left + 1);
        
        int i = left, j = mid + 1, k = left;
        while (i <= mid && j <= right) {
            if (temp[i] <= temp[j]) {  // <= 保证稳定性
                arr[k++] = temp[i++];
            } else {
                arr[k++] = temp[j++];
            }
        }
        while (i <= mid) arr[k++] = temp[i++];
        while (j <= right) arr[k++] = temp[j++];
    }
}

对比

维度快速排序归并排序
平均时间复杂度O(n log n)O(n log n)
最坏时间复杂度O(n²)（已排序数组）O(n log n)
空间复杂度O(log n) 栈空间O(n) 辅助数组
稳定性不稳定稳定
排序方式内部排序（原地）外部排序（需额外空间）

优化策略

快排优化：

  • 三数取中（mid-of-three）：避免已排序数组的O(n²)
  • 随机化pivot：进一步避免最坏情况
  • 小数组插入排序（<15个元素时切换，减少递归深度）
  • 尾递归优化（只递归短区间，长区间循环处理）

选择建议：

  • 内存不敏感、需稳定性 → 归并排序
  • 内存敏感、大数据量 → 快速排序（优化后）
  • Java Arrays.sort()：基本类型用快排（Dual-Pivot QuickSort），对象类型用归并（TimSort，稳定）