经典排序算法--快速排序

快速排序原理

　　快速排序是基于“分治法”原理实现，所谓分治法就是不断的将原数组序列按照一定规律进行拆分，拆分后各自实现排序直到拆分到序列只剩下一个关键字为止。快速排序首先选取一个关键字为标志位（关键字的选取影响排序效率），然后将序列中小于标志位的关键字移动至标志位左侧，大于标志位的关键字移动至右侧。一趟比较完成后，整个序列以选取的标志位为界，左侧均小于标志位，右侧均大于关键字。但左右两侧内部并不是有序的(左右两侧关键字个数也不一定相同)。进而继续将左右两侧分别再以这种方式进行排序，直到将序列拆分的剩余一个关键字为止，整个序列即变成有序。

图解快速排序

　　下面以[6 ,1 ,2 ,7, 9 ,3 ,4 ,5 ,10 ,8]序列为例用图解的方式讲解快速排序的过程

 　　

　　这里我们选取标志位的方式是：序列左边第一个关键字即 6 并放入标志位变量flag中 ，然后将L（left）指针指向最左边，将R（right）指针指向最右边。

　　然后从右边指针开始让R指针指向的关键字与标志位flag比较，如果关键字大于或等于flag，则继续向左移动(右侧关键字本身就要大于flag)，直到找到小于flag的关键字，即关键字5。R指针停止移动。并开始让L指针指向的关键字与flag比较，如果小于flag则L指针继续向后移动，直到找到大于flag的关键字，即关键字7。此时序列如下图所示　　

　　

　　此时再比较指针L是否小于R，满足条件，交换两指针对应的值，即7与5交换。交换后仍满足L<R指针，继续从R指针与flag比较，找小于6的关键字，即指向关键字4，R指针停止移动。并开始让L指针指向的关键字与flag比较，找大于6的关键字，即指向关键字9。此时序列如下图所示

　　

　　此时仍满足L<R的条件，所以将9与4交换。继续按照上述步骤进行，R向前移动并找到小于flag的关键字3，R指针停止移动。并开始L指针向后移动，当L指针指向3时，虽然满足3<6，但此时不再满足L<R(此时L=R)。然后将L和R同时指向的关键字3移动至序列左边第一个关键字中，并将flag放入L和R指向的位置，这一趟比较结束。此时序列如下图所示　　

　　从图中可以看到，一趟比较后，整个序列以我们选取的标志位为界，将整个序列分为两个部分，其中左边部分关键字都小于标志位，而右侧部分均大于标志位。但左右两侧内部无序。

　　然后再将左右两侧子序列分别执行上述步骤，直至左右两侧剩余一个元素无法再拆分时，整个序列即为有序。　　

代码实现

 1 public static void quickSort(int[] array ,int left,int right){
 2         int l,r,flag,temp;
 3         if(left >= right){
 4             return;
 5         }
 6         l = left;
 7         r = right;
 8         flag = array[left];
 9         while (l < r){
10             //先从右边找
11             while (array[r] >= flag && l < r){
12                 r --;
13             }
14             //再从左边找
15             while (array[l] <= flag && l < r){
16                 l ++;
17             }
18             //交换
19             if(l < r){
20                 temp = array[l];
21                 array[l] = array[r];
22                 array[r] = temp;
23             }
24         }
25         //一趟交换完将基准值放入临界位置
26         array[left] = array[l];
27         array[l] = flag;
28         //向左递归
29         quickSort(array,left,l-1);
30         quickSort(array,l+1,right);
31     }

代码分析

　　1）选取数组左边第一个关键字为标志位，并暂存至flag中(注：标志位选取的方式可用不同方式)

　　2）第一层while循环用于保证一趟比较遍历完所有关键字

　　3）第二层第一个while循环用于从右侧依次向左找小于flag的关键字

　　4）第二层第二个while循环用于从左侧依次向右找大于flag的关键字

　　5）第二层的两个while循环执行后，如果l<r则进行交换

　　6）一趟比较后，将l和r共同指向的关键字放入最左侧，即flag的选取位置，并将flag值放入此位置，此时序列便以flag为界，左边均小于flag，右边均大于flag

　　7）然后再用“分治法”分别向左和向右递归执行上述步骤，直到无法拆分为止，整个序列即为有序

时间复杂度

　　快速排序时间复杂度为O(NlogN)

测试算法执行效率

　　与前面的排序算法相同，我们依然生成10万个随机数的数组，使用插入排序方法进行排序，看其执行时间。测试代码如下

public static void main(String[] args){
        int array[] = new int[100000];
        for (int i = 0; i < 100000; i++) {
            array[i] = (int) (Math.random()*1000000);
        }
        long begin = System.currentTimeMillis();
        quickSort(array,0,array.length-1);
        System.out.println("总耗时="+(System.currentTimeMillis()-begin)+"毫秒");
    }

测试结果

　　可以看到快速排序对10万个关键字的数组进行排序，只用了50多毫秒，相比我们前面讲解的希尔排序又快了许多。

总结

　　快速排序每趟比较首先选取某个关键字作为标志位，然后使用左右指针遍历数组关键字与flag进行比较，并将右侧小于flag的关键字与左侧大于flag的关键字进行交换。然后再使用“分治法”方式对数组拆分，将数组以flag为界拆分为左右两个子序列，并对两个子序列递归执行上述步骤，直到子序列剩余1个关键字无法拆分为止，此时整个序列即为有序。