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

MRZYD 發布于2019-08-22 13:59 / 384人閱讀

摘要：一談，原始的歸并排序二談，優化后的歸并排序優化算法的指導思想之一，找到某些可以簡化處理的特殊情況合并時的特殊情況當的最后一個元素小于的第一個元素時，那么順序就應該是當的最后一個元素小于的第一個元素時，那么順序就應該是所以修改函數如下適時

一談，原始的歸并排序

function mergeSort(arr) {
    let {
        length
    } = arr
    if (length < 2) {
        return arr
    }
    let midIndex = Math.floor(length / 2)
    let leftArr = mergeSort(arr.slice(0, midIndex))
    let rightArr = mergeSort(arr.slice(midIndex))
    return merge(leftArr, rightArr)
}

function merge(leftArr, rightArr) {
    let i = 0,
        j = 0,
        arr = []
    while (true) {
        if (i === leftArr.length) {
            arr.push(...rightArr.slice(j))
            break
        }
        if (j === rightArr.length) {
            arr.push(...leftArr.slice(i))
            break
        }
        if (leftArr[i] < rightArr[j]) {
            arr.push(leftArr[i])
            i++
        }
        if (rightArr[j] <= leftArr[i]) {
            arr.push(rightArr[j])
            j++
        }
    }
    return arr
}

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

二談，優化后的歸并排序

優化算法的指導思想之一，找到某些可以簡化處理的特殊情況

合并時的特殊情況

當 leftArr 的最后一個元素小于 rightArr 的第一個元素時，那么順序就應該是 [leftArr, rightArr]

當 rightArr 的最后一個元素小于 leftArr 的第一個元素時，那么順序就應該是 [rightArr, leftArr]

所以修改 mergeSort 函數如下

function mergeSort(arr) {
    let {
        length
    } = arr
    if (length < 2) {
        return arr
    }
    let midIndex = Math.floor(length / 2)
    let leftArr = mergeSort(arr.slice(0, midIndex))
    let rightArr = mergeSort(arr.slice(midIndex))
    if (leftArr[leftArr.length - 1] <= rightArr[0]) {
        return [...leftArr, ...rightArr]
    }
    if (rightArr[rightArr.length - 1] <= leftArr[0]) {
        return [...rightArr, ...leftArr]
    }
    return merge(leftArr, rightArr)
}
...

適時的利用插入排序

當數組的長度變小到一定程序時，采用插入排序

遞歸優化-尾遞歸

先修改代碼如下

function mergeSort(arr, fromIndex, length) {
    if (length < 2) {
        return
    }
    mergeSort(arr, fromIndex, Math.floor(length / 2))
    mergeSort(arr, fromIndex + Math.floor(length / 2), length - Math.floor(length / 2))
    merge(arr, fromIndex, length)
}

function merge(arr, fromIndex, length) {
    let leftArr = arr.slice(fromIndex, fromIndex + Math.floor(length / 2))
    let rightArr = arr.slice(fromIndex + Math.floor(length / 2), fromIndex + length)
    let i = 0,
        j = 0,
        orderedArr = []
    while (true) {
        if (i === leftArr.length) {
            orderedArr.push(...rightArr.slice(j))
            break
        }
        if (j === rightArr.length) {
            orderedArr.push(...leftArr.slice(i))
            break
        }
        if (leftArr[i] < rightArr[j]) {
            orderedArr.push(leftArr[i])
            i++
        }
        if (rightArr[j] <= leftArr[i]) {
            orderedArr.push(rightArr[j])
            j++
        }
    }
    arr.splice(fromIndex, length, ...orderedArr)
}

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

把傳過的參數都記錄下來，存在 argsArr 中

例如在計算 fromIndex 為 0， length 為 10 時，分為三步

先要通過mergeSort計算 fromIndex 為 0， length 為 5

再通過mergeSort計算 fromIndex 為 5， length 為 5

最后merge (arr, 0, 10)

由于尾遞歸調用，只能先計算 mergeSort(arr, 0, 5, argsArr)

