第十四章 Caché 算法與數(shù)據(jù)結(jié)構(gòu) 快速排序

定義

同冒泡排序一樣蹂匹，快速排序也屬于交換排序次洼，通過元素之間的比較和交換位置來達(dá)到排序的目的戚揭。
不同的是雕旨，冒泡排序在每一輪中只把1個元素冒泡到數(shù)列的一端搓译，而快速排序則在每一輪挑選一個基準(zhǔn)元素悲柱，并讓其他比它大的元素移動到數(shù)列一邊，比它小的元素移動到數(shù)列的另一邊些己，從而把數(shù)列拆解成兩個部分豌鸡。
這種思路就叫作分治法。

image.png

流程

image.png

如圖所示段标，在分治法的思想下涯冠，原數(shù)列在每一輪都被拆分成兩部分，每一部分在下一輪又分別被拆分成兩部分逼庞，直到不可再分為止蛇更。
每一輪的比較和交換，需要把數(shù)組全部元素都遍歷一遍，時間復(fù)雜度是O(n)派任。假如元素個數(shù)是n砸逊，那么平均情況下需要logn輪，因此快速排序算法總體的平均時間復(fù)雜度是O(nlogn)掌逛。

選擇基準(zhǔn)元素

基準(zhǔn)元素师逸，英文是pivot，在分治過程中颤诀，以基準(zhǔn)元素為中心字旭，把其他元素移動到它的左右兩邊对湃。
最簡單的方式是選擇數(shù)列的第1個元素崖叫。
加入有原本逆數(shù)序列
- 在這種極端情況下，快速排序需要進(jìn)行n輪拍柒，時間復(fù)雜度退化成了O(n2)心傀。

image.png

我們隨機挑選一個基準(zhǔn)元素

image.png

這樣一來，即使在數(shù)列完全逆序的情況下拆讯，也可以有效地將數(shù)列分成兩部分脂男。
所以，雖然快速排序的平均時間復(fù)雜度是O(nlogn)种呐，但最壞情況下的時間復(fù)雜度是O(n2)宰翅。

元素的交換（遞歸實現(xiàn)）

雙邊循環(huán)

首先，選定基準(zhǔn)元素pivot爽室，并且設(shè)置兩個指針left和right汁讼，指向數(shù)列的最左和最右兩個元素。

image.png
接下來進(jìn)行第1次循環(huán)阔墩，從right指針開始嘿架，讓指針?biāo)赶虻脑睾突鶞?zhǔn)元素做比較。如果大于或等于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)
{
    
    /*  遞歸結(jié)束條件：startIndex大等于endIndex的時候 */
    q:(startIndex >= endIndex) arr
    
    /*  得到基準(zhǔn)元素位置 */
    #dim pivotIndex as %Integer = ..partitionBilateral(arr, startIndex, endIndex)
    w "startIndex：" _ startIndex _" endIndex：" _ endIndex_" pivotIndex：" _ pivotIndex,!
    
    /*  根據(jù)基準(zhǔn)元素，分成兩部分遞歸排序 */
    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)
{
    /*  取第一個位置的元素作為基準(zhǔn)元素（也可以選擇隨機位置） */
    #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
}

}

調(diào)用


/// 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

單邊循環(huán)

而單邊循環(huán)法則簡單得多扎唾，只從數(shù)組的一邊對元素進(jìn)行遍歷和交換蜀肘。

給出原始數(shù)列如下，要求對其從小到大進(jìn)行排序稽屏。

image.png
開始和雙邊循環(huán)法相似扮宠，首先選定基準(zhǔn)元素pivot。同時，設(shè)置一個mark指針指向數(shù)列起始位置坛增，這個mark指針代表小于基準(zhǔn)元素的區(qū)域邊界获雕。

image.png
如果遍歷到的元素大于基準(zhǔn)元素，就繼續(xù)往后遍歷收捣。如果遍歷到的元素小于基準(zhǔn)元素届案，則需要做兩件事：第一，把mark指針右移1位罢艾，因為小于pivot的區(qū)域邊界增大了1楣颠；第二，讓最新遍歷到的元素和mark指針?biāo)谖恢玫脑亟粨Q位置咐蚯，因為最新遍歷的元素歸屬于小于pivot的區(qū)域童漩。首先遍歷到元素7，7>4春锋，所以繼續(xù)遍歷矫膨。

image.png
接下來遍歷到的元素是3，3<4期奔，所以mark指針右移1位侧馅。

image.png
隨后，讓元素3和mark指針?biāo)谖恢玫脑亟粨Q呐萌，因為元素3歸屬于小于pivot的區(qū)域馁痴。

image.png
剩余遍歷

image.png

完整實例

快速排序類

Method quickSortUnilateral(arr As PHA.YX.Arithmetic.Array, startIndex As %Integer, endIndex As %Integer)
{
    
    /*  遞歸結(jié)束條件：startIndex大等于endIndex的時候 */
    q:(startIndex >= endIndex) arr
    
    /*  得到基準(zhǔn)元素位置 */
    #dim pivotIndex as %Integer = ..partitionUnilateral(arr, startIndex, endIndex)
    w "startIndex：" _ startIndex _" endIndex：" _ endIndex_" pivotIndex：" _ pivotIndex,!
    
    /*  根據(jù)基準(zhǔn)元素，分成兩部分遞歸排序 */
    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)
{
    /*  取第一個位置的元素作為基準(zhǔn)元素（也可以選擇隨機位置） */
    #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
}

調(diào)用

/// 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

元素的交換（非遞歸實現(xiàn)）

快速排序類


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)
{
    /*  取第一個位置的元素作為基準(zhǔn)元素（也可以選擇隨機位置） */
    #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
}

調(diào)用

/// 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