快速排序

转自：http://developer.51cto.com/art/201403/430986.htm

高快省的排序算法

有没有既不浪费空间又可以快一点的排序算法呢？那就是“快速排序”啦！光听这个名字是不是就觉得很高端呢。

假设我们现在对“6  1  2 7  9  3  4  5 10  8”这个10个数进行排序。首先在这个序列中随便找一个数作为基准数（不要被这个名词吓到了，就是一个用来参照的数，待会你就知道它用来做啥的了）。为了方便，就让第一个数6作为基准数吧。接下来，需要将这个序列中所有比基准数大的数放在6的右边，比基准数小的数放在6的左边，类似下面这种排列：

3  1  2 5  4  6  9 7  10  8

在初始状态下，数字6在序列的第1位。我们的目标是将6挪到序列中间的某个位置，假设这个位置是k。现在就需要寻找这个k，并且以第k位为分界点，左边的数都小于等于6，右边的数都大于等于6。想一想，你有办法可以做到这点吗？

排序算法显神威

方法其实很简单：分别从初始序列“6  1  2 7  9  3  4  5 10  8”两端开始“探测”。先从右往左找一个小于6的数，再从左往右找一个大于6的数，然后交换他们。这里可以用两个变量i和j，分别指向序列最左边和最右边。我们为这两个变量起个好听的名字“哨兵i”和“哨兵j”。刚开始的时候让哨兵i指向序列的最左边（即i=1），指向数字6。让哨兵j指向序列的最右边（即=10），指向数字。

 

首先哨兵j开始出动。因为此处设置的基准数是最左边的数，所以需要让哨兵j先出动，这一点非常重要（请自己想一想为什么）。哨兵j一步一步地向左挪动（即j--），直到找到一个小于6的数停下来。接下来哨兵i再一步一步向右挪动（即i++），直到找到一个数大于6的数停下来。最后哨兵j停在了数字5面前，哨兵i停在了数字7面前。

现在交换哨兵i和哨兵j所指向的元素的值。交换之后的序列如下：

6  1  2  5  9 3  4  7  10  8

到此，第一次交换结束。接下来开始哨兵j继续向左挪动（再友情提醒，每次必须是哨兵j先出发）。他发现了4（比基准数6要小，满足要求）之后停了下来。哨兵i也继续向右挪动的，他发现了9（比基准数6要大，满足要求）之后停了下来。此时再次进行交换，交换之后的序列如下：

6  1  2 5  4  3  9  7 10  8

第二次交换结束，“探测”继续。哨兵j继续向左挪动，他发现了3（比基准数6要小，满足要求）之后又停了下来。哨兵i继续向右移动，糟啦！此时哨兵i和哨兵j相遇了，哨兵i和哨兵j都走到3面前。说明此时“探测”结束。我们将基准数6和3进行交换。交换之后的序列如下：

3  1 2  5  4  6  9 7  10  8

到此第一轮“探测”真正结束。此时以基准数6为分界点，6左边的数都小于等于6，6右边的数都大于等于6。回顾一下刚才的过程，其实哨兵j的使命就是要找小于基准数的数，而哨兵i的使命就是要找大于基准数的数，直到i和j碰头为止。

OK，解释完毕。现在基准数6已经归位，它正好处在序列的第6位。此时我们已经将原来的序列，以6为分界点拆分成了两个序列，左边的序列是“3  1 2  5  4”，右边的序列是“9  7  10  8”。接下来还需要分别处理这两个序列。因为6左边和右边的序列目前都还是很混乱的。不过不要紧，我们已经掌握了方法，接下来只要模拟刚才的方法分别处理6左边和右边的序列即可。现在先来处理6左边的序列现吧。

左边的序列是“3  1  2 5  4”。请将这个序列以3为基准数进行调整，使得3左边的数都小于等于3，3右边的数都大于等于3。好了开始动笔吧

如果你模拟的没有错，调整完毕之后的序列的顺序应该是：

2  1  3  5  4

OK，现在3已经归位。接下来需要处理3左边的序列“2 1”和右边的序列“5 4”。对序列“2 1”以2为基准数进行调整，处理完毕之后的序列为“1 2”，到此2已经归位。序列“1”只有一个数，也不需要进行任何处理。至此我们对序列“2 1”已全部处理完毕，得到序列是“1 2”。序列“5 4”的处理也仿照此方法，最后得到的序列如下：

1  2  3 4  5  6 9  7  10  8

对于序列“9  7  10  8”也模拟刚才的过程，直到不可拆分出新的子序列为止。最终将会得到这样的序列，如下

1  2  3 4  5  6  7  8 9  10

