四谈快速排序（含尾递归）

BicycleWarrior 发布于2019-08-22 14:01 / 3419人阅读

摘要：一谈，原始的快速排序的位置已经固定，不用在排二谈，优化后的快速排序适时的采用插入排序代码略随机化快速排序改变选择主元的方式，从选择末尾的元素，改为随机选择修改函数随机索引与最后一个元素交换，其余不变三路快排都已经排好序末

一谈，原始的快速排序

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] 的位置已经固定，不用在排
    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 ]

二谈，优化后的快速排序 适时的采用插入排序

代码略

随机化快速排序

改变选择主元 pivot 的方式，从选择末尾的元素，改为随机选择

修改 partition 函数

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 都已经排好序
    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 ]

尾递归

套路和三谈归并排序（含尾递归）中的一样，将要用但是来不及用的参数存起来，在合适的时候，再用，这里的合适一般都是计算至叶结点的时候

仅需修改 quickSort 函数如下，传入参数时，多个空数组

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 都已经排好序
    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个不同元素组成的数组，求第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个不同元素的数组中，第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])
        }
        // 对每组元素进行插入排序，确定中位数
    }
    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递归快速排序快速排序快速排序函数快速排序算法

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/92773.html

三谈归并排序（含尾递归）

摘要：一谈，原始的归并排序二谈，优化后的归并排序优化算法的指导思想之一，找到某些可以简化处理的特殊情况合并时的特殊情况当的最后一个元素小于的第一个元素时，那么顺序就应该是当的最后一个元素小于的第一个元素时，那么顺序就应该是所以修改函数如下适时一谈，原始的归并排序 function mergeSort(arr) { let { length } = arr ...

MRZYD 2019-08-22 13:59 评论0 收藏0
算法系列——JavaScript快速排序思想实现

摘要：源码实现快速排序理论理解起来很容易，但经常是实际写代码，无从下手，下面是我根据快排的步骤实现的递归快速排序。合并第一次快速排序的，，数组。原理快速排序离不开递归的思想，你如果不了解递归，可以结合我另外一篇文章来学习算法入门之递归分而治之思想的实现网上有有趣的动态图来表示快速排序，但其实我们大部分程序员都是脑子不太好使那种，即使看了形象生动的动态图，还是想不到具体实现思路。排序...

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

摘要：实现代码判断参数是否是一个数组递归出口数组长度为，直接返回数组数组元素有多个，则定义两个数组循环遍历数组，把第一个元素当做比较的对象判断当前元素的大小递归调用将所有的结果合并原理：找到当前数组中的任意一个元素（一般选择第一个元素），作为标准，新建两个空数组left、rignt，遍历整个数组元素，如果遍历到的元素比当前的元素小就放到数组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