而把 [0, 10, 5, 5] 存起來，前兩個參數是merge的參數，后兩個是mergeSort的參數

用過的參數就把它去掉，所以[0, 10, 5, 5] => [0, 10] =>

function mergeSort(arr, fromIndex, length, argsArr) {
    if (length < 2) {
        let args = argsArr.pop()
        while (args) {
            if (args.length === 4) {
                argsArr.push([args[0], args[1]])
                break
            }
            if (args.length === 2) {
                merge(arr, args[0], args[1])
                args = argsArr.pop()
            }
        }
        if (args) {
            return mergeSort(arr, args[2], args[3], argsArr)
        } else {
            return
        }
    }
    argsArr.push([fromIndex, length, fromIndex + Math.floor(length / 2), length - Math.floor(length / 2)])
    return mergeSort(arr, fromIndex, Math.floor(length / 2), argsArr)
}

function merge(arr, fromIndex, length) {
    let leftArr = arr.slice(fromIndex, fromIndex + Math.floor(length / 2))
    let rightArr = arr.slice(fromIndex + Math.floor(length / 2), fromIndex + length)
    let i = 0,
        j = 0,
        orderedArr = []
    while (true) {
        if (i === leftArr.length) {
            orderedArr.push(...rightArr.slice(j))
            break
        }
        if (j === rightArr.length) {
            orderedArr.push(...leftArr.slice(i))
            break
        }
        if (leftArr[i] < rightArr[j]) {
            orderedArr.push(leftArr[i])
            i++
        }
        if (rightArr[j] <= leftArr[i]) {
            orderedArr.push(rightArr[j])
            j++
        }
    }
    arr.splice(fromIndex, length, ...orderedArr)
}

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

三談，迭代版歸并排序

其中 merge 函數不變，修改 mergeSort 函數

function mergeSort(arr) {
    for (let size = 1; size < arr.length; size = size * 2) {
        for (let i = 0; i + size < arr.length; i = i + size * 2) {
            merge(arr, i, size * 2)
        }
    }
}
function merge(arr, fromIndex, length) {
  ...
}

云服務器 GPU云服務器歸并排序二路歸并排序歸并排序算法 java歸并排序

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

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

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

摘要：一談，原始的快速排序的位置已經固定，不用在排二談，優化后的快速排序適時的采用插入排序代碼略隨機化快速排序改變選擇主元的方式，從選擇末尾的元素，改為隨機選擇修改函數隨機索引與最后一個元素交換，其余不變三路快排都已經排好序末一談，原始的快速排序 function swap(arr, i, j) { let temp = arr[i] arr[i] = arr[j] ...

BicycleWarrior 2019-08-22 14:01 評論0 收藏0
歸并排序 - Algorithms, Part I, week 3 MERGESORTS

摘要：兩個單元素數組的合并實際就是對這兩個數進行了排序，即變為，同樣再對后一組的兩個數歸并排序，即變為，再將兩單元數組歸并成四單元數組即和歸并為。前言本周講解兩個50多年前發明，但今天仍然很重要的經典算法 (歸并排序和快速排序) 之一 -- 歸并排序，幾乎每個軟件系統中都可以找到其中一個或兩個的實現，并研究這些經典方法的新變革。我們的涉及范圍從數學模型中解釋為什么這些方法有效到使這些算法...

Jokcy 2019-08-19 11:35 評論0 收藏0
Java排序之歸并排序

摘要：排序之歸并排序簡介歸并排序的算法是將多個有序數據表合并成一個有序數據表。如果參與合并的只有兩個有序表，則成為二路合并。對于一個原始的待排序數列，往往可以通過分割的方法來歸結為多路合并排序。 Java排序之歸并排序 1. 簡介歸并排序的算法是將多個有序數據表合并成一個有序數據表。如果參與合并的只有兩個有序表，則成為二路合并。對于一個原始的待排序數列，往往可以通過分割的方法來歸結為多路合...

gityuan 2019-08-15 18:10 評論0 收藏0