首页 > 代码库 > 算法与数据结构(十六) 快速排序(Swift 3.0版)

算法与数据结构(十六) 快速排序(Swift 3.0版)

 上篇博客我们主要聊了比较高效的归并排序算法,本篇博客我们就来介绍另一种高效的排序算法:快速排序。快速排序的思想与归并排序类似,都是采用分而治之的方式进行排序的。快速排序的思想主要是取出无序序列中第一个值,然后通过比较将比该值小的元素放到该值的前方,将比该值大的元素放在该值的后方。这样一来该值前方的数据都要比该值小,该值后方的数据都要比该值大。然后再次对前半部分和后边半部分无序的数列进行上述操作,这样不断的操作,无序的序列的规模不断被缩小。等问题的规模被缩小到一定程度后,我们的序列就变的有序了。

之前我们说过,当一个问题可以被分成一些相同的子问题时,我们就可以使用递归来操作。所以在快速排序的过程中,我们是通过递归的方式将问题规模逐渐减小,知道序列为序为止。本篇博客将会给出这一过程,根据示意图,给出相应的代码实现。

 

一、将无序数组进行拆分

在本篇博客,我们先聊一聊如果将大的问题拆分成一些相同的子问题。我们需要对需要排序的数组进行拆分,从无序序列中取出一个值,然后通过比较,将比该值大的放在该值的后方,比该值小的,放在该值的前方。本部分,我们将给出相应的示意图以及代码实现。

 

1.拆分示意图

下方就是我们上述过程的示意图。也是快速排序第一轮排序的过程。首先将无序数组中的第一个值进行暂存(temp = 62),经过下述步骤,我们会将那些比62小的元素放到62的前面,比62大的元素放到后边。low负责遍历前半部分,将前半部分大于62的值放到后边而high负责遍历后半部分,将后半部分小于62的值放前边。具体步骤如下所示。

  技术分享

2.代码实现

根据上述示意图,我们可以给出相应的代码实现。如果上述的示意图理解了,看下方代码的实现是比较简单的。partition()函数就负责将一个无序的数组转变的以第一个值为准,较小的值放在该值的前边,较大的放在该值的后边。如下所示。

  技术分享

 

二、快速排序

实现完拆分方法后,我们就该实现快速排序的代码了。上面的代码是快排的核心,接下来做的事情是调用上述的函数将无序数组进行拆分,然后再调用上述函数将前后无序的小数组进行拆分,依次执行下去,我们的数组就是有序的了。其实就是一个递归的过程。下方的quickSort()就是这个过程。首先将无需数组调用partition()方法进行拆分,然后再次调用quickSort()方法执行前半部分,同样的调用quickSort()方法执行后半部分。代码如下所示。

  技术分享

 

定义完快速排序的核心方法后,接下来就是使用了。下方的QuickSort就是相应的快速排序类,QuickSort还是要遵循SortType这个排序协议的,而sort()方法则是该协议中定义的对外调用的接口。具体代码如下所示。

  技术分享

 

三、测试用例

用我QuickSort类遵循了SortType方法,我们依然可以使用之前的测试用例。下方就是我们的测试用例,与之前使用的一直,只不过需要将QuickSort这个类的对象传给我们的测试函数即可,如下所示:

  技术分享

本篇博客快速排序的运行结果如下:

  技术分享

 


本篇博客对堆排序的介绍就先到这儿,下篇博客我们将会介绍“基数排序”的详细内容。本篇博客的相关代码依然会在github上进行分享,下方是github分享地址,如下所示:

github代码分享地址:https://github.com/lizelu/DataStruct-Swift/tree/master/AllKindsOfSort 

算法与数据结构(十六) 快速排序(Swift 3.0版)