快速排序動(dòng)態(tài)過程演示

快排的思路很簡(jiǎn)單, 選擇一個(gè)基準(zhǔn)元素, 把比這個(gè)元素大的放到右邊, 小的放到左邊, 這樣就分成了兩組
然后對(duì)左邊的那一組和右邊的那一組分別再進(jìn)行上面的操作
遞歸進(jìn)行,如果一組元素的長(zhǎng)度為1, 就是遞歸的出口了

考試時(shí)候一般要求給出快速排序分劃交換的過程

開始: 50, 79, 8, 56, 32, 41, 85, 26, 70

要注意由于教科書上采用的是兩個(gè)指針從左右掃描分組的交換策略
因此在排序的過程中并不是簡(jiǎn)單地分成兩組
順序需要與程序?qū)嶋H運(yùn)行的一致
這也是快排不穩(wěn)定的原因吧
如果采取新建數(shù)組來分別存儲(chǔ)兩個(gè)分組
那么快排是穩(wěn)定的
只是空間復(fù)雜度會(huì)更高一些

第一趟: [26, 8,41, 32 ] 50 [56, 85, 79, 70]
第二趟: [8] 26 [41, 32] 50 56 [85, 79, 70]
第三趟: 8 26 [32] 41 50 56 [70, 79] 85
第四趟: 8 26 32 41 50 56 70 [79] 85
第五趟: 8 26 32 41 50 56 70 79 85

JavaScript實(shí)現(xiàn)如下:

/*
 * 快速排序, 不使用另外的數(shù)組, 在原數(shù)組上原地排序
 *
 * @param array - 待排序的數(shù)組
 * @param start - 排序的起始位置下標(biāo)
 * @param end - 排序的結(jié)束位置下標(biāo)
 */
function quickSort(array, start, end)
{
    // 遞歸出口
    if(end <= start)
    {
        return
    }

    const datum = array[start] // 取最左邊的元素作為基準(zhǔn)變量
    let left = start // 左指針
    let right = end + 1 // 右指針
    while(left < right)
    {
        // 從左邊開始向右找一個(gè)比基準(zhǔn)元素大的元素, 注意要防止越界
        left ++
        while(array[left] < datum && left < end)
        {
            left ++
        }

        // 從右邊開始向左找一個(gè)比基準(zhǔn)元素小的元素
        // 向左尋找的過程中不會(huì)越界, 臨界情況是右指針移動(dòng)到基準(zhǔn)元素位置
        right --
        while(array[right] > datum)
        {
            right --
        }

        // 交換這兩個(gè)元素
        if(left < right)
        {
            swap(array, left, right)
        }
    }
    
    // 臨界情況下, 右指針移動(dòng)到基準(zhǔn)元素位置
    // 這個(gè)時(shí)候, 就不必再交換基準(zhǔn)元素了, 直接分組即可
    // 左邊的那一組元素個(gè)數(shù)肯定為 -1, 會(huì)直接到達(dá)遞歸出口
    if(datum < right)
    {
        // 交換基準(zhǔn)元素, 將原數(shù)組分成兩組
        swap(array, datum, right)
    }


    // 分別對(duì)兩組進(jìn)行遞歸
    quickSort(array, start, right - 1)
    quickSort(array, right + 1, end)
}