四談快速排序（含尾遞歸）

BicycleWarrior 發(fā)布于2019-08-22 14:01 / 3425人閱讀

摘要：一談，原始的快速排序的位置已經(jīng)固定，不用在排二談，優(yōu)化后的快速排序適時的采用插入排序代碼略隨機化快速排序改變選擇主元的方式，從選擇末尾的元素，改為隨機選擇修改函數(shù)隨機索引與最后一個元素交換，其余不變三路快排都已經(jīng)排好序末

一談，原始的快速排序

function swap(arr, i, j) {
    let temp = arr[i]
    arr[i] = arr[j]
    arr[j] = temp
}

function quickSort(arr, fromIndex, length) {
    if (length < 2) {
        return
    }
    // arr[midIndex] 的位置已經(jīng)固定，不用在排
    let midIndex = partition(arr, fromIndex, length)
    let subLength = midIndex - fromIndex
    quickSort(arr, fromIndex, subLength)
    if (midIndex + 1 !== arr.length) {
        quickSort(arr, midIndex + 1, length - subLength - 1)
    }
}

function partition(arr, fromIndex, length) {
    let lastIndex = fromIndex + length - 1
    let pivot = arr[lastIndex]
    let lastIndexUnderPivot = fromIndex - 1
    for (let currentIndex = fromIndex; currentIndex < lastIndex; currentIndex++) {
        if (arr[currentIndex] <= pivot) {
            swap(arr, lastIndexUnderPivot + 1, currentIndex)
            lastIndexUnderPivot++
        }
    }
    swap(arr, lastIndexUnderPivot + 1, lastIndex)
    return lastIndexUnderPivot + 1
}

let arr = [1, 5, 2, 11, 7, 3, 1, 6, 17, 10, 312, 312, 1, 1, 2323, 4, 56, 3, 14, 5543]
quickSort(arr, 0, arr.length)
console.log(arr) // [ 1, 1, 1, 1, 2, 3, 3, 4, 5, 6, 7, 10, 11, 14, 17, 56, 312, 312, 2323, 5543 ]

二談，優(yōu)化后的快速排序 適時的采用插入排序

代碼略

隨機化快速排序

改變選擇主元 pivot 的方式，從選擇末尾的元素，改為隨機選擇

修改 partition 函數(shù)

function partition(arr, fromIndex, length) {
    let lastIndex = fromIndex + length - 1
    let randomIndex = fromIndex + Math.floor(Math.random() * length) // 隨機索引
    swap(arr, randomIndex, lastIndex) // 與最后一個元素交換，其余不變
    let pivot = arr[lastIndex]
    let lastIndexUnderPivot = fromIndex - 1
    for (let currentIndex = fromIndex; currentIndex < lastIndex; currentIndex++) {
        if (arr[currentIndex] <= pivot) {
            swap(arr, lastIndexUnderPivot + 1, currentIndex)
            lastIndexUnderPivot++
        }
    }
    swap(arr, lastIndexUnderPivot + 1, lastIndex)
    return lastIndexUnderPivot + 1
}

三路快排

function swap(arr, i, j) {
    let temp = arr[i]
    arr[i] = arr[j]
    arr[j] = temp
}

function quickSort(arr, fromIndex, length) {
    if (length < 2) {
        return
    }
    let [firstIndexEqualPivot, lastIndexEqualPivot] = partition(arr, fromIndex, length)
    // pivot 都已經(jīng)排好序
    quickSort(arr, fromIndex, firstIndexEqualPivot - fromIndex)
    let subLength = fromIndex + length - 1 - (lastIndexEqualPivot + 1) + 1
    // subLength =  末尾索引 - 第一個大于主元素的索引 + 1
    quickSort(arr, lastIndexEqualPivot + 1, subLength)
}

