using System;
using System.Collections.Generic;

namespace quick_sort
{
    public static class Sort
    {//升序排列
        public static void Quick_Sort_low(int[] list, int left, int right)
        {//性能偏弱
            if (left < right)//注意递归退出条件
            {
                int p = list[left];//p是将list[left:right+1]分段的参考值，
                int l = left;//因为在之后的递归中还需要left和right作为入参
                int r = right;//所以不能改变left和right的原始值
                while (l < r)
                {
                    while (l < r && p <= list[r])
                        r--;
                    if (l < r)
                    {//运行到这里，必然有p>left[r]
                        list[r] = list[l] + list[r];
                        list[l] = list[r] - list[l];
                        list[r] = list[r] - list[l];//不使用中间变量进行值交换
                        l++;
                    }//实际上是p的值和left[r]交换,即if语句完成后参考值p=list[r]
                    while (l < r && p >= list[l])
                        l++;
                    if (l < r)
                    {//运行到这里，必然有p<left[l]
                        list[r] = list[l] + list[r];
                        list[l] = list[r] - list[l];
                        list[r] = list[r] - list[l];//不使用中间变量进行值交换
                        r--;
                    }//实际上是p的值和left[l]交换,即if语句完成后参考值p=list[l]
                }
                Quick_Sort_low(list, left, l - 1);
                Quick_Sort_low(list, r + 1, right);
                //此处，l必等于r，且p=list[l]=list[r]
                //同时p>=list[left:l],p<=list[r+1,right],所以p不必再参与之后的排序过程
            }
        }
        public static void Quick_Sort_low_2(int[] list, int left, int right)
        {//性能偏弱
            if (left < right)//注意递归退出条件
            {
                //此段代码隐藏了p=list[left]这个声明，但实质上仍然是这样的
                int l = left;//因为在之后的递归中还需要left和right作为入参
                int r = right;//所以不能改变left和right的原始值
                while (l < r)
                {
                    //此处list[l]必等于p
                    while (l < r && list[l] <= list[r])
                        r--;
                    if (l < r)
                    {
                        list[r] = list[l] + list[r];
                        list[l] = list[r] - list[l];
                        list[r] = list[r] - list[l];//不使用中间变量进行值交换
                        l++;
                    }
                    //此处list[r]必等于p
                    //也许有人想问会不会出现上一条的if语句为假，我的回答是：
                    //可能为假，但为假意味着l==r为真，即应该做的是循环结束，继续递归。
                    while (l < r && list[r] >= list[l])
                        l++;
                    if (l < r)
                    {
                        list[r] = list[l] + list[r];
                        list[l] = list[r] - list[l];
                        list[r] = list[r] - list[l];//不使用中间变量进行值交换
                        r--;
                    }
                    //此处list[l]必等于p
                    //然后进入下一个循环，下一个循环的初始条件与上一个循环结束时的条件恰好相等
                }
                Quick_Sort_low_2(list, left, l - 1);
                Quick_Sort_low_2(list, r + 1, right);
                //此处，l必等于r，且p=list[l]=list[r]
                //同时p>=list[left:l],p<=list[r+1,right],所以p不必再参与之后的排序过程
            }
        }
        public static void Quick_Sort_up(int[] list, int left, int right)
        {//性能优于Quick_Sort_low
            if (left < right)
            {
                int p = list[left];//取最左侧的值作为分段参考
                int l = left;
                int r = right;
                while (l < r)
                {
                    while (l < r && p <= list[r])
                        r--;
                    //从r开始向左找，直到找到一个比p大的数
                    while (l < r && p >= list[l])
                        l++;
                    //从l开始向右找，直到找到一个比p小的数
                    if (l < r)
                    {
                        list[r] = list[l] + list[r];
                        list[l] = list[r] - list[l];
                        list[r] = list[r] - list[l];//不使用中间变量进行值交换
                        //此处是将一个比p小的数和一个比p大的数进行交换
                    }
                }
                //执行到此处，必有l=r
                list[left] = list[l];
                list[r] = p;//想想为什么需要这两句代码,为什么没有p与list[l]的大小问题？
                //因为分段是以p作为参考进行分段的，而不是以list[l]作为的参考，所以list[l]不应该在这里
                //因为无论如何循环，最后都会回归到
                //当l+1=r时的list[l]与list[r]的大小与p的比较问题
                //一：若p>list[l],p<list[r],则r=r-1，r会等于l，此时list[l]必小于p
                //二：若p<list[l],p>list[r],则会将list[l]和list[r]的值交换，并跳到一
                //三：若p>list[l],p>list[r],条件不可能成立
                //四：若p<list[l],p<list[r],条件也不可能成立

                Quick_Sort_up(list, left, l - 1);
                Quick_Sort_up(list, r + 1, right);
            }
        }
    }
    class Program
    {
        static void Main(string[] args)
        {
            Random m = new Random();
            List<int> list = new List<int>();
            for (int i = 0; i < 20000000; i++)
            {
                list.Add(m.Next(10000));
            }
            Console.WriteLine("\n");
            DateTime test_time = DateTime.Now;//
            {
                int[] new_array = list.ToArray();//转为数组
                //因为链表是逻辑连续，数组是存储结构连续，所以数组适合排序
                DateTime b_time = DateTime.Now;
                Sort.Quick_Sort_low(new_array, 0, new_array.Length - 1);
                DateTime a_time = DateTime.Now;
                TimeSpan time = a_time.Subtract(b_time);
                Console.WriteLine(time);
            }
            {
                int[] new_array = list.ToArray();//转为数组
                //因为链表是逻辑连续，数组是存储结构连续，所以数组适合排序
                DateTime b_time = DateTime.Now;
                Sort.Quick_Sort_low_2(new_array, 0, new_array.Length - 1);
                DateTime a_time = DateTime.Now;
                TimeSpan time = a_time.Subtract(b_time);
                Console.WriteLine(time);
            }
            {
                int[] new_array = list.ToArray();//转为数组
                //因为链表是逻辑连续，数组是存储结构连续，所以数组适合排序
                DateTime b_time = DateTime.Now;
                Sort.Quick_Sort_up(new_array, 0, new_array.Length - 1);
                DateTime a_time = DateTime.Now;
                TimeSpan time = a_time.Subtract(b_time);
                Console.WriteLine(time);
            }
        }
    }
}

以2000万个0～9999的随机数进行测试：

00:00:53.3620840
00:00:59.9160950
00:00:50.0931710

Press any key to continue...

    快速排序，什么是快速排序？
    百度百科定义：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
    下面用通俗易懂的语言来描述快速排序的实现过程。根据定义，在每一趟排序要将所排序的内容分割成两个部分，且必须满足某一部分的所有数据都得不小于另一部分的所有数据(为什么与定义不符？因为完全可能存在要排序的数据是完全相等的)。所以可以这样更改定义，在每一趟排序结束后，左侧部分数据都不得大于右侧任一数据。
    根据前面的分析，每一趟排序结束后，左侧部分数据都不得大于右侧任一数据，并不会再每趟排序时使所排数据有序。而是以左段数据和右段数据有一个逻辑上的大小关系，这样，通过n趟排序之后，会出现这样的现象，分段到最后就是分两个数的大小顺序，即此时该段数据自动有序。排序函数运行结束之后，所有数据自动有序。