快速排序.gif

1. 快速排序，也叫分治法，是9種經典排序方法中效率最高的。

2. 原理：以升序為例，每輪比較之后，保證基準值左邊的數比它小，右邊的數比它大。

3. 思路：使用分治法(Divide and conquer)策略來把一個序列(list)分成兩個子序列(sub-list)。
   （3.1）從數列中挑出一個元素，稱為"基準"(pivot)。
   （3.2）重新排列數列，所有元素比基準值小的擺放在基準左邊，所有元素比基準值大的擺放在基準右邊。
   ......
   （3.3）遞歸地(recursive)把小于基準值元素的子數列和大于基準值元素的子數列再次進行排序。
   4.舉例：
   （1）要排序的數組是：[15, 22, 35, 9, 16, 33, 15, 23, 68, 1, 33, 25, 14]。

       //相對來說，快速排序數值越大速度越快 。  快速排序是所有排序里面最快的
   class Program
   {
    static void Main(string[] args)
    {
        int[] arr = { 15, 22, 35, 9, 16, 33, 15, 23, 68, 1, 33, 25, 14 }; //待排序數組
        //控制臺遍歷輸出
        Console.WriteLine("排序前的數列：");
        foreach (int item in arr)
            Console.Write(item + " ");
   
   
        QuickSort(arr, 0, arr.Length - 1);  //調用快速排序函數。傳值(要排序數組，基準值位置，數組長度)
   
        //控制臺遍歷輸出
        Console.WriteLine();
        Console.WriteLine("排序后的數列：");
        foreach (int item in arr)
            Console.Write(item+" ");
   
        Console.ReadLine();
    }
   
    private static void QuickSort(int[] arr, int begin, int end)
    {
        if (begin >= end) return;   //兩個指針重合就返回，結束調用
        int pivotIndex = QuickSort_Once(arr, begin, end);  //會得到一個基準值下標
   
        QuickSort(arr, begin, pivotIndex - 1);  //對基準的左端進行排序  遞歸
        QuickSort(arr, pivotIndex + 1, end);   //對基準的右端進行排序  遞歸
    }
   
    private static int QuickSort_Once(int[] arr, int begin, int end)
    {
        int pivot = arr[begin];   //將首元素作為基準
        int i = begin;
        int j = end;
        while (i < j)
        {
            while (arr[j] >= pivot && i < j)  //從右到左，尋找第一個小于基準pivot的元素
            {
                j--; //指針向前移
            }
            arr[i] = arr[j];  //執(zhí)行到此，j已指向從右端起第一個小于基準pivot的元素，執(zhí)行替換
   
            
            while (arr[i] <= pivot && i < j) //從左到右，尋找首個大于基準pivot的元素
            {
                i++; //指針向后移
            }
            arr[j] = arr[i];  //執(zhí)行到此,i已指向從左端起首個大于基準pivot的元素，執(zhí)行替換
        }
   
        //退出while循環(huán),執(zhí)行至此，必定是 i= j的情況（最后兩個指針會碰頭）
        //i(或j)所指向的既是基準位置，定位該趟的基準并將該基準位置返回
        arr[i] = pivot;
        return i;
    }
   

   }
   5.輸出結果

   排序前的數列：
   15 22 35 9 16 33 15 23 68 1 33 25 14
   排序后的數列：
   1 9 14 15 15 16 22 23 25 33 33 35 68
   

• 快速排序的時間主要耗費在劃分操作上，對長度為k的區(qū)間進行劃分，共需k-1次關鍵字的比較；

• 最壞情況是每次劃分選取的基準都是當前無序區(qū)中關鍵字最小(或最大)的記錄，劃分的結果是基準左邊的子區(qū)間為空(或右邊的子區(qū)間為空)，而劃分所得的另一個非空的子區(qū)間中記錄數目，僅僅比劃分前的無序區(qū)中記錄個數減少一個。時間復雜度為O(n*n)；

• 在最好情況下，每次劃分所取的基準都是當前無序區(qū)的"中值"記錄，劃分的結果是基準的左、右兩個無序子區(qū)間的長度大致相等?？偟年P鍵字比較次數：O(nlogn)；

• 盡管快速排序的最壞時間為O(n*n)，但就平均性能而言，它是基于關鍵字比較的內部排序算法中速度最快者，快速排序亦因此而得名。它的平均時間復雜度為O(nlogn)。