javascript實作堆排序

堆排序

堆是具有以下性質的完全二叉樹：每個結點的值都大于或等于其左右孩子結點的值，稱為大頂堆；或者每個結點的值都小于或等于其左右孩子結點的值，稱為小頂堆。如下圖：

function heapSort(arr) {

	  for(var i=Math.floor(arr.length/2)-1;i>=0;i--){         //從上而下生成大頂堆
	   	   	  heapAdjust(arr,i,arr.length);
	   }

	  for(var j=arr.length-1;j>0;j--){
		          swap(arr,0,j);                           //交換頂推元素和末尾元素，使最大元素換到隊尾
		          heapAdjust(arr,0,j);                      //重新調整堆
	  }

	return arr;
     }

	  function heapAdjust(arr,i,len) {               //自上而下
	          var temp=arr[i];
	          var largest=i;
	          var left=2*i+1;
	          var right=2*i+2;
	          if(left<len && arr[left]>arr[largest]){
	          		larget=left;
	          }

	          if(right<len && arr[right]>arr[largest]){
	          	largest=right;
	          }
	          if(largest!=i){
	          	swap(arr,larget,i);
	          	heapAdjust(arr,largest,len);	          	
	          }
	   }