第十四章 Caché 算法与数据结构快速排序

定义

同冒泡排序一样，快速排序也属于交换排序，通过元素之间的比较和交换位置来达到排序的目的。
不同的是，冒泡排序在每一轮中只把1个元素冒泡到数列的一端，而快速排序则在每一轮挑选一个基准元素，并让其他比它大的元素移动到数列一边，比它小的元素移动到数列的另一边，从而把数列拆解成两个部分。
这种思路就叫作分治法。

image.png

流程

image.png

如图所示，在分治法的思想下，原数列在每一轮都被拆分成两部分，每一部分在下一轮又分别被拆分成两部分，直到不可再分为止。
每一轮的比较和交换，需要把数组全部元素都遍历一遍，时间复杂度是O(n)。假如元素个数是n，那么平均情况下需要logn轮，因此快速排序算法总体的平均时间复杂度是O(nlogn)。

选择基准元素

基准元素，英文是pivot，在分治过程中，以基准元素为中心，把其他元素移动到它的左右两边。
最简单的方式是选择数列的第1个元素。
加入有原本逆数序列
- 在这种极端情况下，快速排序需要进行n轮，时间复杂度退化成了O(n2)。

image.png

我们随机挑选一个基准元素

image.png

这样一来，即使在数列完全逆序的情况下，也可以有效地将数列分成两部分。
所以，虽然快速排序的平均时间复杂度是O(nlogn)，但最坏情况下的时间复杂度是O(n2)。

元素的交换（递归实现）

双边循环

首先，选定基准元素pivot，并且设置两个指针left和right，指向数列的最左和最右两个元素。

image.png
接下来进行第1次循环，从right指针开始，让指针所指向的元素和基准元素做比较。如果大于或等于pivot，则指针向左移动；如果小于pivot，则right指针停止移动，切换到left指针。

image.png

完整实例

快速排序类

Class PHA.YX.Arithmetic.QuickSort Extends %RegisteredObject
{

Method quickSortBilateral(arr As PHA.YX.Arithmetic.Array, startIndex As %Integer, endIndex As %Integer)
{
    
    /*  递归结束条件：startIndex大等于endIndex的时候 */
    q:(startIndex >= endIndex) arr
    
    /*  得到基准元素位置 */
    #dim pivotIndex as %Integer = ..partitionBilateral(arr, startIndex, endIndex)
    w "startIndex：" _ startIndex _" endIndex：" _ endIndex_" pivotIndex：" _ pivotIndex,!
    
    /*  根据基准元素，分成两部分递归排序 */
    d ..quickSortBilateral(arr, startIndex, pivotIndex - 1)
    d ..quickSortBilateral(arr, pivotIndex + 1, endIndex)
    
    q arr
}

Method partitionBilateral(arr As PHA.YX.Arithmetic.Array, startIndex As %Integer, endIndex As %Integer)
{
    /*  取第一个位置的元素作为基准元素（也可以选择随机位置） */
    #dim pivot as %Integer = arr.get(startIndex)
    #dim left as %Integer = startIndex
    #dim right as %Integer = endIndex
    while (left '= right){
        
        /*  控制right指针比较并左移 */
        while ((left < right) && (arr.get(right) > pivot)){
            w "first left：" _ left _" right：" _ right _ " arr.get(right)：" _ arr.get(right) _" pivot：" _ pivot,!
            s right = right -1
        } 
        
        /*  控制left指针比较并右移 */
        while ((left < right) && (arr.get(left) <= pivot)){
            w "second left：" _ left _" right：" _ right _" arr.get(left)：" _ arr.get(left) _" pivot：" _ pivot,!
            s left = left + 1
        }
        /*  交换left和right指向的元素 */
        if (left < right){
            #dim p as %Integer = arr.get(left)
            d arr.set(left, arr.get(right))
            d arr.set(right, p)
        }
    }
    d arr.set(startIndex, arr.get(left))
    d arr.set(left, pivot)
    q left
}

}

调用


