介紹

快速排序是對冒泡排序的一種改進，

思想：將排序的資料分為兩部分，一部分資料所有資料小于另一部分所有資料，然后在分別進行快速排序，排序程序可遞回，從而得到有序序列，

它使用分治法（Divide and conquer）策略，把一個串行分為兩個子串行，

步驟

1. 從數列中選一個元素，作為“基準”（pivot）；

2. 重新排序數列，比基準小的值在左邊（left），大的值在右邊（right），等值隨意；得到兩個子數列：left、right；

3. left子數列重復1和2；right子數列重復1和2；遞回，

代碼

        /// <summary>
        /// 一次排序單元，左邊小，右邊大
        /// </summary>
        /// <param name="array">排序陣列</param>
        /// <param name="left">排序起始位置</param>
        /// <param name="right">排序結束位置</param>
        /// <returns></returns>
        private static int SortUnit(int[] array, int left, int right)
        {
            int pivot = array[left];
            while (left < right)
            {
                // 從后向前搜索比 pivot 小的值
                while (array[right] >= pivot && right > left)
                {
                    --right;
                }
                // 比 pivot 小的放左邊
                array[left] = array[right];
                // 從前向后搜索比 key 大的值
                while (array[left] <= pivot && right > left)
                {
                    ++left;
                }
                // 比 pivot 大的放右邊
                array[right] = array[left];
            }
            // 左邊都比 pivot 小，右邊都比 pivot 大
            // 將 pivot 放在游標當前位置，此時 left 等于 right
            array[left] = pivot;
            foreach (var i in array)
            {
                Console.Write("{0}\t", i);
            }
            Console.WriteLine();
            return right;
        }
        /// <summary>
        /// 左邊小，右邊大
        /// </summary>
        /// <param name="array">排序陣列</param>
        /// <param name="left">排序起始位置</param>
        /// <param name="high">排序結束位置</param>
        /// <returns></returns>
        public static void QuickSort(int[] array, int left, int right)
        {
            if (left >= right)
                return;
            // 完成一次單元排序
            int index = SortUnit(array, left, right);
            // 對左邊單元進行排序，遞回
            QuickSort(array, left, index - 1);
            // 對右側單元進行排序，遞回
            QuickSort(array, index + 1, right);
        }
        static void Main(string[] args)
        {

            #region 快速排序演算法
            int[] array = { 149, 100, 112, 38, 80, 35, 615, 297, 592, 976, 143, 217 };
            QuickSort(array, 0, array.Length - 1);
            Console.ReadLine();
            #endregion
        }

View Code

性能分析

演算法復雜度

快速排序的性能高度依賴于選擇的基準值，

最糟糕的：O(n ^ 2)；

　　在最糟糕的情況下，堆疊長O(n)，在呼叫堆疊的每層都涉及O(n)個元素，完成每層所需的時間都為O(n)；O(n) * O(n) = O(n ^ 2)；

最佳的：O(n log n)；

　　在最佳的情況下，中間的元素作為基準值，堆疊長O(log n)；每一層運行時間為O(n)；O(n) * O(log n) = O(n log n)；

平均的：O(n log n)；

　　最佳即平均，只要每次都隨機地選擇一個陣列元素作為基準值，快速排序的平均運行時間就將為O(n log n)，

快速排序是最快的排序演算法之一，

穩定性：不穩定，如排序中有相同的值，排序也可交換亦不可交換；

　　注：快速排序原本是不穩定的排序方法，但若待排序記錄中只有一組具有相同基準值的記錄，而選擇的軸值恰好是這組相同基準值中的一個，此時的快速排序就是穩定的，

　　穩定性判斷條件：對于不穩定的排序演算法，只要舉出一個實體，即可說明它的不穩定性；而對于穩定的排序演算法，必須對演算法進行分析從而得到穩定的特性，需要注意的是，排序演算法是否為穩定的是由具體演算法決定的，不穩定的演算法在某種條件下可以變為穩定的演算法，而穩定的演算法在某種條件下也可以變為不穩定的演算法，

本文地址： https://www.cnblogs.com/Fletcher/p/11777121.html

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/135937.html

標籤：其他

上一篇：歸并排序

下一篇：閑的