到此，排序完全结束。细心的同学可能已经发现，快速排序的每一轮处理其实就是将这一轮的基准数归位，直到所有的数都归位为止，排序就结束了。下面上个霸气的图来描述下整个算法的处理过程。

这是为什么呢？

快速排序之所比较快，因为相比冒泡排序，每次交换是跳跃式的。每次排序的时候设置一个基准点，将小于等于基准点的数全部放到基准点的左边，将大于等于基准点的数全部放到基准点的右边。这样在每次交换的时候就不会像冒泡排序一样每次只能在相邻的数之间进行交换，交换的距离就大的多了。因此总的比较和交换次数就少了，速度自然就提高了。当然在最坏的情况下，仍可能是相邻的两个数进行了交换。因此快速排序的最差时间复杂度和冒泡排序是一样的都是O(N2)，它的平均时间复杂度为O(NlogN)。其实快速排序是基于一种叫做“二分”的思想。我们后面还会遇到“二分”思想，到时候再聊。先上代码，如下

public class QuickSort {
    private static void sort(int[] intArrays ,int left,int right) {
        //如果左索引大于右索引，直接返回
        if(left > right){
            return;
        }
        int i = left ;
        int j = right;
        int temp = intArrays[left];//设置基准值，将最左端元素作为基准值
        while(i != j){
            //往左移位，直到小于temp
            while(i<j && intArrays[j]>=temp){
                j--;
            }
            //往右移位，直到大于temp
            while(i<j && intArrays[i]<=temp){
                i++;
            }
            if(i < j){
                //如果i<j,也就是说i和j还没相遇时，交换彼此的数据
                NumberUtils.exchange(intArrays,i,j);
            }
        }
        //当哨兵i与哨兵j相遇时退出循环，将哨兵i与基位交换位置
        NumberUtils.exchange(intArrays,left,i);
        //下一次迭代
        sort(intArrays,left,i-1);//左半边
        sort(intArrays,j+1,right);//右半边
    }
 
    /**
     * 执行入口，intArrays：待排序的数组，displaySort：是否显示排序前和排序后的内容。
     *
    */
    public static void run(int intArrays[],boolean displaySort){
        //克隆一份数组
        int arrays[]= intArrays.clone();
        // 判断是否需要显示排序前的内容
        if(displaySort){
            NumberUtils.display(arrays,1);
        }
        // 记录开始时间
        long startTime=System.currentTimeMillis();
        sort(arrays,0,arrays.length-1);
        // 记录结束时间
        long endTime=System.currentTimeMillis();
        // 判断是否需要显示排序前的内容
        if(displaySort){
            NumberUtils.display(arrays,2);
        }
        System.out.println("快速排序用时："+(endTime-startTime)+"毫秒");
    }
/**
     * 测试排序用的主方法
    */
    public static void main(String[] args){
        //数组长度
        int length=30000;
        //最大值
        int max =100000000;
        //是否打印排序后的内容
        boolean display=true;
        //随机获取的排序数组
        int intArrays[]= NumberUtils.getRandomArs(length,max);
        //快速排序
        QuickSort.run(intArrays,display);
    }
}

运行结果：

排序前：30219946 49994982 92019983 92061993 68823407 65581837 42406960 46573221 41114308 ......53295442 11162732 2552911 96686132 1235026 41810573 93985951 42532276 76469405 83088302 
排序后：344 3474 3734 6663 11146 15237 15591 20634 26106 ......99957850 99959002 99961132 99967423 99982497 99984534 99985995 99989068 99991522 99996737 
快速排序用时：30毫秒

工具类用来生产随机数组和打印排序前后数组：

public class NumberUtils {
    /**
     * 获取随机int类型数组
     */
     public static int[] getRandomArs(int length,int max){
        int rs[]=new int[length];
        Random random=new Random();
        for(int i=0;i<length;i++){
            rs[i]=random.nextInt(max);
        }
        return rs ;
    }
    /**
     * 打印内容
    */
    public static void display(int intArrays[],int type){
        int count=0;
        if(type==2){
            System.out.print("排序后：");
        }else if(type==1){
            System.out.print("排序前：");
        }
        if(intArrays.length<40){
            for(int i:intArrays){
                System.out.print(i+" ");
            }
        }else {
            for(int i:intArrays){
                count++;
                if(count<10){
                    System.out.print(i+" ");
                }else if(count==10){
                    System.out.print("......");
                }else if(count> intArrays.length-10){
                    System.out.print(i+" ");
                }
            }
        }
        System.out.println();
    }

    /**
     * 交换数组中两个数的位置
    */
    public static void exchange(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}