Javascript 數組自定義排序，并擷取排序後的儲存原索引的同序數組(堆排序實作)...

比如數組A：

[

0: 5,

1: 2,

2: 4,

3: 3,

4: 1

]

排序後的結果為：[1, 2, 3, 4, 5]，但是有時候會有需求想要保留排序前的位置到一個同位數組裡，如前例則為：[4, 1, 3, 2, 0]，是以就利用堆排序寫了一個單獨的數組排序過程加以實作。

代碼如下：

function arrayKeys(arr) {
        var i    = 0, 
            len  = arr.length,
            keys = [];
        while (i < len) {
            keys.push(i++);
        }
        return keys;
    }　　 
// 判斷變量是否為數組
    function isArray(arr) {
        return ({}).toString.call(arr).match(/^\[[^\s]+\s*([^\s]+)\]$/)[1] == 'Array';
    }
// 堆排序
    function heapSort(arr, keys, order) {
        if (!isArray(arr) || !isArray(keys)) return ;
        var order = (order + '').toLowerCase() == 'desc' ? order : 'asc';
        // 交換位置
        function changePos(arr, cur, left) {
            var tmp;
            tmp       = arr[cur];
            arr[cur]  = arr[left];
            arr[left] = tmp;
        }
        // 構造二叉堆
        function heap(arr, start, end, isMax) {
            var isMax = isMax == undefined ? true : isMax,  // 是否最大堆，否為最小堆
                cur   = start,        // 目前節點的位置
                left  = 2 * cur + 1;  // 左孩子的位置
            for (; left <= end; cur = left, left = 2 * left + 1) {
                // left是左孩子，left + 1是右孩子
                if (left < end && ((isMax && arr[left] < arr[left + 1]) || (!isMax && arr[left] > arr[left + 1]))) {
                    left++;  // 左右子節點中取較大/小者
                }
                if ((isMax && arr[cur] >= arr[left]) || (!isMax && arr[cur] <= arr[left])) {
                    break;
                } else {
                    // 原index跟随排序同步進行
                    changePos(keys, cur, left);
                    changePos(arr, cur, left);
                }
            }
        }
        return (function () {
            // 從(n/2-1) --> 0逐次周遊。周遊之後，得到的數組實際上是一個二叉堆
            for (var len = arr.length, i = Math.floor(len / 2) - 1; i >= 0; i--) {
                heap(arr, i, len - 1, order == 'asc');
            }
            // 從最後一個元素開始對序列進行調整，不斷的縮小調整的範圍直到第一個元素
            for (i = len - 1; i > 0; i--) {
                changePos(keys, 0, i);
                changePos(arr, 0, i);
                // 調整arr[0...i - 1]，使得arr[0...i - 1]仍然是一個最大/小堆
                // 即，保證arr[i - 1]是arr[0...i - 1]中的最大/小值
                heap(arr, 0, i - 1, order == 'asc');
            }
        })();
    }
    
// 測試
    var aa = [5, 2, 8, 9, 1, 3, 4, 7, 6];
    var kk = arrayKeys(aa);  // 原索引數組
    heapSort(aa, kk, 'asc');
    console.log(aa);  // 排序後：[1, 2, 3, 4, 5, 6, 7, 8, 9]
    console.log(kk);  // 原索引：[4, 1, 5, 6, 0, 8, 7, 2, 3]

當然，也可以在確定安全的前提下把該方法寫入Array.prototype.heapSort，這樣就可以用數組直接調用了，代碼略微修改一下即可，如下：

