专栏首页take time, save time你所能用到的数据结构(五)

你所能用到的数据结构(五)

七、骚年,这就是你的终极速度了吗?

在介绍了前面的几个排序算法之后,这一次我准备写写快速排序,快速排序之所以叫快速排序是因为它很快,它是已知实践中最快的排序算法(不过曾经我看过一个叫google的位图排序算法,传说能更快,但从那以后我再也没有找到过相关的资料了,所以说江湖小报上的消息还是不要信的比较好),它的平均运行时间能达到O(NLOGN),而且在绝大部分情况下很容易达到这个时间界。

     快速排序算法过程分为如下几步:

     1.如果数列中的元素只有0个或者1个,那么算法结束,

     2.在待排序数列中任意选取一个数,记为p好了,

     3.将剩下的元素划分成两个子序列,一个子序列里面的数全部比p小,另一个全部比p大,

     4.分别对两个子序列进行上述过程的排序。

     看完这四步,我相信很多人又要开始退缩了,这里面又有递归,其实不用怕,仔细分析一下先,快速排序和归并排序挺像的,可以看出来这是一个思想的延伸,不同的是归并排序在递归(排序)之前并不对数列进行任何处理,而快速排序是要进行一些排序的预处理,得到两个子序列,然后再将这两个子序列进行排序。在这里面要特别提到的一个就是如何选取p值对于这个算法的效率是有影响的,这也是快速排序很微妙的一个事情,基本思想说完了,惯例是贴个代码了。

 1 void quickSort(int numbers[], int array_size)
 2 {
 3   q_sort(numbers, 0, array_size - 1);
 4 }
 5 
 6 
 7 
 8 void q_sort(int numbers[], int left, int right)
 9 {
10   int pivot, l_hold, r_hold;
11 
12   l_hold = left;
13   r_hold = right;
14   pivot = numbers[left];
15   while (left < right)
16   {
17     while ((numbers[right] >= pivot) && (left < right))
18       right--;
19     if (left != right)
20     {
21       numbers[left] = numbers[right];
22       left++;
23     }
24     while ((numbers[left] <= pivot) && (left < right))
25       left++;
26     if (left != right)
27     {
28       numbers[right] = numbers[left];
29       right--;
30     }
31   }
32   numbers[left] = pivot;
33   pivot = left;
34   left = l_hold;
35   right = r_hold;
36   if (left < pivot)
37     q_sort(numbers, left, pivot-1);
38   if (right > pivot)
39     q_sort(numbers, pivot+1, right);
40 }

     第一个函数你可以理解为一个驱动程序,为的是隐藏一些实现细节,让调用者调用时传递更少的参数,减小出错的可能性,这也是一种有技巧的设计方法。第二个函数是真正的快速排序函数,从代码上看,这里选取每个序列的第一个点作为p点,然后分别从两端开始和这个p点进行比较,先从右端一直找到第一个小于p点的值,然后停住,交换左端左边现在扫描到的值(也就是p点的值),两个值,然后换从左边开始扫描,找到目前比p点大值,交换,如此继续,最后当从左端扫描的坐标和右端扫描的坐标相遇时,记下这个点,将p点和这个点的值交换,这样就可以保证p点左边的值都是比p点的值小(但是不一定是有序的),右边的值都比p点的值要大,如此循环,然后依次对两个子序列进行一样的排序过程,因为在上一篇里我已经详细的分析了递归的调用过程,所以在这里我就不再分析了,唉,人还是懒的。

     先看下效果好了。

     分析下结果好了,就看第一行,第一行里面我们选取的p是34,那么从右端开始,81大于34,不用交换,继续扫描,12小于34,交换两个值,12交换到第一位,34交换到倒数第二位,现在换从左边扫描,43大于34,又开始交换,43变到倒数第二位,34交换到第二位,如此往复,得到以34为分界点的,左边的序列的元素全部比34小,右边的元素全部比34大。

     下面来简单说明一下为什么p点的选取对于快速排序的效率有一定的影响,因为看到第三步,是要将序列划分成为两个序列然后进行递归,试想如果一个逆序的数列,也就是54321这种,如果按照我们上述的方法选取p点,会出现的问题就是划分成了的两个子序列,一个子序列里面是原数列的所有数,一个子序列里面没有数,这样会导致效率的大大降低。那么如果是随机选取p点呢?这样会减少我上面说的这个问题,但是会带来的负面效应就是随机数的生成也是要耗费大量时间的,所以说这也是一种得不偿失的方法。那么有没有好一点的方法呢?有一种通用的方法叫做三中值分割法,如果让快速排序效率尽量高,那么我们的选取的p值尽量是中值,这样的话分成的两个序列比较平均,其实就是对于一个带排列的数列,选取其中间位置上的那个元素,在实践中,因为大部分应用背景的关系,所以这样的方法往往能神奇的提高效率。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 你所能用到的数据结构(四)

    五、如何递,怎样归? 很多人看完递归的原理之后会有这种感觉,喔,这个原理我懂了,然后再找一道其余的题目看一看能不能写的出来,突然发现,我勒个去,还是不会。其实...

    一心一怿
  • 你所能用到的数据结构(一)

         无损编码的霍夫曼编码以及其余的各种编码由于要使用比较复杂的数据结构,所以按照我昨天说的,我决定从数据结构开始写起。数据结构和算法很难完全的分开,好的数...

    一心一怿
  • 三十天学不会TCP,UDP/IP网络编程 - RST的用法

    不知不觉也写了这么多了,继续我的自己的推广大业~完整版可以去gitbook(https://www.gitbook.com/@rogerzhu/)看到。 如果对...

    一心一怿
  • “快排”笔记

      关于排序,我想没有多少程序员会感觉陌生,信手拈来的可能就有不少:冒泡、选择或者归并等等;可在实际开发中,排序又让许多程序员感到很不熟悉,因为在大多数情况下,...

    用户2615200
  • 算法:快速排序以及第k小元素的线性选择算法

    简要介绍下快速排序的思想:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行...

    s1mba
  • PHP基础之查找

    之前的文章介绍了PHP的运算符、流程控制、函数、排序等。有兴趣可以去看看。 PHP入门之类型与运算符 PHP入门之流程控制 PHP入门之函数 PHP...

    雪痕@
  • ubuntu动态一键切换python版本

    AlicFeng
  • 通过春节参加宴席引发的设计开发App的深层次思考

    版权声明:本文为博主原创文章,未经博主允许不得转载。https://www.jianshu.com/p/5e3c7b4ef37d

    AWeiLoveAndroid
  • 2017年11月互联网和相关服务业保持快速增长

    百通企业咨询服务平台,诚信、专业、高效、贴心,您身边的企业管家 2017年1-11月,互联网和相关服务业规模保持快速增长,营业利润继续快速上升,企业所得税保持稳...

    企鹅号小编
  • 前十一个网络游戏业务收入1341亿 同比增22.1%

    近日,工信部网站透露,1-11月,互联网和相关服务业规模保持快速增长,营业利润继续快速上升,企业所得税保持稳步增长态势,网络游戏、电子商务领域保持活跃。1-11...

    企鹅号小编

扫码关注云+社区

领取腾讯云代金券