算法导论之快速排序实现

实现该算法的背景

快速排序实现的方式有各种各样的，但是却很少看到算法导论中的实现。就是书上那个，我很是纳闷。所以在这里贴一份这样的实现，以便需要的人的用。

算法导论中的伪代码

这里先贴出伪代码，这个我觉得算是比较好理解快排的了，更重要的非常简洁。对于记性不好的我，非常友好。

QUICKSORT(A, p, r)
 if  p < r
       q = PARTITION(A，p，r）
      QUICKSORT(A，p，q-1)
       QUICKSORT(A，q+1，r)

PARTITION(A, p, r)
  x = A[r]
  i = p-1
  for j = p to r-1
          if A[j] <= x   //<=与书上有区别，符号的区别，不会打那个。。。。
               i = i + 1
               exchange A[i] with A[j]
  exchange A[i+1] with A[r]
  return i + 1

理解的话，我用大白话叙述一下。目的将数组划分为 4 个部分，1：比 x 小的，2：为比 x 大，3：等于 x 的，4: 可能为空。粘一些书上的话。设任意p -> r，数组下标为k。

1. 当 p ≤ k ≤ i ， 则 A[k] ≤ x
2. 当 i+1 ≤ k ≤ j-1，则 A[k] > x
3. 当 k = r ，则 A[k] = x
   证明：第一轮迭代之前是成立的，每一轮迭代都成立。
   第一轮迭代之前：
   i = p-1 ，j = p，所以1，2 这两成立，因为没有值在 [p ，i] 和 [i+1，j-1]之间。k = r，A[k] = A[r] = x。
   每一轮迭代：
   存在两种情况：
   A[j] > x ，j=j+1，i不变，只有 j 变化了，所以只要条件2后半部分 k ≤ j-1，k=j，A[k] > x成立，条件1，2，3成立。
   A[j] ≤ x，i=i+1，交换 A[i=i+1] 和 A[j] , k=j，在[p，i]，A[i=i+1]=A[j] ≤ x，条件1满足，我们知道在迭代前，A[i+1] > x ，因为 k ≥ i+1，A[k] > x。所以交换的结果为 A[j] > x，永远确保A[j-1] > x。
   如果不能理解的话，去看书本，或者其他博主的回答吧。就不粘图了。

基于java语言的代码实现

回到我们实现代码上来。用static 因为在main 中运行。

public class QuickSort {


    public static int partition(int[] Array, int start, int end){
        int x = Array[end];
        int i = start-1;
        for (int j = start; j <= end-1; j++) {
            if(Array[j] <= x){
                i = i + 1;
                exchange(Array,i,j);
            }
        }
        exchange(Array,i+1,end);
        return i+1;
    }

    public static void exchange(int[] Array, int i, int j){
        int temp = Array[i];
        Array[i] = Array[j];
        Array[j] = temp;
    }

    public static void quickSort(int [] Array, int start, int end){
        if(start < end){
            int mid = partition(Array,start,end);
            quickSort(Array,start, mid -1);
            quickSort(Array, mid+1, end);
        }
    }

    public static void main(String[] args) {
        int[] Array  = new int[]{2,8,7,1,3,5,6,4};
        arrayToString(Array);
        quickSort(Array,0,Array.length-1);
        arrayToString(Array);
        Array  = new int[]{10,1,6,9,4,9,18};
        arrayToString(Array);
        quickSort(Array,0,Array.length-1);
        arrayToString(Array);

    }

    public static void arrayToString(int [] Array){
        System.out.print("[");
        for (int i = 0; i < Array.length; i++) {
            if(i != Array.length -1){
                System.out.print(Array[i]+",");
            }else {
                System.out.print(Array[i]);
            }
        }
        System.out.print("]\n");
    }

}

这是运行结果：

[2,8,7,1,3,5,6,4]
[1,2,3,4,5,6,7,8]
[10,1,6,9,4,9,18]
[1,4,6,9,9,10,18]

总结

用这个去理解的话，只要设置好初始值以及结束值和一个比较条件即可。x = Array[end] , i = start -1 ，
j=start 且 j <= end-1, 用Array[j] 和 x 比较，返回 =x 的位置即 i+1。