快速排序是对冒泡排序的一种改进。它的基本思想是：通过一躺排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据段变成有序序列。
过程: 每趟调用都要选择一个基准元素,将待处理段按这个基准数据进行划分,即左边的元素都小于等于基准元素,而右边都大于等与基准元素. 针对下面的算法,注意扫描过程是右->左->右->左....这样交替进行的, 算法首先把基准元素保存到temp中,这样数组就空出一个位置了(i 指向的位置) ,接着从右边开始扫描寻找比temp小的元素,找到后将元素覆盖到 i 指向的位置(i 中的元素已经放到temp中了),接着换左边开始扫描(i中元素是有效数据,这时j 指向的空间是交换空间),左边扫描时逐1增加i的数值,直到找到一个Array[i]>temp,将array[i]保存到arra[j]中,j 指向的空间是交换空间,接着再换右边开始扫描,如果到i=j都没找到符合条件的元素就表示i(i=j)位置就是temp元素应该存放的位置了,上面过程可以看到i或j其中必然有一个指向交换空间(元素已经被移动,里面的内容没有意义了,在C#的引用类型中这个就是一个指针数据)而当i=j时可以放心的执行array[i]=temp 或array[j]=temp 操作,将基准元素放会到数组排序后对应的位置.
关键点: 选择基准元素是随机的(一般是第一个)因此这个元素的位置是不确定的,(不要老以为它应该放到数组的中间位置),而上面的操作实质上都是围绕给基准元素找到一个合适位置进行的,执行上面描述的过程后, 只要基准元素找到位置则可. 比方数组的第一个元素是23,而23是数组的最小元素,那么根据上面过程执行后会发现最后i=j=0, 那么array[i]=temp 将把23放回array[0]位置.这样继续递归时左边的递归调用直接返回,而右边则是少一个元素的QuickSort.
说明: 快速排序是不稳定排序,即两个等价元素其先后(左右)位置与排序前不统一,比方 x1,.....x2 ,排序后有可能是 ...x2,x1...,这样的形式. C#代码实现
-----------------------------------------
public class QuickSort { public static void Sort(T[] array, IComparer comparer) { Sort(array, 0, array.Length - 1, comparer); } ///
/// 注意这里注意扫描过程的处理 /// 元素移动后,那么它原来的位置就用来当临时空间来使用了 /// 而i或j其中一个始终指向这个临时空间,当i=j时,表示扫描结束 /// 最后array[i]=temp,将选择的中间元素放回到数组里(排序后对应的位置) /// /// /// /// /// private static void Sort(T[] array, int L, int h, IComparer comparer) { T temp; int i, j; if (L < h)//至少有2个元素 { //选择第一个元素为基准元素,从右开始扫描 temp = array[L]; i = L; j = h; while (i < j) { //选择 array[j] < temp的元素,将其移动到前面 i 指向的位置 //而移动后的空间可空出来做下次交换使用,这时j为这个空间的下标 while (i < j && comparer.Compare(temp, array[j]) <= 0) j--; //i if (i < j) array[i] = array[j]; //从左边开始扫描大于temp的元素 while (i < j && comparer.Compare( array[i],temp) <= 0) i++; //i< j表示找到一个大与 if (i < j) array[j] = array[i]; } //这里有i=j;temp元素找到自己的位置了, //左变的都比temp小,右边的都比temp大(或者等于) array[i] = temp;Sort(array, L, i - 1, comparer);//完成左边 Sort(array, i + 1, h, comparer);//完成右边
} } }
------------------------------
另外在.net2.0中的很多集合类其中的Sort方法使用的都是快速度排序实现的,因此进行集合排序时不需要自己专门实现这么个排序方法. 从Reflector摘录的部分代码
---------------------------------
private void QuickSort (T[] keys, TValue[] values, int left, int right, IComparer comparer) { do { int a = left; int b = right; int num3 = a + ((b - a) >> 1); //中间值下标,等价于 a+ (b-a)/2 this.SwapIfGreaterWithItems (keys, values, comparer, a, num3); this.SwapIfGreaterWithItems (keys, values, comparer, a, b); this.SwapIfGreaterWithItems (keys, values, comparer, num3, b); T y = keys[num3]; ............................. 这里在排序前先进行"三者取中",即比较这3个元素的大小取中间值做为基准,另外上面类的扫描过程不是交替进行的,而是两边同时扫描(可能找到2个后互换),具体参考Reflector后的代码,下面给出链接中的算法分析有"三者取中"的说明. 参考 快速排序算法原理与实现 算法分析(网站名称: 数据结构)
