递归算法实现快速排序

吃亏还不长记性没办法活该吃亏,就在上次笔试中遇到了让写排序算法可以根据isDesc来判断是否从小到大或者从大到小在这个过程中让我吃了大亏,按道理说这块随便写个算法就可以了但是面试官不是这样理解的,面试官要求应该是一个比较有灵魂的排序算法,比如那些比较经典的快速排序,并不是我所写的冒泡排序让我惨遭被刷。随后本人便回家开始学习一种可以拿的出手的排序算法,快速排序。
例如下面这个数组:{2,4,5,9,7,6,3,1,8}首先需要从第一个数字开始遍历,第一个数字为2,以2为支撑数X,开始从右向左遍历数组遇到比2小的变换位置即可,i是从左往右的遍历节点,j是从右往左的遍历节点,第一轮遍历如下:
支撑节点X=2:
1) 1,4,5,9,7,6,3, 2 ,8 i=0,j=7;
2) 1, 2 ,5,9,7,6,3,4,8 i=1,j=7;
这个时候你就会发现2的左边都是比它小的数,右边都是比它大的数,这时候以2为中心左边开始从新按照上面的方法来执行一次,发现2左边只有1所以不管左边,现在观察2的右边都是比他大的而且数大于一个,这时候以i+1为开始的位置,j=8依然是最后一个数字。
支撑节点X=5:
1)1, 2 ,4,9,7,6,3, 5 ,8 i=2,j=7;
2)1, 2 ,4, 5 ,7,6,3,9,8 i=3,j=7;
3)1, 2 ,4,3,7,6, 5 ,9,8 i=3,j=6;
4)1, 2 ,4,3, 5 ,6,7,9,8 i=4,j=6;
这时候第二轮已经结束;
第三轮以5为中心,左边从i=2开始到j=3结束,右边从i=5开始j=8结束一直重复以上步骤即可完成排序。
Java代码如下所示:



public class QuickSoft {
    public void soft(Boolean isDesc, int a[], int start, int end){
        if (start < end ){
            int s = a[start];
            int i = start;
            int j = end;
            while( i < j ){
                while (i < j && (isDesc ? a[j]>=s : a[j]<=s))     //{2,4,5,9,7,6,3,1,8}
                    j--;
                if (i < j && i != j)
                    a[i++] = a[j];
                while(i < j && (isDesc ? a[i] < s : a[i] > s))
                    i++;
                if (i < j && i != j)
                    a[j--] = a[i];
            }
            a[i] = s;
            soft(isDesc, a, start, i-1);
            soft(isDesc, a, i+1, end);
        }
    }
    public static void main(String[] args) {
        QuickSoft q = new QuickSoft();
        int b[] ={2,4,5,9,7,6,3,1,8};
        Boolean isDesc = false;
        q.soft(isDesc, b, 0, b.length-1);
        for (int i=0; i < b.length; i++)
            System.out.print(a[i]);
    }
}