首页 > 代码库 > 排序算法系列——快速排序

排序算法系列——快速排序

记录学习点滴

快速排序算法是一种很有趣的算法,短小精悍,性能强劲,对于大部分情况都可以胜任,但对极端环境难以应付。

快速排序我理解为:这是一个“以自我为中心的”+“分治法”思想的算法。

分治法不必多说,化繁为简,那就是逐个击破。

那什么是“以自我为中心”?顾名思义,就是每次都一个“我”,每个人都要围绕“我”行事,比“我”小的都去左边站着,比“我”他大的都去右边站着,而且“我”不去关心每一边都有谁,反正你没“我”大或者小就行。一旦“我”落位了妥帖了,“我”就不动了。然后再在左右两边分别产生新“我”,重复上述步骤。

那大家又是如何以“我”为中心的呢?有两种方式,一种是单边扫描,一种是两头扫描。

1.单边扫描

即总是选取一个数组的最右边为主元("我"),按照《导论》,设置两个标记,iji标记分界点(左边为小的,右边为大的),j为扫描器(从头到尾遍历数组)如下图所示。i的作用是标记位置,左边为小的,右边为大的;j的作用是发现比4(“我”)小的数,然后和i+1的换位置,最后将“我”放在正确的位置上

     

按照《导论》,代码如下

 1 def Partition_OneSideScan(A,p,r):#单边扫描 2     i = p-1 3     x = A[r-1] 4     for j in range(p,r):  5         if A[j-1] <= x: 6             i = i+1 7             A[i-1],A[j-1] = A[j-1],A[i-1] 8      9     A[r-1],A[i] = A[i],A[r-1]10     return i+1 #返回一个Base点

2.两头扫描

两头扫描,就是两边一起扫描,遇到比“我”大的放到右面,遇到比“我”小的放在左面,具体到代码如何实现?最好的方法是白话经典算法系列之六 快速排序 快速搞定中提到的“坑”,非常形象,很容易理解(大牛就是大牛,By the way,我认为最好的理解方式就是举例子,作比喻)。

在这里画个图来描述其思想。

 代码实现,可以去看大牛写的代码。

 最后,通过递归调用实现快速排序,代码如下:

1 def QuickSort(A,p,r):#快速排序的分治法部分2     if p<r:3         q = Partition_DigHole(A,p,r)4         QuickSort(A,p,q-1)5         QuickSort(A,q+1,r)