JS实现堆排序

原理

堆排序原理

实现

(function(){
  'use strict';
  var heapAdjust=(function f(arr,i){
    var len=arr.length,
        j=i*2;
    if(i>0 && j<=len){
      if(isNaN(arr[j-1]) || isNaN(arr[i-1])){
        return 'isNaN';
      }

      if(j+1<=len){
        if(isNaN(arr[j])){
          return 'isNaN';
        }

        if(arr[j-1]<=arr[j]){
          if(arr[i-1]>arr[j-1]){
            [arr[i-1],arr[j-1]]=[arr[j-1],arr[i-1]];
            f(arr,j);
          }
        }else{
          if(arr[i-1]>arr[j]){
            [arr[i-1],arr[j]]=[arr[j],arr[i-1]];
            f(arr,j+1);
          }
        }
      }else{
        if(arr[i-1]>arr[j-1]){
          [arr[i-1],arr[j-1]]=[arr[j-1],arr[i-1]];
          f(arr,j);
        }
      }
    }
    return arr;
  });

  function heapSort(arr){
    var temp=[],
        a=arr,
        len=arr.length;
    if(!Array.isArray(arr)){
      console.log('this is not a array!');
      return arr;
    }

    for(var k=0;k<len;k++){
      for(var x=Math.floor(a.length/2);x>0;x--){
        a=heapAdjust(a,x);
        if(a==='isNaN'){
          console.log('this is not a pure numeric array!');
          return arr;
        }
      }
      temp.push(a[0]);
      a=a.slice(1,len);
    }
    return temp;
  }

  var array1='1111';
  var array2=[3,2,53,67765,3243,44,'aaaa'];
  var array3=[3,2,53,67765,3243,44,2,3,567,342,6785,976,643,2342,23423,4564,678,23325,854,2324,345435,457];
  console.log(heapSort(array1));
  console.log(heapSort(array2));
  console.log(heapSort(array3));
})();

说明

• 堆排序对大文件很有效
• 堆排序是不稳定排序