排序算法之快速排序 java实现

---

快速排序.png

如上图所示：给定数组序列【8,7,15,5,20】，
1.首先挖坑用temp保存数字数组0位置的数据8，使用两个标志位i ，j。
2.将j向左移动查找小于temp的数据并将其填充到i的位置（挖坑填数），此时将i向前移动一位（i++）。
3.将i向右查找大于temp值的数据，只要查询到大于temp的数据将数据填充到j的位置。同时j向后移动一位（j--）
4.重复进行2,3步骤直到i不小于j则成功将数据分成两部分大于temp的在右边，小于temp的在左边
5.接着又将数据分成左右两份进行 1,2,3,4步骤（分治），递归调用，直到被拆分的数据开始位置与结束位置相等则结束
注 上图只画出了一个部分的流程并不完整。

快速排序java实现

---

   public static void  quickSort(int[] num,int start,int end){
        //如果开始位置大于或等于最终位置则直接返回
        if(start>=end) return;
        int i,j;
        i=start;j=end;
        //挖坑记录第一个位置的值num[i]
        int temp=num[i];
        while(i<j){
            //从坑的右边往左查找大于坑内数据的位置
            while(i<j&&num[j]>=temp) j--;
            if(i<j){
                //填补坑，同时j的位置出现新坑
                num[i]=num[j];
                i++;
            }
            //从i的左往右查找小于temp的值
            while(i<j&&num[i]<=temp) i++;
            if(i<j){
                num[j]=num[i];
                j--;
            }
        }
        num[j]=temp;
        quickSort(num, start, i - 1);//递归调用
        quickSort(num, i + 1, end);//递归调用

    }