Array.prototype.heapSort = function (keys, order) {
        var keys  = ({}).toString.call(keys) == '[object Array]' ? keys : [],
            order = (order + '').toLowerCase() == 'desc' ? order : 'asc';
        // 交換位置
        function changePos(arr, cur, left) {
            var tmp;
            tmp       = arr[cur];
            arr[cur]  = arr[left];
            arr[left] = tmp;
        }
        // 構造二叉堆
        function heap(arr, start, end, isMax) {
            var isMax = isMax == undefined ? true : isMax,  // 是否最大堆，否為最小堆
                cur   = start,        // 目前節點的位置
                left  = 2 * cur + 1;  // 左孩子的位置
            for (; left <= end; cur = left, left = 2 * left + 1) {
                // left是左孩子，left + 1是右孩子
                if (left < end && ((isMax && arr[left] < arr[left + 1]) || (!isMax && arr[left] > arr[left + 1]))) {
                    left++;  // 左右子節點中取較大/小者
                }
                if ((isMax && arr[cur] >= arr[left]) || (!isMax && arr[cur] <= arr[left])) {
                    break;
                } else {
                    // 原index跟随排序同步進行
                    changePos(keys, cur, left);
                    changePos(arr, cur, left);
                }
            }
        }
        return (function (arr) {
            // 從(n/2-1) --> 0逐次周遊。周遊之後，得到的數組實際上是一個二叉堆
            for (var len = arr.length, i = Math.floor(len / 2) - 1; i >= 0; i--) {
                heap(arr, i, len - 1, order == 'asc');
            }
            // 從最後一個元素開始對序列進行調整，不斷的縮小調整的範圍直到第一個元素
            for (i = len - 1; i > 0; i--) {
                changePos(keys, 0, i);
                changePos(arr, 0, i);
                // 調整arr[0...i - 1]，使得arr[0...i - 1]仍然是一個最大/小堆
                // 即，保證arr[i - 1]是arr[0...i - 1]中的最大/小值
                heap(arr, 0, i - 1, order == 'asc');
            }
        })(this);
    };

經過測試發現，在數組沒有相同元素的情況下，原索引的序列同排序後的數組是比對的，但是在有相同元素的情況下，序列就比較亂，這是因為堆排序本來就不是一個穩定的排序，排序後所有元素的位置會被打亂。比如：數組[5, 5, 5, 5, 5]，因為元素都一樣，是以排序過程中應該是隻做了比較，卻并沒有交換原來位置的，但實際得到的索引卻是：[1, 2, 3, 4, 0]，這也很好了解，因為堆排序假如是最大堆的話，根節點是要被交換到末尾的，而很明顯元素首位的5即是根節點，是以得到了前面那個颠倒的序列。

這樣一來就跟初衷有點不符了，是以我又重新模拟了一個穩定排序的算法----歸并排序，效果已經達到了預期。

代碼如下：

