c# 实现快速排序

快速排序的思想是"分而治之"

如果一个数列所有的元素都小于另一个数列的任意元素,那么如果将两个数列排列好,就非常容易合并.

最重要的就是找一个基准(pivot),将数列分裂成比它大的部分,和比它小的部分.

这个pivot数值最好是中间,每次递归,都能化为两个规模类似的问题.

这里采用中值法,第一个,中间位置,最后一个,取中间值.

然后调整序列,使得左边小,右边大,再传出来中间值坐标.

 private static int FindMiddle(int[] nums,int left,int right)
        {
            int middleIndex = (left + right) / 2;
            if (nums[left] > nums[middleIndex])
            {
                Swap(nums, left, middleIndex);
            }
            if (nums[middleIndex] > nums[right])
            {
                Swap(nums, middleIndex, right);
            }
            if (nums[left] > nums[middleIndex])
            {
                Swap(nums, middleIndex, left);
            }
            Swap(nums, middleIndex, right - 1);
            //将倒数第二个元素放到合适的位置,其中左边都比他小,右边都比它大
            int i = left;int j = right - 1;
            while (true)
            {
                while (nums[++i] < nums[right - 1]) { };
                while (nums[--j] > nums[right - 1]) { };
                if (i < j)
                    Swap(nums, i, j);
                else
                {
                    Swap(nums, i, right - 1);
                    return i;
                }
            }
        }

解决好这一步,就可以用递归解决了,由于递归非常浪费系统资源,当问题规模较小时,使用其他非递归排序法

   private static void QuickSort(int[] nums,int left,int right)
        {
            if((right-left)<3)//递归基,真正使用,设置为100左右
            {
                M_InsertSort(nums, left, right);
            }//用一个插入排序好了
            else
            {
               int middleIndex= FindMiddle(nums, left, right);
                QuickSort(nums, left, middleIndex - 1);
                QuickSort(nums, middleIndex + 1, right);
            }
        }
        private static void M_InsertSort(int[] nums,int left,int right)
        {
            if (left == right) return;
            for(int i = left + 1; i <= right; i++)
            {
                int temp = nums[i];
                int p = i - 1;
                while (p>=left&& nums[p] > temp)
                {
                    nums[p + 1] = nums[p];
                    p--;
                }
                nums[p + 1] = temp;
            }
        }
        
        public static void Quick_Sort(int[] nums)
        {
            QuickSort(nums, 0, nums.Length - 1);
        }