有意思的快速排序法（VBA版本）！

vlambda
2020-01-01

有意思的快速排序法（VBA版本）！

我的目标：让中国的大学生走出校门的那一刻就已经具备这些office技能，让职场人士能高效使用office为其服务。支持我，也为自己加油！

前面三节分享了冒泡排序法，冒泡排序法是基于数据大小按顺序两两比较大小进行排序，当数据量大的时候，此方法就需要进行很多次循环与比较，运行速度相对较慢。

我们学习这些方法的目的主要是领会其思路，以便在处理实际问题时思路能够更加的宽广和灵活。

今天分享下快速排序法。

快速排序（Quicksort）：

其实是对冒泡排序的一种改进。由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

快速排序法的基本流程是：

1、首先在数组中随便找一个值作为基准值，可以是数组最左边的值，最右边的值，中间的值或者是随机位置的值。

2、从序列的两边进行探测，大于基准值的元素全部放到基准值的右边，小于基准值的元素全部放在基准值左边，这样该数组就根据基准值分为了两部分，左边部分全部小于基准值，右边部分全部大于基准值。

3、被基准值分开的两部分序列分别按照1，2中的步骤处理。（递归过程）

快速排序法运用的是“分治”策略，根据基准值通过交换把整个数组不断的分成短的序列进行排序。

下面是原理图：

这样讲大家有可能还是比较迷糊，下面的实例可以形象的说明快速排序的过程。

有一组数据：

9，2，5，8，3，6，7，1，4，10

要对这组数据进行排序。

图解如下（黄色块代表基准值）：

大家可以把后面的文字和图片对照起来理解。

我把序列中间位置的值作为基准值，所以选定6作为基准值，然后派出两个哨兵 i 和哨兵 j 从数组的两端向中间位置进行巡查，i 负责找基准值左边序列中大于基准值的值，j负责寻找基准值右边序列中小于基准值的值，所以 i 找到了9，j 找到了4，两个位置的值进行交换。

然后继续巡查，i 又找到一个大于基准值的值8，j 也找到一个小于基准值的值1，两个位置的值进行交换。

接着继续巡查，直到 i 和 j 在基准值的位置碰头了，这时候就没必要继续巡查了，因为此时已经保证基准值右边的值全部大于基准值，基准值左边的值全部小于基准值了。

然后以基准值为分界线，把数组分为两部分，左边一部分，右边一部分。

然后对左右两部分序列分别重复上面的过程，直到排序完成。

VBA代码如下：

Option ExplicitPublic m&
Sub 排序()Dim arr() As Long, n%, min&, max&ReDim arr(1 To 10)For n = 1 To 10 arr(n) = Cells(1, n).ValueNextmin = LBound(arr)max = UBound(arr)Quicksort arr(), min, max
'导出结果最终结果，验证正确与否Cells(m + 1, 1).Resize(1, 10) = arrEnd SubSub Quicksort(arr() As Long, min As Long, max As Long)Dim i&, j&, ref&, temp&
'在需要查询的序列起始端和终点端各设置一个哨兵，i,ji = minj = max
'取中间位置的值为基准值ref = arr((min + max) / 2)
'两边哨兵出动开始巡查,相遇后停止巡查Do '先出动右边的哨兵,寻找小于等于基准值ref的元素 Do While arr(j) > ref j = j - 1 Loop '再出动左边的哨兵,寻找大于等于基准值ref的元素 Do While arr(i) < ref i = i + 1 Loop '找到目标值或者相遇后交换其所在位置的值 If i <= j Then temp = arr(i) arr(i) = arr(j) arr(j) = temp
 '导出以观察结果 m = m + 1 Cells(m + 1, 1).Resize(1, 10) = arr
 '继续巡查 i = i + 1 j = j - 1 End If
Loop Until i > j
'第一轮巡查完毕，基准值归位，对基准值左右两边的序列分别进行上面的过程，直到排序完毕If min < j Then Quicksort arr, min, jIf i < max Then Quicksort arr, i, max
End Sub

因为涉及到递归过程，所以我写了两段代码，而且为了方便观察理解，我把每次交换后的数组输出到了工作表中，实际应用时可以删除掉输出语句（14、15、46、47行）

大家可以在代码中设置断点，一行一行输出，通过本地窗口观察基准值ref，i，j的值，理解递归时处理的是哪部分序列，这样更容易理解快速排序法的原理。

本节的分享就到这里，祝大家每天都有进步。

成为米宏office学堂终身会员有啥好处：

1、米宏云课堂的视频永久免费观看

2、日后录制的视频可以免费观看

3、视频中不懂的可以提问

5、可以帮助解决视频中未提到，文章中未写到的典型问题

期待真心想提高office水平的朋友，非诚勿扰！

点击“阅读原文”，发现惊喜哦！

vlambda博客
学习文章列表