平均時間復(fù)雜度： O(NLogN)
最好情況時間復(fù)雜度： O(NLogN)
最差情況時間復(fù)雜度： O（N^2）
所需要額外空間： O(NLogN)
穩(wěn)定性：不穩(wěn)定

快速排序采用了分治策略，其基本思想是：

通過一趟排序，將待排記錄分割為獨立的兩部分，其中一部分記錄的關(guān)鍵字均比另一部分記錄的關(guān)鍵字小。
不斷重復(fù)這個步驟，直到每個部分都只有一個記錄為止。

其核心是一個Partition函數(shù)，這個函數(shù)可以選取一個關(guān)鍵字（稱之為Pivot），然后把它放到一個合適的位置，使在它左邊的值都比它小，在它右邊的值都比它大。

具體實現(xiàn)（In JAVA）

package com.yenghye.sort;

public class Sort {

    public static void QuickSort(int[] arr, int low, int high) {
        int pivot;
        if (low < high) {
            pivot = Partition(arr, low, high);
            QuickSort(arr, low, pivot - 1);
            QuickSort(arr, pivot + 1, high);
        }
    }

    private static int Partition(int[] arr, int low, int high) {
        int pivotkey = arr[low];

        while (low < high) {
            while (low < high && pivotkey <= arr[high])
                high--;
            arr[low] = arr[high];

            while (low < high && pivotkey >= arr[low])
                low++;
            arr[high] = arr[low];
        }
        arr[low] = pivotkey;

        return low;
    }
}

Partition函數(shù)除了可以應(yīng)用在快速排序算法當(dāng)中，還可以用來實現(xiàn)對數(shù)組中第k大的數(shù)字的查找。
比如題目

數(shù)組中有一個數(shù)字出現(xiàn)的次數(shù)超過數(shù)組長度的一半，請找出這個數(shù)字。例如輸入一個長度為9的數(shù)組{1,2,3,2,2,2,5,4,2}。由于數(shù)字2在數(shù)組中出現(xiàn)了5次，超過數(shù)組長度的一半，因此輸出2。如果不存在則輸出0。

容易想到，如果一個數(shù)組當(dāng)中某個元素的個數(shù)超過了數(shù)組長度的一半，那么如果對這個數(shù)組排序，這個數(shù)組正中間位置上的數(shù)一定是我們要找的那個數(shù)字。
那么接下來的事很簡單，我們只要用一個現(xiàn)成的函數(shù)：Partitan，如果我們得到的pivot剛剛好在數(shù)組的正中間，那么我們就找到了這個數(shù)，如果沒有得到，根據(jù)pivot和正中間的位置關(guān)系，縮小范圍繼續(xù)查找就可以了。
實現(xiàn)（In JAVA）

public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        if(array == null || array.length == 0)
            return 0;
        int middle = array.length >> 1;
        int start = 0;
        int end = array.length - 1;
        int pivot = Partition(array, start, end);
        
        while(pivot != middle)
        {
            if(pivot > middle)
            {
                end = pivot - 1;
                pivot = Partition(array, start, end);
            }
            else
            {
                start = pivot + 1;
                pivot = Partition(array, start, end);
            }
                
        }
        int result = array[middle];
        if(CheckMoreThanHalf(array, result)!=0)
            return 0;
        return result;
        
    }
    
    private int CheckMoreThanHalf(int[] array, int result)
    {
        int times = 0;
        for(int i = 0; i < array.length; i++)
        {
            if(result == array[i])
                times++;
        }
        
        if((times << 1) > array.length)
            return 0;
        return 1;
    }
    
    private int Partition(int[] a, int low, int high)
    {
        int pivotkey = a[low];
        while(low < high)
        {
            while(low < high && a[high] >= pivotkey)
                high--;
            a[low] = a[high];
            
            while(low < high && a[low] <= pivotkey)
                low++;
            a[high] = a[low];
        }
        a[low] = pivotkey;
        return low;
    }
}

***除了用Partition，這道題還有另一種解法，其解題核心是：數(shù)組中的一個數(shù)字出現(xiàn)的次數(shù)超過數(shù)組長度的一半，就意味著它出現(xiàn)的次數(shù)比其他所有的數(shù)字出現(xiàn)的次數(shù)加起來還多。那么我們只要從前往后遍歷整個數(shù)組，選中一個數(shù)字為備選，并記錄它的次數(shù)，如果接下來出現(xiàn)的數(shù)字和備選相等，那么增加次數(shù)，不等則減少次數(shù)。當(dāng)次數(shù)為0的時候，則說明遍歷到此為止，相等和不等的個數(shù)相互抵消了，則應(yīng)當(dāng)選擇一個新的備選，并將次數(shù)設(shè)置為1.
這個思路很清晰，代碼寫出來也很簡單，就不寫了。

接下來再舉個用Partition函數(shù)解決問題的例子。

輸入n個整數(shù)，找出其中最小的K個數(shù)。例如輸入4,5,1,6,2,7,3,8這8個數(shù)字，則最小的4個數(shù)字是1,2,3,4,。

想到用Partition函數(shù)來解決問題很容易，一直找直到pivot為k-1就可以了。這樣從下標(biāo)0到下標(biāo)k-1的k個數(shù)，就是最小的k個數(shù)了。
但是解決問題之前要知道，Partition會改變輸入數(shù)組內(nèi)的元素順序，以及，這種方法比較適合n的數(shù)量較小的情況。

import java.util.*;
public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        if(input == null || input.length == 0 || input.length < k)
            return new ArrayList();
        
        int start = 0;
        int end = input.length-1;
        int pivot = Partition(input, start, end);
        
        while(pivot != k-1){
            if(pivot > k-1){
                end = pivot - 1;
                pivot = Partition(input, start, end);
            }
            else {
                start = pivot + 1;
                pivot = Partition(input, start, end);
            }
        }
        ArrayList<Integer> result = new ArrayList();
        for(int i = 0; i < k; i++)
            result.add(Integer.valueOf(input[i]));
        return result;
    }
    
    private int Partition(int[] a, int low, int high)
    {
        int pivotkey = a[low];
        while(low < high) {
            while(low < high && a[high] >= pivotkey)
                high--;
            a[low] = a[high];
            
            while(low < high && a[low] <= pivotkey)
                low++;
            a[high] = a[low];
        }
        a[low] = pivotkey;
        return low;
    }
}