快速排序

什么是快速排序呢？按照他的定义来是找到一个数使得它左边和右边都是有序的。那么如何实现全部都有序的，这就需要我们使用分治和递归的思想。

快速排序基准的选择

基本上我们选择基准是选择第一个元素作为基准，一旦选择了基准，就要进行一个判断，要使得他左边的数都小于它右边的都大于大，反过来也行。

算法实现

快排的分治其实跟归并差不太多，分治是先从两个开始以中间为界左右同时进行，而快排是以right- -和left+ + 相等为界，到两边进行递归。归并可以看着我之前写的这个

好了，接下来我们看具体的如何让他按照我们的想法进行。

创建快排类

public class MyQuickSort
   
    > {
       private AnyType[] myArray;    private int left,right;    public MyQuickSort(AnyType[] a){
           this.myArray=a;        this.left=0;        this.right=a.length;        myquick(left,right-1);    }

我们可以让他是泛型的，到时候我们在实现的时候只用给他注入类型即可。然后我们定义一个泛型数组用于接收实现的时候传递过来的数据。

排序

好，我们看到这里，通过上面的构造方法，我们进入了这个快排的方法，首先我们得保证左边界不能大于右边界吧，因为一旦大了说明你这个就有问题了呀。也就是会下标越界，所以我们当他们左边界大于右边界的时候直接给他返回就好。

然后我们看我们定义了i=left j=right 还用一个x暂时保存基准的值，从刚开始我们就开始进入一个死循环，直至i=j的时候退出，因为这说明进来的是一个元素。然后我们先从数组尾进行判断，找到一个比基准大或者比基准小的都行，我这边安排的是比基准小的，你找到了则退出这个for循环，然后从左边界开始寻找比基准大的，直至i=j或者找到了。然后交换位置。

当这个while循环退出时，我们满足的条件是i=j对不对，但在其过程当中，我们是不是把小于基准的放在了i=j的左边，大的放在了i=j的右边？对吧，所以i=j这个位置一定是一个比基准小的数，这就是为什么要从末尾开始寻找的原因，如果你从左边开始寻找，相等的这个位置的值就会大于基准。好了然后我们把他们交换一下就好了，也就是基准的元素与i=j这个位置的元素交互一下，这样就保证了左右都有序！。然后我们从这个位置出发，左边递归右边递归是不是到最后都有序了！！

好吧，干说是太费脑子，那我们上图！

private void myquick(int left,int right){
           if(left>right)            return;        AnyType x=myArray[left];//record this 值        int i=left;        int j=right;        while (i!=j){
               for(;i!=j;j--)                if(x.compareTo(myArray[j])>0)                    break;            for (;i!=j;i++)                if (x.compareTo(myArray[i])<0)                    break;            swapThing(i,j);        }//when out this position 值左边都是小于基准，右边都是大于基准        //所以交换当前位置与基准的值        int position=i=j;        swapThing(left,position);        //左边右边依次进行递归        myquick(left,position-1);        myquick(position+1,right);    }

交换和打印

private void swapThing(int i,int j){
           AnyType x=myArray[i];        myArray[i]=myArray[j];        myArray[j]=x;    }    public void print(){
           for (AnyType x:myArray)            System.out.println(x);    }}

测试

public class testt {
       public static void main(String[] args) {
           Integer[] a=new Integer[]{
   7,6,9,2,1};        MyQuickSort
   
     quick=new MyQuickSort<>(a);        quick.print();    }}

在这里插入图片描述

转载地址：http://zgqai.baihongyu.com/

你可能感兴趣的文章