/// w ##class(PHA.YX.Arithmetic).QuickSortBilateral()
ClassMethod QuickSortBilateral()
{
    s $zt = "ErrQuickSort"
    s array = ##class(PHA.YX.Arithmetic.Array).%New()
    d array.init(8)
    d array.insert(0,41)
    d array.insert(1,73)
    d array.insert(2,64)
    d array.insert(3,55)
    d array.insert(4,36)
    d array.insert(5,27)
    d array.insert(6,88)
    d array.insert(7,19)
    
    #dim mQuickSort as PHA.YX.Arithmetic.QuickSort = ##class(PHA.YX.Arithmetic.QuickSort).%New()
    s array = mQuickSort.quickSortBilateral(array, 0 ,array.length - 1)
    d array.output()
    q ""
ErrQuickSort
    q $ze
}

DHC-APP>w ##class(PHA.YX.Arithmetic).QuickSortBilateral()

19
27
36
41
55
64
73
88

单边循环

而单边循环法则简单得多，只从数组的一边对元素进行遍历和交换。

给出原始数列如下，要求对其从小到大进行排序。

image.png
开始和双边循环法相似，首先选定基准元素pivot。同时，设置一个mark指针指向数列起始位置，这个mark指针代表小于基准元素的区域边界。

image.png
如果遍历到的元素大于基准元素，就继续往后遍历。如果遍历到的元素小于基准元素，则需要做两件事：第一，把mark指针右移1位，因为小于pivot的区域边界增大了1；第二，让最新遍历到的元素和mark指针所在位置的元素交换位置，因为最新遍历的元素归属于小于pivot的区域。首先遍历到元素7，7>4，所以继续遍历。

image.png
接下来遍历到的元素是3，3<4，所以mark指针右移1位。

image.png
随后，让元素3和mark指针所在位置的元素交换，因为元素3归属于小于pivot的区域。

image.png
剩余遍历

image.png

完整实例

快速排序类

Method quickSortUnilateral(arr As PHA.YX.Arithmetic.Array, startIndex As %Integer, endIndex As %Integer)
{
    
    /*  递归结束条件：startIndex大等于endIndex的时候 */
    q:(startIndex >= endIndex) arr
    
    /*  得到基准元素位置 */
    #dim pivotIndex as %Integer = ..partitionUnilateral(arr, startIndex, endIndex)
    w "startIndex：" _ startIndex _" endIndex：" _ endIndex_" pivotIndex：" _ pivotIndex,!
    
    /*  根据基准元素，分成两部分递归排序 */
    d ..quickSortUnilateral(arr, startIndex, pivotIndex - 1)
    d ..quickSortUnilateral(arr, pivotIndex + 1, endIndex)
    
    q arr
}

Method partitionUnilateral(arr As PHA.YX.Arithmetic.Array, startIndex As %Integer, endIndex As %Integer)
{
    /*  取第一个位置的元素作为基准元素（也可以选择随机位置） */
    #dim pivot as %Integer = arr.get(startIndex)
    #dim mark as %Integer = startIndex
    
    for i = (startIndex + 1) : 1 : endIndex {
        if (arr.get(i) < pivot){
            s mark = mark + 1
            #dim p as %Integer = arr.get(mark)
            d arr.set(mark, arr.get(i))
            d arr.set(i, p)
        }
    }
    d arr.set(startIndex, arr.get(mark))
    d arr.set(mark, pivot)
    q mark
}

调用

/// w ##class(PHA.YX.Arithmetic).QuickSortUnilateral()
ClassMethod QuickSortUnilateral()
{
    s $zt = "ErrQuickSort"
    s array = ##class(PHA.YX.Arithmetic.Array).%New()
    d array.init(8)
    d array.insert(0,41)
    d array.insert(1,73)
    d array.insert(2,64)
    d array.insert(3,55)
    d array.insert(4,36)
    d array.insert(5,27)
    d array.insert(6,88)
    d array.insert(7,19)
    
    #dim mQuickSort as PHA.YX.Arithmetic.QuickSort = ##class(PHA.YX.Arithmetic.QuickSort).%New()
    s array = mQuickSort.quickSortUnilateral(array, 0 ,array.length - 1)
    d array.output()
    q ""
ErrQuickSort
    q $ze
}

DHC-APP>w ##class(PHA.YX.Arithmetic).QuickSortUnilateral()
startIndex：0 endIndex：7 pivotIndex：3
startIndex：0 endIndex：2 pivotIndex：0
startIndex：1 endIndex：2 pivotIndex：2
startIndex：4 endIndex：7 pivotIndex：6
startIndex：4 endIndex：5 pivotIndex：4
19
27
36
41
55
64
73
88

