找回密码
 立即注册
  • QQ空间
  • 回复
  • 收藏

算法与人生(二)

admin 2019-4-11 06:21 131人围观 C++相关

昨天阴雨连绵,今日艳阳高照。早上骑单车的的时候没注意,有只麻雀”伫立“在路中间,在我匆忙避让的时候这小家伙却也不着急飞走,踱步前行,感叹现在它们竟也可能意识到自己在人类世界的地位,只是我们是规矩了自己罢了。



闲话扯多了,我们回归正题吧。今天我想与大家分享的是排序界的”扛把子“——快速排序(复杂度nlogn)。为什么是扛把子呢?在于它背后的思想——“分而治之”。什么是分而治之?简单说来,就是并行的概念。像我们所知的多线程,就是同时能运行好几个任务,带来的利益就是速度快。

我们可以通过最基础的分两部分来实现快速排序。你们说为啥不分三部分,四部分甚至更多呢?在我看来,有以下的原因:1. 首先对于一个数组(列表)来说,主要是包含头尾,进出这一说,你要是分三部分或更多部分比较困难选择一个合适的位置。2. 老子的思想“大道至简”和奥卡姆剃刀定律没准也能在这派上用场呢是吧。

我们定好了头尾两个方向,接着该找一个基准用于比较大小。一般来说,基准从数组的第一个元素开始(其他元素也行,跟着你的习惯走都ok的)。在此,我举一个例子更形象化的说明这个过程。对于原始列表lst = [20,40,50,10,60],我们设定基准是首元素20,定义指针(在python里可用变量代替)left指向lst[0],right指向lst[5],如下:



(红色加粗数字代表当前的基准数字)

从尾——>首的方向开始第一次比较基准和right指针指向的数,如果right指针的数比基准大,right指针往左移,直到找到比基准小的数,停止,赋值给left。过程如下:



(没有红色加粗数字出现代表基准不变)

接着从首——>尾的方向开始第二次比较基准和left指针指向的数,如果left指针的数比基准小,left指针往右移,直到找到比基准大的数,停止,赋值给right。过程如下:



重复上述的过程,直到left指针和right指针重合,将基准数字插入到重合的位置:



接着,就是递归对左右两个子序列进行排序,重复上述的步骤。由于这个例子左子序只有一个元素,不需要再排序,所以我们对右子序重复上述的步骤:



至此,排序完成。

附上代码一,第一次交换至第三次交换的过程:

    def Partition(lst, left, right):    baseline = lst[left]whileleft < right:whileleft < right and lst[right] >= baseline:right -= 1 lst[left] = lst[right]whileleft < right and lst[left] <= baseline:left += 1        lst[right] = lst[left] lst[left] = baselinereturnleft

    代码二,递归的过程:

      def quick_sort(lst, left, right):ifleft < right:       base  = Partition(lst, left, right)       q_sort(lst, left, base - 1)       q_sort(lst, base + 1, right)return lst

      还有一种简便写法如下:

        def quick_sort(lst):if not lst:return [] base = lst[0] left = quick_sort([x for x in lst[1: ] if x < base]) right = quick_sort([x for x in lst[1: ] if x >= base])return left + [base] + right

        不过没有第一种方法对快排的思想具体阐述。

        在我们的生活当中,存在着很多棘手的事。若你选择一步完成,在大部分情况下是比较困难的,可能需要你花费大量的力气,我们将大问题分解为一个个小问题,分头解决,不仅能完成应定的任务,而且能在较短的时间内完成,何乐而不为呢?

        同样,面对联合强敌的时候,我们能拆散他们的联盟,分而治之,也比独木成林的对手要好得多。反之同理,抱团取暖总比单兵作战要强很多。



        So,大家请多多关注我的个人公众号,也许未来的某一天,我们有对抗世界的能力呢?

        鲜花

        握手

        雷人

        路过

        鸡蛋

        yafeilinux和他的朋友们微信公众号二维码

        微信公众号

        专注于Qt嵌入式Linux开发等。扫一扫立即关注。

        Qt开源社区官方QQ群二维码

        QQ交流群

        欢迎加入QQ群大家庭,一起讨论学习!

        我有话说......

        
        关于进行手机实名认证的紧急通知!
        按照有关部门要求,论坛类网站必须完成手机实名认证才可以进行发帖等操作。希望大家积极配合,为创建一个和谐文明的社区而贡献自己的力量。我们会对会员的隐私进行严格保密,对大家造成的不便深表歉意! 我知道了