一、奇怪的现象
研究快速排序很久了,发现一个古怪的实情:这算法描述起来很简单,写一个正确的出来实在不容易.写一个优秀的快速排序算法更是难上加难.
也难怪该算法提出来过了很久才有人写出一个正确的算法,过了很久才优秀的版本出来.
二、原理描述从数列中挑出一个元素，称为 "基准"（pivot），
重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序.
三、最容易让人理解的版本一个List形式的数组,找到其中的第一个做基准,遍历剩下的数据,然后创建两个左右List,大的放右边,小的放左边.然后对左右List各自进行如上操作.......
详情见代码
using System; using System.Collections.Generic; using System.Text; namespace test { class Program { static void Main(string[]args) { List<int> array=new List<int>(); array.AddRange(new int[]{3,2,9,5,8,6,23,23,222,12,21}); var t1=DateTime.Now.Ticks; sort(array); var t2=DateTime.Now.Ticks; Console.WriteLine(t2-t1); Console.ReadLine(); } static int Count=0; public static void sort(List<int> array) { var guid=Count++; Console.WriteLine(); Console.Write("目标字符串:("+guid+")"); Show(array); if (array.Count<=1) { return; } if (array.Count==2) { if (array[0]>array[1]) { var temp=array[0]; array[0]=array[1]; array[1]=temp; Console.Write("双值交换:"); Show(array); } } else{ var xData=array[0]; var leftList=new List<int>(); var rightList=new List<int>(); for (int i = 1; i < array.Count; i++) { var t=array[i]; if (t<=xData) { leftList.Add(t); }else{ rightList.Add(t); } } Console.WriteLine("中间值:"+xData); Console.Write("左边的字符串("+guid+"):"); Show(leftList); Console.Write("右边的字符串("+guid+"):"); Show(rightList); sort(leftList); Console.Write("左边的字符串(排序后)("+guid+"):"); Show(leftList); sort(rightList); Console.Write("右边的字符串(排序后)("+guid+"):"); Show(rightList); array.Clear(); array.AddRange(leftList); array.Add(xData); array.AddRange(rightList); Console.Write("排好的("+guid+"):"); Show(array); Console.WriteLine(); leftList.Clear(); rightList.Clear(); } } public static void Show(List<int>array){ foreach (var a in array) { Console.Write(a+","); } Console.WriteLine(); } } }