元素的交换（非递归实现）

快速排序类


Method quickSortStack(arr As PHA.YX.Arithmetic.Array, startIndex As %Integer, endIndex As %Integer)
{
    #dim quickSortStack as PHA.YX.Arithmetic.Stack = ##class(PHA.YX.Arithmetic.Stack).%New()
    #dim rootParam as %ArrayOfDataTypes = ##class(%ArrayOfDataTypes).%New()
    d rootParam.SetAt(startIndex, "startIndex")
    d rootParam.SetAt(endIndex, "endIndex")
    d quickSortStack.push(rootParam)

    while ('quickSortStack.isEmpty()){
        #dim param as %ArrayOfDataTypes = quickSortStack.pop()
        w "param.GetAt(startIndex)：" _ param.GetAt("startIndex") _ " param.GetAt(endIndex)：" _ param.GetAt("endIndex") ,!
        #dim pivotIndex as %Integer = ..partitionStack(arr, param.GetAt("startIndex"), param.GetAt("endIndex"))
        if ((param.GetAt("startIndex")) < (pivotIndex - 1) ){
            #dim leftParam as %ArrayOfDataTypes = ##class(%ArrayOfDataTypes).%New()
            d leftParam.SetAt(param.GetAt("startIndex"), "startIndex")
            d leftParam.SetAt(pivotIndex - 1, "endIndex")
            d quickSortStack.push(leftParam)
        }
        if ((pivotIndex + 1) < (param.GetAt("endIndex"))){
            #dim rightParam as %ArrayOfDataTypes = ##class(%ArrayOfDataTypes).%New()
            d rightParam.SetAt(pivotIndex + 1, "startIndex")
            d rightParam.SetAt(param.GetAt("endIndex"), "endIndex")
            d quickSortStack.push(rightParam)
        }
    }
    q arr
}

Method partitionStack(arr As PHA.YX.Arithmetic.Array, startIndex As %Integer, endIndex As %Integer)
{
    /*  取第一个位置的元素作为基准元素（也可以选择随机位置） */
    #dim pivot as %Integer = arr.get(startIndex)
    #dim mark as %Integer = startIndex
    
    for i = (startIndex + 1) : 1 : endIndex {
        if (arr.get(i) < pivot){
            s mark = mark + 1
            #dim p as %Integer = arr.get(mark)
            d arr.set(mark, arr.get(i))
            d arr.set(i, p)
        }
    }
    d arr.set(startIndex, arr.get(mark))
    d arr.set(mark, pivot)
    q mark
}

调用

/// w ##class(PHA.YX.Arithmetic).QuickSortStack()
ClassMethod QuickSortStack()
{
    s $zt = "QuickSortStack"
    s array = ##class(PHA.YX.Arithmetic.Array).%New()
    d array.init(8)
    d array.insert(0,41)
    d array.insert(1,73)
    d array.insert(2,64)
    d array.insert(3,55)
    d array.insert(4,36)
    d array.insert(5,27)
    d array.insert(6,88)
    d array.insert(7,19)
    
    #dim mQuickSort as PHA.YX.Arithmetic.QuickSort = ##class(PHA.YX.Arithmetic.QuickSort).%New()
    s array = mQuickSort.quickSortStack(array, 0 ,array.length - 1)
    d array.output()
    q ""
QuickSortStack
    q $ze
}

DHC-APP>w ##class(PHA.YX.Arithmetic).QuickSortStack()
param.GetAt(startIndex)：0 param.GetAt(endIndex)：7
param.GetAt(startIndex)：4 param.GetAt(endIndex)：7
param.GetAt(startIndex)：4 param.GetAt(endIndex)：5
param.GetAt(startIndex)：0 param.GetAt(endIndex)：2
param.GetAt(startIndex)：1 param.GetAt(endIndex)：2
19
27
36
41
55
64
73
88

第十四章 Caché 算法与数据结构 快速排序

第十四章 Caché 算法与数据结构 快速排序

定义

流程

选择基准元素

元素的交换（递归实现）

双边循环

完整实例

快速排序类

调用

单边循环

完整实例

快速排序类

调用

元素的交换（非递归实现）

快速排序类

调用

第十四章 Caché 算法与数据结构快速排序

第十四章 Caché 算法与数据结构快速排序