【新手自白书】简单快速排序的实现（JAVA）

复习一下快速排序

• 快速排序（Quicksort）是对冒泡排序的一种改进。快速排序由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。（来自百度百科）
  冒泡排序传送门
  　　快速排序的思路大概可以这样理解：
  　　有两个人，L和R分别站在数据data的两端，这两个人规定了一个值K，只要R头顶的值不小于K，R就走一步，直到走到一个值比K小，L恰恰相反，L头顶的值如果不大于K，L就走一步，直到走到一个值比K大。当两个人都停下的时候，就交换头顶的值，如果两个人相遇在一个地方，就把相遇的那个值和K交换，然后两个人停止前行。

这样操作后，LR相遇点之前的值一定小于K，LR相遇点之后的值一定大于K，可以自行手动验证(#滑稽)。
之后我们可以以相遇点为分界，得到两个子表，这两个子表分别以这种方式进行操作，就可以把无序列变为有序列。本质上是递归。
需要注意的是，我们进行操作的时候必须按照先R后L的顺序才可以正确的递归，而K值一般取data[0]。

在方法设计上，要注意如何递归，我们给LR相遇点的下标取名mid，表总长length，左子表的下标值在0~mid-1,右子表的下标值在mid+1~length-1。所以我们每次递归都要返回mid值，才能正确的递归。

public int getMid(int[] list,int left,int right){
        right = right - 1 ;
        int key = list[left] ;
        while(left < right){
            while(left < right && list[right] > key){
                right -- ;
            }
            while(left < right && list[left] < key){
                left ++ ;
            }
            //mid = left ;
            int temp = list[left] ;
            list[left] = list[right] ;
            list[right] = temp ;
        }
        int temp = list[left] ;
        list[left] = key ;
        key = temp ;
        return left ;
    }

每次获取mid的方法完成。
递归方法很简单，只需要在一个方法里调用获取mid的方法即可。

public void sort(int[] list,int left,int right){
        int mid = 0 ;
        if(left < right){
            mid = this.getMid(list,left,right) ;
            this.sort(list, 0, mid-1) ;
            this.sort(list, mid+1, right) ;
        }
    }

总体类设计如下：

public class QSort{

    private int[] data = null ;
    //private int[] array = null ;

    public QSort(int[] data,int left,int right){
        this.setData(data) ;
        this.sort(data, left, right) ;
    }

    private void setData(int[] data){
        this.data = data ;
    }

    public String getArray(){
        String s = "排序后：" ;
        for(int i : this.data){
            s = s + i + " " ; 
        }
        return s ;
    }

    public void sort(int[] list,int left,int right){
        int mid = 0 ;
        if(left < right){
            mid = this.getMid(list,left,right) ;
            this.sort(list, 0, mid-1) ;
            this.sort(list, mid+1, right) ;
        }

    }
    public int getMid(int[] list,int left,int right){
        right = right - 1 ;
        int key = list[left] ;
        while(left < right){
            while(left < right && list[right] > key){
                right -- ;
            }
            while(left < right && list[left] < key){
                left ++ ;
            }
            //mid = left ;
            int temp = list[left] ;
            list[left] = list[right] ;
            list[right] = temp ;
        }
        int temp = list[left] ;
        list[left] = key ;
        key = temp ;
        return left ;
    }
} 

• 测试

public class Test {

    public static void main(String[] args) {

        System.out.println(new QSort(new int[]{7,1,4,2,9,3,8,5,10,6},0,10)
                            .getArray());

    }

}

• 结果

排序后：1 2 3 4 5 6 7 8 9 10