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趟排序之后，会出现这样的现象，分段到最后就是分两个数的大小顺序，即此时该段数据自动有序。排序函数运行结束之后，所有数据自动有序。