// 歸并排序(過程：從下向上)
    function mergeSort(arr, key, order) {
        if (!isArray(arr)) return [];
        var key = isArray(key) ? key : [];
        // 對數組arr做若幹次合并：數組arr的總長度為len，将它分為若幹個長度為gap的子數組；
        // 将"每2個相鄰的子數組" 進行合并排序。
        // len = 數組的長度，gap = 子數組的長度
        function mergeGroups(arr, len, gap) {
            // 對arr[0..len)做一趟歸并排序
            // 将"每2個相鄰的子數組"進行合并排序
            for (var i = 0; i + 2 * gap - 1 < len; i += gap * 2) {
                merge(arr, i, i + gap - 1, i + 2 * gap - 1);  // 歸并長度為len的兩個相鄰子數組
            }
            // 注意：
            // 若i ≤ len - 1且i + gap - 1 ≥ len - 1時，則剩餘一個子數組輪空，無須歸并
            // 若i + gap - 1 < len - 1，則剩餘一個子數組沒有配對
            // 将該子數組合并到已排序的數組中
            if (i + gap - 1 < len - 1) {                              // 尚有兩個子檔案，其中後一個長度小于len - 1
                merge(arr, i, i + gap - 1, len - 1);           // 歸并最後兩個子數組
            }        
        }
        // 核心排序過程
        function merge(arr, start, mid, end) {
            var i = start;      // 第1個有序區的索引，周遊區間是：arr數組中的[start..mid]
            var j = mid + 1;    // 第2個有序區的索引，周遊區間是：arr數組中的[mid + 1..end]
            var aTmp  = [];     // 彙總2個有序區臨時數組
            var kTmp  = [];
            var isAsc = (order + '').toLowerCase() !== 'desc';
            /* 排序過程開始 */
            while (i <= mid && j <= end) {   // 周遊2個有序區，當該while循環終止時，2個有序區必然有1個已經周遊并排序完畢
                if ((!isAsc && arr[i] <= arr[j]) || (isAsc && arr[i] >= arr[j])) {  // 并逐個從2個有序區分别取1個數進行比較，将較小的數存到臨時數組aTmp中
                    aTmp.push(arr[i]);
                    kTmp.push(key[i++]);
                } else {
                    aTmp.push(arr[j]);
                    kTmp.push(key[j++]);
                }
            }
            // 将剩餘有序區的剩餘元素添加到臨時數組aTmp中
            while (i <= mid) {
                aTmp.push(arr[i]);
                kTmp.push(key[i++]);
            }
            while (j <= end) {
                aTmp.push(arr[j]);
                kTmp.push(key[j++]);
            }
　　　　　　  /*排序過程結束*/
            var len = aTmp.length, k;
            // 此時，aTmp數組是經過排序後的有序數列，然後将其重新整合到數組arr中
            for (k = 0; k < len; k++) {  
                arr[start + k] = aTmp[k];
                key[start + k] = kTmp[k];
            }
        }
        // 歸并排序(從下往上)
        return (function (arr) {
            // 采用自底向上的方法，對arr[0..len)進行二路歸并排序
            var len = arr.length;
            if (len <= 0) return arr;
            for (var i = 1; i < len; i *= 2) {   // 共log2(len - 1)趟歸并
                mergeGroups(arr, len, i);        // 有序段長度 ≥ len時終止
            }
        })(arr);
    }

    // 數組原型鍊方法
    Array.prototype.mergeSort = function (key, order) {
        var key = ({}).toString.call(key) == '[object Array]' ? key : [];
        function mergeGroups(arr, len, gap) {
            for (var i = 0; i + 2 * gap - 1 < len; i += gap * 2) {
                merge(arr, i, i + gap - 1, i + 2 * gap - 1);
            }
            if (i + gap - 1 < len - 1) {
                merge(arr, i, i + gap - 1, len - 1);
            }        
        }
        // 核心排序過程
        function merge(arr, start, mid, end) {
            var i = start; 
            var j = mid + 1;
            var aTmp = [];
            var kTmp = [];
            var isAsc = (order + '').toLowerCase() !== 'desc';
            /* 排序過程開始 */
            while (i <= mid && j <= end) { 
                if ((isAsc && arr[i] <= arr[j]) || (!isAsc && arr[i] >= arr[j])) {
                    aTmp.push(arr[i]);
                    kTmp.push(key[i++]);
                } else {
                    aTmp.push(arr[j]);
                    kTmp.push(key[j++]);
                }
            }
            while (i <= mid) {
                aTmp.push(arr[i]);
                kTmp.push(key[i++]);
            }
            while (j <= end) {
                aTmp.push(arr[j]);
                kTmp.push(key[j++]);
            }
　　　　　　　/*排序過程結束*/
            var len = aTmp.length, k;
            for (k = 0; k < len; k++) {  
                arr[start + k] = aTmp[k];
                key[start + k] = kTmp[k];
            }
        }
        // 歸并排序(從下往上)
        return (function (arr) {
            var len = arr.length;
            if (len <= 0) return arr;
            for (var i = 1; i < len; i *= 2) {
                mergeGroups(arr, len, i);
            }
            return arr;
        })(this);
    };

    // 測試
    var arr1 = [2, 2, 2, 2, 2, 2, 2, 2];
    var arr2 = [5, 2, 7, 1, 2, 6, 6, 8];
var key1 = arrayKeys(arr1);
    var key2 = arrayKeys(arr2);
    console.log(arr1.mergeSort(key1));  // [2, 2, 2, 2, 2, 2, 2, 2]
    console.log(key1);                  // [0, 1, 2, 3, 4, 5, 6, 7]
    console.log(arr2.mergeSort(key2));  // [1, 2, 2, 5, 6, 6, 7, 8]
    console.log(key2);                  // [3, 1, 4, 0, 5, 6, 2, 7]

轉載于:https://www.cnblogs.com/go-jzg/p/5812021.html

Javascript 數組自定義排序，并擷取排序後的儲存原索引的同序數組(堆排序實作)...

繼續閱讀

JavaScript自學筆記【4】函數的聲明與調用目錄二、函數的聲明三、函數的調用

請求逾時VUE axios重新再次請求

nodejs微信開發---授權登入+擷取使用者資訊微信網頁授權

debian9更新4.9.0核心到4.19.2核心過程

Javascript建構Bingo卡片遊戲

JavaScript的那些坑之事件代理事件代理事件階段

javascript的for (var i in data)慎用javascript中的for (var i in data)謹慎用

PAT 1089 Insert or Merge[難]

tab滑鼠經過菜單切換

vue （vue2.0）使用總結(從大體結構總結)

vue搭建過程及出現問題

/\B(?=(?:\d{3})+$)/g 一條令人費解的正規表達式

适用于JavaScript的ECMAScript 2020規範向前發展

JS生成uuid的四種方法

layui多任務上傳添加進度條