首页 > 代码库 > Javascript 数组自定义排序，并获取排序后的保存原索引的同位数组(堆排序实现)
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 arr = this, 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 () { // 从(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‘); } }(); };
Javascript 数组自定义排序，并获取排序后的保存原索引的同位数组(堆排序实现)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。