1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75
| class HeapSort { less( heap=[], i=0, j=0 ){ return heap[i] < heap[j] } swop( heap=[], i=0, j=0 ){ [ heap[i], heap[j] ] = [ heap[j], heap[i] ] } createHeap( source=[], heap=[] ){ heap.push( "", ...source ) for( let i = Math.floor( source.length / 2 ); i > 0; i -- ){ this.sink( heap, i, heap.length-1 ) } }
sink( heap=[], target=0, range=0 ){ while( 2*target <= range ){ let max if( 2*target+1 <= range ){ if( this.less( heap, 2*target, 2*target+1 ) ){ max = 2*target+1 } else { max = 2*target } } else { max = 2*target } if( !this.less( heap, target, max ) ){ break } this.swop( heap, target, max ) target = max } } sort( source=[] ){ let newHeap = [] this.createHeap( source, newHeap ) console.log( "变换后的堆:", newHeap ) let n = newHeap.length - 1 while( n > 1 ){ this.swop( newHeap, 1, n ) n -- this.sink( newHeap, 1, n ) } console.log( "交换后的堆:", newHeap ) newHeap.shift() source.length = 0 source.push( ...newHeap ) } }
let sourceArr = [ "S","O","R","T","E","X","A","M","P","L","E" ]
let heapSort = new HeapSort() heapSort.sort( sourceArr )
console.log( sourceArr )
|