7.骚年，这就是你的***速度吗？介绍完前面的排序算法，这次要写的是快速排序。快速排序之所以称为快速排序，是因为它非常快。是目前已知实践中最快的排序算法（不过我看过一个叫Google的位图排序算法，据说可以更快，但是之后一直没找到相关资料，所以还是不要相信上面的消息为好thetabloids），它的平均运行时间可以达到O(NLOGN)，并且在大多数情况下很容易达到这个时间界限。快速排序算法的过程分为以下几个步骤：1.如果序列中只有0个或1个元素，则算法结束。2、在待排序序列中任意选择一个数，记录为p。3.保存剩下的将下面的元素分成两个子序列，一个子序列中的所有数都小于p，另一个子序列中的所有数都大于p，4.对上面的过程进行上述处理两个子序列。看完这四个步骤，相信很多人又开始退缩了。里面有递归。其实大可不必害怕。仔细分析一下，快速排序和归并排序很相似。可见这是思想的延伸。不同的是，归并排序在递归（排序）之前不对序列进行任何处理，而快速排序则需要进行一些排序预处理，得到两个子序列，然后对这两个子序列进行排序。这里要提的一件事是如何选择对这个算法的效率有影响的p值。这也是快速排序的一个很微妙的地方。基本思路说完了，约定俗成贴一段代码。voidquickSort(intnumbers[],intarray_size){q_sort(numbers,0,array_size-1);}voidq_sort(intnumbers[],intleft,intright){intpivot,l_hold,r_hold;l_hold=left;r_hold=right;pivot=numbers[左边];while(left=pivot)&&(leftpivot)q_sort(numbers,pivot+1,right);}第一个函数可以理解为驱动，是为了隐藏一些实现细节，让调用者在调用的时候传递更少的参数，减少出错的可能性。这也是一种巧妙的设计方法。第二个函数是真正的快速排序函数。从代码来看，这里选择每个序列的第一个点作为p点，然后从两端和这个p点进行比较，先从右端找***小于p点的值，然后停止，交换左端左边当前扫描的值（即p点的值），两个值，然后从左边开始扫描，找到当前大于p点的值，交换,等等,***当从左端扫描的坐标和从右端扫描的坐标相交时,记下这个点,用这个点交换p点的值,这样就可以保证这个值p点左边的值比p点的值小（但不一定有序），右边的值比p点的值大，以此类推，再对p点进行同样的排序过程依次是两个子序列，因为我在之前的文章中详细分析了递归计算ling过程，这里就不分析了，唉，人还是懒的。先来看看效果吧。分析完结果再来看***行，***行我们选择的p是34，然后从右端开始，81大于34，不用交换，继续扫描，12小于大于34，交换两个值，12交换到第一位，34交换到倒数第二位，现在从左边开始扫描，43大于34，再次开始交换，43交换到倒数第二位，34交换到第二位，和以此类推，得到34为分界点，左边序列的元素都小于34，右边的元素都大于34。下面简单说明一下为什么p点的选择对快速排序的效率，因为第三步是把序列分成两个序列然后递归。想象一下，如果一个倒序的数列，即54321这样，如果按照我们上面的方法选择p点，那么会出现的问题是，它被分成了两个子序列，一个子序列包含了所有的数原始序列，而一个子序列不包含任何数字，这将导致效率大大提高降低。那么如果p点是随机选择的呢？这样会减少我上面提到的问题，但是带来的负面影响是随机数的生成也需要很多时间，所以这也是一种得不偿失的方法。那么有没有更好的办法呢？有一种通用的方法称为三中值分割法。如果快速排序的效率越高越好，那么我们选择的p值就应该尽可能的取中值。这样，分成两个序列的两个序列就比较平均了。事实上，对于一个排列为的序列，选择中间位置的元素。在实践中，由于大多数应用程序的后台，这种方法往往可以神奇地提高效率。原文链接：http://www.cnblogs.com/ZXYloveFR/archive/2012/09/27/2705463.html【编者推荐】Java数据结构：栈的实现浅谈C++中数据结构与算法的分离从淘宝开发看电商中商品属性的数据结构设计如何使用Perl关联数组创建数据结构详细介绍C++中的虚函数和动态链接
