都是Google幫我寫的

快速排序概念有些複雜(會用到遞迴的概念)

不過搞懂之後程式碼會很容易理解

基準點(pivot)是選擇最右邊

由小排到大時(!descend)

從左邊找比基準大的值

從右邊找比基準小的值

左邊較大值與右邊較小值互換

直到較大值在較小值的右邊時(left>right)中斷 (因為大的本來就要在右邊)

這時候最右邊的基準值與較大值(left)交換

開始左右兩邊遞迴

時間複雜度是O(NxlogN)

wiki上有更好的寫法

這個版本是以安全好懂為主

 

        private static void recursion_QuickSort(int[] array, int begin, int end, bool descend)
        {
            if (end > begin)
            {               
                int pivot = end;
                int right = end - 1;
                int left = begin;
                while (true)
                {
                    for (int i = left; i < end; i++)
                    {
                        if ((!descend && array[left] > array[pivot]) || (descend && array[left] < array[pivot]))
                        {
                            break;
                        }
                        left++;
                    }
                    for (int j = right; j >= begin; j--)
                    {
                        if ((!descend && array[right] < array[pivot]) || (descend && array[right] > array[pivot]))
                        {
                            break;
                        }
                        right--;
                    }
                    if (left > right)
                    {
                        break;
                    }
                    swapArray(array, left, right);
                }
                swapArray(array, pivot, left);
                recursion_QuickSort(array, begin, left - 1, descend);
                recursion_QuickSort(array, left + 1, end, descend);
            }
        }