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();
        }
    }
}