function partition(arr, fromIndex, length) {
    let lastIndex = fromIndex + length - 1
    let randomIndex = fromIndex + Math.floor(Math.random() * length)
    swap(arr, randomIndex, lastIndex)
    let pivot = arr[lastIndex]
    let lastIndexUnderPivot = fromIndex - 1
    let firstIndexOverPivot = lastIndex
    let currentLeftIndex = fromIndex
    let currentRightIndex = lastIndex - 1
    while (currentLeftIndex <= currentRightIndex) {
        while (arr[currentLeftIndex] <= pivot) {
            if (arr[currentLeftIndex] < pivot) {
                swap(arr, lastIndexUnderPivot + 1, currentLeftIndex)
                lastIndexUnderPivot++
            }
            currentLeftIndex++
        }
        
        while (arr[currentRightIndex] >= pivot) {
            if (arr[currentRightIndex] > pivot) {
                swap(arr, firstIndexOverPivot - 1, currentRightIndex)
                firstIndexOverPivot--
            }
            currentRightIndex--
        }
        // 越界
        if (currentLeftIndex > lastIndex - 1) {
            break
        }
        // 越界
        if (currentRightIndex < fromIndex) {
            break
        }
        // 越界
        if (currentLeftIndex > currentRightIndex) {
            break
        }
        // 此時arr[currentLeftIndex] > pivot, arr[currentRightIndex] < pivot
        swap(arr, currentLeftIndex, currentRightIndex)
    }
    swap(arr, firstIndexOverPivot, lastIndex)
    let firstIndexEqualPivot = lastIndexUnderPivot + 1
    let lastIndexEqualPivot = firstIndexOverPivot
    return [firstIndexEqualPivot, lastIndexEqualPivot]
}

let arr = [1, 5, 2, 11, 7, 3, 1, 6, 17, 10]
quickSort(arr, 0, arr.length)
console.log(arr) // [ 1, 2, 3, 5, 6, 1, 7, 10, 11, 17 ]

尾遞歸

套路和三談歸并排序（含尾遞歸）中的一樣，將要用但是來不及用的參數(shù)存起來，在合適的時候，再用，這里的合適一般都是計算至葉結點的時候

僅需修改 quickSort 函數(shù)如下，傳入?yún)?shù)時，多個空數(shù)組

function quickSort(arr, fromIndex, length, argsArr) {
    if (length < 2) {
        if (argsArr.length === 0) {
            return
        }
        let args = argsArr.pop()
        return quickSort(arr, args[0], args[1], argsArr)
    }
    let [firstIndexEqualPivot, lastIndexEqualPivot] = partition(arr, fromIndex, length)
    // pivot 都已經(jīng)排好序
    argsArr.push([lastIndexEqualPivot + 1, fromIndex + length - 1 - (lastIndexEqualPivot + 1) + 1])
    return quickSort(arr, fromIndex, firstIndexEqualPivot - fromIndex, argsArr)
}
...
let arr = [1, 5, 2, 11, 7, 3, 1, 6, 17, 10]
quickSort(arr, 0, arr.length, [])
console.log(arr) // [ 1, 2, 3, 5, 6, 1, 7, 10, 11, 17 ]

四談，快速排序的應用，top-k 問題

BFPRT算法

《算法導論》9.3 最壞情況為線性時間的選擇算法

輸入是n個不同元素組成的數(shù)組，求第i小的元素，i從0算起

function insertSort(arr, fromIndex, length) {
    for (let currentIndex = fromIndex + 1; currentIndex < fromIndex + length; currentIndex++) {
        let currentCard = arr[currentIndex]
        let j = currentIndex - 1
        for (j; j >= fromIndex; j--) {
            if (currentCard > arr[j]) {
                break
            } else {
                arr[j + 1] = arr[j]
            }
        }
        arr[j + 1] = currentCard
    }
}

