排序演算法 下

以下被稱為分布式排序的演算法，原始陣列中的資料會分發到多個中間結構（桶），再合起來放回原始陣列，最著名的分布式演算法有計數排序、桶排序和基數排序，這三種演算法非常相似，

計數排序

計數排序是一種用來排序整數的優秀演算法，時間復雜度為O(n + k)，其中k是臨時計數陣列的大小，但是，他需要更多的記憶體來存放臨時變數，

• 先創建一個排序資料中最大值 + 1創建一個陣列(關于這部分我剛開始也不是很明白，js的陣列不是動態的嗎!何必多此一舉去找排序資料的最大值，然后創建一個陣列呢???后來想了一下陣列的擴容是不是要資料遷移，那樣的確不如提前創建大一點，然后找了一下資料: 探究JS V8引擎下的“陣列”底層實作)，感興趣的可以瞧一瞧，
• 然后開始計數，其實就是以下標代表資料，然后以值作為資料出現的次數(分布式中的第一步)
• 回圈計數的陣列，然后將其回歸到原陣列上(分布式中的第二步)

export function sortArray(arr: Array<number>) {
    
    if (arr.length < 2){
        return;
    }
    
    let len = findMaxNumber(arr) + 1;
    let countArr = new Array(len).fill(0);

    for (let i = 0; i < arr.length; i++) {
        countArr[arr[i]]++;
    }

    for (let i = 0,index = 0; i < countArr.length; i++) {

        for (let j = 0; j < countArr[i]; j++) {
            arr[index++] = i;
        }
    }
}

/**
 * 找最大數
 * @param arr
 */
function findMaxNumber(arr: Array<number>):number {
    let max:number = 0;
    
    for (let i = 0; i < arr.length; i++) {
        if(arr[i] > max){
            max = arr[i];
        }
    }
    return max;
}


let arr = [54,8,45,7, 1,2,45,9,8,452,35,754,127,6,21,124,454]
sortArray(arr)

// @ts-ignore
console.log(arr)

可以看出這種排序很適合那種有多個重復資料的整數陣列，但是資料中有一個特別大的時候，計數陣列將會占用很大的記憶體

還有這里創建的陣列是 最大值 + 1，因為陣列的下標是0開始的，所以 +1確保最大值也能加入資料

桶排序

桶排序也稱之為箱排序，也是分布式排序演算法中的一種，它將元素分為不同的桶(較小的陣列)，然后使用一個簡單的排序演算法排序(比如說插入排序)，然后合并陣列為結果

對于桶排序演算法，我們需要指定需要多少個桶來排序各個元素，默認情況下，我們會使用5個桶(這里我認為是每個桶的容量為5，而且看這個作者命名bucketSize，也覺得就是桶容量，不過確定了一個桶的容量，自然就確定了桶的個數，后面我還是以桶容量來說明該引數)，桶排序在所有元素平分到各個桶時的表現最好，如果元素非常稀疏，則使用更多的桶會更好，如果元素非常密集，則使用較少的桶會比較好，因此我們允許bucketSize以引數的形式傳遞

• 第一步: 創建桶

  創建桶看似很簡單，實際上還是有點難度的，需要做到幾點

  • 算出桶的個數: Math.floor((最大值 - 最小值 ) / 單個桶的容量) + 1
  • 然后創建一個桶的個數對應大小的陣列，內部填充[]，注意這里不能使用fill填充，fill填充的陣列是同一個參考，所以會導致失敗(這里創建了一個二維陣列)
  • 將排序元素塞到對應的桶里去: (當前值 - 最小值) / 單個桶的容量，其實這個塞入的程序就已經對桶內資料進行了一次粗略排序

• 第二步: 對桶排序

  傳回的是一個二維陣列，桶是有序的(0號桶的內容會都小于1號桶的內容)

  使用插入排序對桶內資料排序

  組合為新的陣列回傳

import {sortArray as insertSort} from "./InsertSort"

export function sortArray(arr: Array<number>, bucketSize: number = 5) {

    if (arr.length < 2) {
        return arr;
    }

    // 創建桶
    let buckets = createBuckets(arr, bucketSize);
    // 桶排序并回傳陣列
    return sortBuckets(buckets);
}


/**
 * 創建桶
 * @param arr
 * @param bucketSize  單個桶的容量
 */
function createBuckets(arr: Array<number>, bucketSize: number):any[][] {
    let minNum = arr[0];
    let maxNum = arr[0];

    // 回圈查找最大值最小值
    for (let i = 1; i < arr.length; i++) {

        if (maxNum < arr[i]) {
            maxNum = arr[i];
        } else if (arr[i] < minNum) {
            minNum = arr[i];
        }

    }

    // 計算桶數
    const bucketCount = Math.floor((maxNum - minNum) / bucketSize) + 1;
    // 創建并初始化裝桶的陣列,這里就是一個二元陣列了
    const buckets = [];
    
    //這個for回圈不要使用fill替換
    for (let i = 0; i < bucketCount; i++) {
        buckets[i] = [];
    }

    for (let i = 0; i < arr.length; i++) {
        // 計算下標的程序其實是對資料進行了一次簡單的排序,然后桶就會呈現出有序性
        const index = Math.floor((arr[i] - minNum) / bucketSize)
        buckets[index].push(arr[i]);
    }

    return buckets;
}

/**
 * 對桶進行排序
 * @param buckets
 */
function sortBuckets(buckets: any[][]) {
    let result = [];
    for (let i = 0; i < buckets.length; i++) {
        let element = buckets[i];

        if(element !== null){
            insertSort(element)
            result.push(...element);
        }
    }

    return result;
}

let arr = [54,8,45,7, 1,2,45,9,8,452,35,754,127,6,21,124,454]
let sortArr = sortArray(arr)

// @ts-ignore
console.log(sortArr)

還是想強調一下，填充桶陣列的時候不能使用'fill'

標籤：其他

上一篇：vue專案中企業微信使用js-sdk時config和agentConfig配置

下一篇：Vue整理