VB-快速排序

飞熊 • 2023年5月24日上午10:55 • 后端开发 • 阅读 208

快速排序（QuickSort）

快速排序 是分而治之的算法。（分成几部分一点点来处理）在排序过程中会选择 一个元素 作为支点或者称为轴，将数组元素一个个与之比较，分成小于轴和大于轴的两个新的数组。所以从另一种理解来看快速排序的关键过程是一个分区的过程。在分区的过程中由于选取 轴元素 不同的方式也使得快速排序也产生了许多不同的版本。但最终的实践效果区别并不大。

时间复杂度：

从平均情况来看快速排序的平均时间复杂度为O(nlogn),若数组恰巧为倒序每次选轴时都为最大或者最小时有最坏情况，时间复杂度为O(n^2)

###排序的稳定性：
由于在快速排序过程中，各数组元素与选定的轴进行对比交换位置，所以使得快速排序是一种不稳定的排序过程。

###从VB来看-插入排序

因为快速排序使用了分而治之的处理思想，所以在VB代码的设计中使用了递归的方式来满足我们一次次分割的需要。

Sub QuickSort(MyArray(), L, R)              '获取数组，并取得下、上界值到L、R
Dim I, J, X, Y

    I = L                                   '确定从数组左边与轴比较的元素位置I
    J = R                                   '确定从数组右边与轴比较的元素位置J
    X = MyArray((L + R) / 2)                '将X选取为数组的轴
        
    While (I <= J)                          '当左右查询位置没有相交时执行
        
        While (MyArray(I) < X And I < R)    '在左边找出大于 X 的值
            I = I + 1
        Wend
        
        While (X < MyArray(J) And J > L)    '在右边找出小于 X 的值
            J = J - 1
        Wend
        
        If (I <= J) Then                    '当查询的位置没有相交时执行
            
            Y = MyArray(I)                  '将小于轴的元素放在左边，大于轴的换到右边
            MyArray(I) = MyArray(J)         
            MyArray(J) = Y
            
            I = I + 1                       '移动从左边开始的查询位置
            J = J - 1                       '移动从右边开始的查询位置
        End If
        
        gIterations = gIterations + 1       '记录一次循环
    Wend
    '递归过程
    If (L < J) Then Call QuickSort(MyArray(), L, J)            '分析轴左边的数组
    If (I < R) Then Call QuickSort(MyArray(), I, R)            '分析轴右边的数组

End Sub

目前没有找到好的抽象的动图举例，如果有好的例子，我会补上哒。
感谢您的阅读~

文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/144349.html