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

2019-06-15 00:00:00 排序 快速 自白书

复习一下快速排序

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

《【新手自白书】简单快速排序的实现(JAVA)》
这样操作后,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

相关文章