《java kuaisu排序算法》

 快速排序算法

package com.jx.p2p.service;



public class QuickTest {
    //快速排序----比start索引元素小的元素全部放在左侧，比start索引元素大的元素全部放在右侧。
    public static int QuickTestMethod(int[] msgs,int start,int end){
        //从小到大排序
        //快速排序思路   以start索引上的数字为中轴线，从右到左找到第一个比中轴数字小的数字(索引x)，并放在中轴线所在索引上
        //②再从左到右找第一个大于(原)中轴线上的数字(索引y)，并将此中轴线上的数字放置到上面的索引x位置上
        //③然后再从索引x向左找第一个小于(原)中轴线的数据(索引z)，然后将此数据放在(索引y)位置上
        //④再从索引y开始向右查找第一个大于(原)中轴线上的数据，并将此数据放在索引z位置上
        //⑤.......知道比较时，start值>=end时，上面的循环判断就结束。并且将(原)中轴线上的数据放置到start位置上。
        /***以上就是快速排序的原理和思路****/
        int centreVal = msgs[start];  //中轴线数据
        while(start<end){//整个过程start<end，找中轴线数据应该所处的位置
            //先从右(end开始)向左找第一个小于中轴线数据的数据
            while(start<end && msgs[end]>=centreVal){//必须有start<end判断条件   要不然索引减去后，end<start  再匹配就没有任何意义了   
                /*****相等的处理****因为假如中轴线和最后一位相等的话，并且假如不处理的话会存在死循环里**/
                end--;
            }
            msgs[start]=msgs[end];//找到一个小于中轴数据的数据，然后此数据左移
            //再从左(start开始)向右找第一个大于(原)中轴线数据的数据
            while(start<end && msgs[start]<=centreVal){
                /*****相等的处理******/
                start++;
            }
            msgs[end]=msgs[start];//找到一个大于中轴数据的数据，然后此数据右移
            //一次从右向左，然后从左向右的，移动两次，右==小的==左移   左==大的==右移
        }
        //找到中轴应该位置  右--》左   左--》右   左侧的最后一次移动的索引上的元素此时为无效数据，应该替换为原中轴数据
        msgs[start]=centreVal;
        System.out.println("快速排序算法，移动后此时数组中轴线的位置为：第【"+start+"】位---且数据："+centreVal+"左侧的数据全小，右侧的数据全大");
        for(int intem:msgs){
            System.out.println("【"+intem+"】");
        }
        return start;
    }
   
   
    public static void main(String[] args) {
        int[] msglist = new int[]{56,65,45,85,95,25,15,77,56};
        checkInt(msglist,0,msglist.length-1);
        for(int item:msglist){
            System.out.print("["+item+"]");
        }
    }
   
    public static void checkInt(int[] args,int left,int right){
        if(left<right){   //必须加此判断，因为加入left>right，就会落于死循环
            int indexnum = QuickTestMethod(args,left,right);//先对给定的数组进行一次性移位操作，并且返回中轴线数据的安放位置
            //上面一次移动将数据分为了两部分，一部分是比中轴线数据小的数据、一部分是比中轴线数据大的数据
            //针对上面以中轴线为中心的两部分数组，分别继续上面的分组操作
            checkInt(args,left,indexnum-1);//针对中轴数据所落位置的前半部分进行移位操作
            checkInt(args,indexnum+1,right);//针对中轴数据所落位置的后半部分进行移位操作
        }
    }
   
}