// 確定n個不同元素的數(shù)組中，第i小的元素
function BFPRT(arr, flag) {
    if (arr.length === 1) {
        return arr[0]
    }
    let medianArr = []
    for (let i = 0; i < arr.length; i = i + 5) {
        if (i + 5 > arr.length) {
            insertSort(arr, i, arr.length - i)
            if ((arr.length - i) % 2 === 0) {
                let index = (arr.length - i) / 2 + i - 1
                medianArr.push(arr[index])
            } else {
                let index = Math.floor((arr.length - i) / 2) + i
                medianArr.push(arr[index])
            }
        } else {
            insertSort(arr, i, 5)
            medianArr.push(arr[i + 2])
        }
        // 對每組元素進行插入排序，確定中位數(shù)
    }
    let subFlag = 0
    if (medianArr.length % 2 === 0) {
        subFlag = medianArr.length / 2 - 1
    } else {
        subFlag = Math.floor(medianArr.length / 2)
    }
    let pivot = BFPRT(medianArr, subFlag)
    let [leftArr, rightArr] = partition(arr, pivot)
    if (leftArr.length === flag) {
        return pivot
    }
    if (leftArr.length > flag) {
        return BFPRT(leftArr, flag)
    }
    if (leftArr.length < flag) {
        return BFPRT(rightArr, flag - leftArr.length - 1)
    }
}

function partition(arr, pivot) {
    let leftArr = []
    let rightArr = []
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] < pivot) {
            leftArr.push(arr[i])
        }
        if (arr[i] > pivot) {
            rightArr.push(arr[i])
        }
    }
    return [leftArr, rightArr]
}

let arr = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 11, 13]
console.log(BFPRT(arr, 2))

GPU云服務器云服務器 java遞歸快速排序快速排序快速排序函數(shù) 快速排序算法

文章版權歸作者所有，未經(jīng)允許請勿轉載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/92773.html

三談歸并排序（含尾遞歸）

摘要：一談，原始的歸并排序二談，優(yōu)化后的歸并排序優(yōu)化算法的指導思想之一，找到某些可以簡化處理的特殊情況合并時的特殊情況當?shù)淖詈笠粋€元素小于的第一個元素時，那么順序就應該是當?shù)淖詈笠粋€元素小于的第一個元素時，那么順序就應該是所以修改函數(shù)如下適時一談，原始的歸并排序 function mergeSort(arr) { let { length } = arr ...

MRZYD 2019-08-22 13:59 評論0 收藏0
算法系列——JavaScript快速排序思想實現(xiàn)

摘要：源碼實現(xiàn)快速排序理論理解起來很容易，但經(jīng)常是實際寫代碼，無從下手，下面是我根據(jù)快排的步驟實現(xiàn)的遞歸快速排序。合并第一次快速排序的，，數(shù)組。原理快速排序離不開遞歸的思想，你如果不了解遞歸，可以結合我另外一篇文章來學習算法入門之遞歸分而治之思想的實現(xiàn) 網(wǎng)上有有趣的動態(tài)圖來表示快速排序，但其實我們大部分程序員都是腦子不太好使那種，即使看了形象生動的動態(tài)圖，還是想不到具體實現(xiàn)思路。排序...

lentrue 2019-08-21 17:33 評論0 收藏0
PHP排序算法之快速排序

摘要：實現(xiàn)代碼判斷參數(shù)是否是一個數(shù)組遞歸出口數(shù)組長度為，直接返回數(shù)組數(shù)組元素有多個，則定義兩個數(shù)組循環(huán)遍歷數(shù)組，把第一個元素當做比較的對象判斷當前元素的大小遞歸調用將所有的結果合并原理：找到當前數(shù)組中的任意一個元素（一般選擇第一個元素），作為標準，新建兩個空數(shù)組left、rignt，遍歷整個數(shù)組元素，如果遍歷到的元素比當前的元素小就放到數(shù)組left，比當前的元素大放到rignt，然后再對新...

CoderDock 2019-07-01 10:30 評論0 收藏0
算法之旅 | 快速排序法

摘要：今天跟大家分享多種排序算法里使用較廣泛，速度快的排序算法快速排序法平均時間復雜度為。快速排序法的原理快速排序是一種劃分交換排序，它采用分治的策略，通常稱其為分治法。 HTML5學堂-碼匠：前幾期算法之旅跟大家分享了冒泡排序法和選擇排序法，它們都屬于時間復雜度為O(n^2)的慢排序。今天跟大家分享多種排序算法里使用較廣泛，速度快的排序算法—— 快速排序法 [ 平均時間復雜度為O (n l...

AlanKeene 2019-08-22 11:11 評論0 收藏0