heap算法
function findParentNodeKey (key) { let parentKey = 1 if(key===1){ return parentKey }else if(key%2===0){ parentKey = key/2 return parentKey }else if(key%2!==0){ parentKey = (key-1)/2 return parentKey } } function swap(sortList,start,end){ let temp = sortList[start] sortList[start]=sortList[end] sortList[end]=temp } let heapArr = [4,1,3,2,16,9,10,14,8,7] function getHeap (sortArr) { for(let i = sortArr.length;i>1;i--){ let currNodeVal = sortArr[i-1] let parentNodeKey = findParentNodeKey (i) let parentNodeVal= sortArr[parentNodeKey-1] if(currNodeVal>parentNodeVal){ swap(sortArr,i-1,parentNodeKey-1) if(sortArr[i*2]){ if(sortArr[i*2]>sortArr[i-1]){ swap(sortArr,i-1,i*2) } } if(sortArr[i*2-1]){ if(sortArr[i*2-1]>sortArr[i-1]){ swap(sortArr,i-1,i*2-1) } } } } return sortArr } let arr = getHeap (heapArr) console.log(arr) function heapSort(arr){ let len = arr.length for(let i = arr.length-1;i>=0;i--){ swap(arr,0,i) len-- let currIndex = 1 let swapFlag = true while(currIndex*2<=len&&swapFlag){ let curNode = arr[currIndex-1] let left = arr[currIndex*2-1] let right = arr[currIndex*2]&&currIndex*2+1<=len?arr[currIndex*2]:-Infinity if(left>right){ if(left>curNode){ swap(arr,currIndex-1,currIndex*2-1) currIndex = currIndex*2 }else{ swapFlag = false } }else{ if(right>curNode){ swap(arr,currIndex-1,currIndex*2) currIndex = currIndex*2+1 }else{ swapFlag = false } } } } return arr } console.log(heapSort(arr))