快排的多种写法总结归纳

快排基本思路

  • 如果S中元素个数是0或者1，则返回 【边界条件】
  • 取S中任一元素v，称之为枢纽元pivot【partition】
  • 将S-{v}划分成两个不相交的集合：S1={x属于S-{v} | x<=v} 和 S2={x属于S-{v} | x>= v}
  • 返回{quickSort（S1)+v+quickSort（S2）} 【递归】

选取枢纽元Pivot

选取左（右）端点

  • 缺点：如果是已排好序的或者倒序的，O(n2)
  • 选取左右端点作为枢纽元时，数组可以全部使用快排进行排序

  • 选取左端点：swap(A, left, j)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    public void qsL(int[] A, int left, int right) {
        if(left < right) {
            int pivot = A[left];
            int i = left + 1, j = right;
            while(true) {
                while(i < A.length && A[i] < pivot) i++;
                while(j >=0 && A[j] > pivot) j--;
                if(i<j) {
                    swap(A, i, j);
                }else{
                    break;
                }
            }
            swap(A, left, j);
            qs(A, left, j-1);
            qs(A, j+1, right);
        }
    }

  • 选取右端点：swap(A, i, right)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
       public void qsR(int[] A, int left ,int right) {
        if(left < right) {
            int pivot = A[right];
            int i = left, j = right -1;
            while(true) {
                while(A[i] < pivot) i++;
                while(j >=0 && A[j] > pivot) j--;
                if(i < j) {
                    swap(A, i, j);
                }else{
                    break;
                }
            }
            swap(A, i, right);
            qsR(A, left, i-1);
            qsR(A, i+1, right);
        }
    }

随机选取枢纽元

  • 缺点：随机数生成开销很大

三数中值分割法

  • 取left/right/center三个数中中间大的数作为pivot，然后将pivot放到right-1的位置，遍历0->right-2的位置即可

  • 如果使用三数中值分割法（优化版快排），则在小于某一个CUTOFF值时，需要改用插入排序，因为三数中值分割法时，至少需要三个数进行，在快排到两个数时，如果还使用该方法，则会出现排序错误

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    private int median3(int[] A, int left, int right) {
        int center = (left + right)/2;
        if(A[center] < A[left]){
            swap(A, center, left);
        }
        if(A[left] > A[right]){
            swap(A, left, right);
        }
        if(A[center] > A[right]) {
            swap(A, center, right);
        }
        swap(A, center, right-1);
        return A[right -1];
    }

  • 然后进行递归快排：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    public static final int CUTOFF = 5;
    public void qs3(int[] A, int left, int right) {
        if(left + CUTOFF <= right) {
            int pivot = median3(A, left, right);
            int i = left, j = right -1;
            while(true) {
                while(A[i] < pivot) i++;
                while(A[j] > pivot) j--;
                if(i<j){
                    swap(A, i, j);
                }else{
                    break;
                }
            }
            swap(A, i, right -1);
            qs3(A, left, i-1);
            qs3(A, i+1, right);
        }else{
            insertionSort(A, left, right);
        }
    }

附

交叉元素的位置

1
2
3
4
5
private void swap(int[] A, int i, int j) {
    int tmp = A[i];
    A[i] = A[j];
    A[j] = tmp;
}

插入排序

1
2
3
4
5
6
7
8
9
10
11
12
private void insertionSort(int[] A, int left, int right) {
    if(A == null || left >= right) return;
    for(int i=left +1; i<=right; i++) {
        int key = A[i];
        int j = i-1;
        while(j >= left && A[j] > key) {
            A[j+1] = A[j];
            j--;
        }
        A[j+1] = key;
    }
}