C#之快速排序

演算法描述

1.假定數組首位元素為“樞軸”，設定數列首位（begin）與末位（end）索引；

2.由末位索引對應元素與“樞軸”進行比較，如果末位索引對應元素大於“樞軸”元素，對末位索引減一（end--），直到比較出大於“樞軸”元素，將該元素覆蓋到首位，對應索引上的數值空出；

3.由首位索引對應元素與“樞軸”進行比較，如果首位索引對應元素小於“樞軸”元素，對首位索引加一（begin++）;直到比較出小於“樞軸”元素，將該元素覆蓋到步驟2中空出位置，同時對應索引上的數值空出；

4.重覆步驟2與步驟3，直到begin==end結束迴圈，這時候begin與end已指向同一位置，將“樞軸”元素覆蓋到該位置；

5.這時候該位置前面元素都小於“樞軸”元素，該位置後面元素都大於“樞軸”元素，第一輪迴圈結束，對前後兩部分執行相同步驟，通過“遞歸”最終將數組中數值完成排序；

代碼實現

        public int[] Quick(int[] arr, int begin, int end) // 通過自我調用實現“遞歸”
        {
            if (begin >= end)
            {
                return arr;
            }

            int pivotIndex = QuickCondition(arr, begin, end); // 獲得“樞軸”索引

            Quick(arr, begin, pivotIndex - 1); // 對所有小於“樞軸”元素再次比較
            Quick(arr, pivotIndex + 1, end);// 對所有大於“樞軸”元素再次比較

            return arr;
        }

        public int QuickCondition(int[] arr, int begin, int end)
        {
            int pivot = arr[begin]; // 設定首位為“樞軸”元素

            while (begin < end)
            {
                while (arr[end] > pivot && begin < end) // 通過比較找到小於“樞軸”元素的索引，進行替換
                {
                    end--;
                }

                arr[begin] = arr[end];

                while (arr[begin] < pivot && begin < end) // 通過比較找到第大於“樞軸”元素的索引，進行替換
                {
                    begin++;
                }

                arr[end] = arr[begin];
            }
            arr[begin] = pivot; // 當begin == end 跳出迴圈將“樞軸”覆蓋到該索引上

            return begin;
        }

完整代碼

using System;

namespace QuickSortApplication
{
    class Program
    {
        static void Main(string[] args)
        {
            var setArray = new SetArray();
            var quickSort = new QuickSort();

            int[] arr = setArray.GetArray();
            int[] array = quickSort.Quick(arr, 0, arr.Length - 1);
            quickSort.DisPlay(array);
            
            Console.ReadLine();
        }
    }

    class SetArray
    {
        public int[] GetArray()
        {
            int length;
            int[] arr;

            Console.WriteLine("請輸入數組長度：");
            length = Convert.ToInt32(Console.ReadLine());

            arr = new int[length];

            for (int i = 0; i <= length - 1; i++)
            {
                Console.Write("請輸入數組第{0}位數值：", i);
                arr[i] = Convert.ToInt32(Console.ReadLine());
            }

            Console.Clear();

            Console.Write("arr[] = {");
            foreach (int item in arr)
            {
                Console.Write(item + " ");
            }
            Console.Write("}\n");
            return arr;
        }
    }

    class QuickSort
    {
        public int[] Quick(int[] arr, int begin, int end) // 通過自我調用實現“遞歸”
        {
            if (begin >= end)
            {
                return arr;
            }

            int pivotIndex = QuickCondition(arr, begin, end); // 獲得“樞軸”索引

            Quick(arr, begin, pivotIndex - 1); // 對所有小於“樞軸”元素再次比較
            Quick(arr, pivotIndex + 1, end);// 對所有大於“樞軸”元素再次比較

            return arr;
        }

        public int QuickCondition(int[] arr, int begin, int end)
        {
            int pivot = arr[begin]; // 設定首位為“樞軸”元素

            while (begin < end)
            {
                while (arr[end] > pivot && begin < end) // 通過比較找到小於“樞軸”元素的索引，進行替換
                {
                    end--;
                }

                arr[begin] = arr[end];

                while (arr[begin] < pivot && begin < end) // 通過比較找到第大於“樞軸”元素的索引，進行替換
                {
                    begin++;
                }

                arr[end] = arr[begin];
            }
            arr[begin] = pivot; // 當begin == end 跳出迴圈將“樞軸”覆蓋到該索引上

            return begin;
        }

        public void DisPlay(int[] arr)
        {
            Console.Write("快速排序：");
            foreach (int item in arr)
            {
                Console.Write(item + " ");
            }
            Console.WriteLine();
        }
    }
}