排序算法之快速排序

快速排序算法由于排序效率在同为O(N*logN)的几种排序方法中效率较高，因此经常被采用，再加上快速排序思想--分治法在实际处理问题中很实用，因此快速排序算法一直都是排序算法中比较受关注的一个，因此很有必要详细了解快排的实现原理。

快排的基本思想

1. 先从数列中取一个数作为基准数。
2. 分区过程，将比这个数大的数全放到它的右边，小于或者等于它的数全部放到它的左边。
3. 再对左右区间重复第二步，直到各区间只有一个数。

图解法看快排过程

假设现在对[6 1 2 7 9 3 4 5 10 8]这10个数排序。首先再这个序列中随便找一个数作为基准数。为了方便，一般都选择第一个数即6作为基准数。接下来需要将这个序列中所有比基准数大的数放在6的右边，比基准数小的数放在6的左边，类似如下序列：
[1 2 3 4 5 6 7 9 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），指向数字。

image.png
首先哨兵j开始移动。因为此处设置的基准数是最左边的数，所以需要让哨兵j先出动，这一点非常重要。哨兵j一步步向左移动（即j--），直到找到一个小于6的数停下来。接下来哨兵i再一步一步向右移动（即i++），直到找到一个大于6的数停下来。最后哨兵j停在数字5面前，哨兵i停在了数字7面前。
image.png
现在交换哨兵i和哨兵j所指向的元素的值。交换之后的序列如下：
[6 1 2 5 9 3 4 7 10 8 ]
image.png
到此，第一次交换结束。接下来开始哨兵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]

image.png
image.png
image.png
到此第一轮“探测”真正结束。此时以基准数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]

java 代码实现

package sortdemo;
import java.util.Arrays;
import java.util.Scanner;
public class QuickSort {
    public static void main(String[] args){
        System.out.print("Please input:\n");
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int[] arr = new int[n];
        for(int i=0;i<n;i++){
            arr[i]=scan.nextInt();
        }
        quickSort(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));
        
    
    }
    public static void quickSort(int[] arr, int left, int right){
        if(left<right){
            int q = partition(arr,left,right);
            quickSort(arr,left,q-1);
            quickSort(arr,q+1,right);
        }
    }
    public static int partition(int[]arr,int left,int right){
        int  i=left;
        int  j=right;
        int temp = arr[left];
        while(i<j){
            while(i<j&&arr[j]>=temp){
                j--;
            }
            arr[i]=arr[j];
            while(i<j&&arr[i]<=temp){
                i++;
            }
            arr[j]=arr[i];
        }
        arr[j]=temp;
        return j;
    }
}

算法复杂度分析

快速排序的运行时间与划分是否对称有关，其最坏情况发生在划分过程产生的两个区域分别包含n-1个元素和1个元素的时候。由于函数partition的计算时间为O(n),所以如果算法 partition的每一步都出现这种不对称划分，则其计算时间复杂性为O(n2)