最近一直在看《算法导论》，看完麻省理工的视频，才敢动手敲敲代码。对于一些经典算法感觉看了就会忘 ，只有自己体会了消化了才会成为自己的东西，在这里就相当于写写笔记加深印象。快速排序是一种基于分治技术的排序算法，思想核心是选择一个基准元素X将待排序元素分成两个子序列，使得一个子序列中的元素均小于等于X,而另一个子序列中的元素均大于X,处于其终端所处在的位置上。
或者你也可以打个比喻，想象一下，假设r为主元素，J元素为前方开路元素,和主元素进行比较，如果大于主元素则继续开路 ，如果小于主元素则I元素加1之后和J元素交换之后，J元素继续开路直到最后。
书中给出了划分的伪代码：
1 PARTITION(A,p,r) 2 x = A[r] //将最后一个元素作为主元素 3 i = p-1 4 for j=p to r-1 //从第一个元素开始到倒数第二个元素结束，比较确定主元的位置 5 do if A[j] <= x 6 i = i+1 7 exchange A[i] <-> A[j] 8 exchange A[i+1]<->A[r] //最终确定主元的位置 9 return i+1 //返回主元的位置
通过递归，书中又给出了快速排序的伪代码：
1 QUICKSORT(A,p,r) 2 if p<r 3 q = PARTITION(A,p,r) //确定划分位置 4 QUICKSORT(A,p,q-1) //子数组A[p...q-1] 5 QUICKSORT(Q,q+1,r) //子数组A[q+1...r]
采用C#语言来段代码：
static void Main(string[] args) { int[] ArrInput = new int[] { 78, 13, 9, 23, 45, 14, 35, 65, 56, 79 }; QuickSort(ArrInput, 0, ArrInput.Length - 1); for (int i = 0; i < ArrInput.Length; i++) { Console.WriteLine(ArrInput[i]); } Console.Read(); } /// <summary> /// 快速排序算法 /// </summary> /// <param name="arr"></param> /// <param name="p"></param> /// <param name="q"></param> /// <returns></returns> static int Partition(int[] arr, int p, int q) { #region //根据算法导论上的来的 int x = arr[q]; int i = p - 1; for (int j = p; j <= q - 1; j++) { if (arr[j] <= x) { i=i+1; Swap(arr, i,j); } } Swap(arr, i+1,q); return (i + 1); #endregion } /// <summary> /// 递归实现左右两部分 /// </summary> /// <param name="arr"></param> /// <param name="p"></param> /// <param name="r"></param> static void QuickSort(int[] arr, int p, int r) { if (p < r) { int q = Partition(arr, p, r); QuickSort(arr, p, q - 1); QuickSort(arr, q + 1, r); } } /// <summary> /// 交换数据 /// </summary> /// <param name="a"></param> /// <param name="b"></param> static void Swap(int []a, int n1,int n2) { var temp = a[n1]; a[n1]= a[n2]; a[n2] = temp; }
经过分析，快速排序算法在平均情况下的时间复杂度为T(N)=O(nlogn)，如果序列本身已经是排好序了此时快速排序处于最坏的情况。可以通过修改操作Partition,采用随机选择策略来选择基准元素 。至于随机化快速排序大家可以参考其他的资料。
热爱C++编程，自认为通过努力改变人生，喜欢研究新奇技术。 转载请注明出处。 作者：曹麒文 博客地址：http://www.cnblogs.com/master-image/