排序算法速度测试（插入排序、二分法插入、选择排序、快速排序、堆排序）js实现

摘要：公共函数库用于取出随机排列的数字原数组给原数组赋值排序算法插入排序时间复杂度二分法插入排序选择排序快速排序一堆排序测试用例插入排序时间测试二分法插入排序时间测试选择排序时间测试快速排序时间测试一堆

公共函数库（用于取出随机排列的数字）

module.exports={
    randomIntegerArray:function(count){
        var originalArray=new Array;//原数组 
        //给原数组originalArray赋值 
        for (var i=0;i
排序算法

//插入排序 时间复杂度O(n^2)
function insertionSort(array){
  if(Object.prototype.toString.call(array).slice(8,-1)!="Array") {
      throw new Error("array is not a Array")
      return;
  };
  for (var i = 0,l=array.length; i < l; i++) {
      var insert=array[i];
      var j=i-1;
      while (j>=0&&array[j]>insert) {
          array[j+1]=array[j];
          j--;
      }
      array[j+1]=insert;
  }
  return array;
}
//二分法插入排序
function dichotomyInsertSort(array){
    if(Object.prototype.toString.call(array).slice(8,-1)!="Array"){
      throw new Error("array is not a Array")
         return;
    }
    for (var i = 0; i < array.length; i++) {
        var key=array[i],left=0,right=i-1;
        while(left<=right){
            var mid=parseInt((left+right)/2);
            if(key=left; j--) {
            array[j+1]=array[j];
        }
        array[left]=key;

    }
    return array;
}

//选择排序
function selectionSort(array){
    if(Object.prototype.toString.call(array).slice(8,-1)!="Array"){
          throw new Error("array is not a Array")
             return;
        }
    for (var i = 0; i < array.length-1; i++) {
            var min=array[i];
            for(var j=i+1;jarray[j]){
                    var temp=array[j];
                    array[j]=min;
                    min=temp;
                }
            }
            array[i]=min;
        }
        return array;    
}
//快速排序 一
function quickSort(array,left,right){
    if(Object.prototype.toString.call(array).slice(8,-1)!="Array"){
      throw new Error("array is not a Array")
         return;
    }
    if(left>=right) return;
    var j=left-1,key=array[right],temp;
    for (var i = left; i <=right; i++) {
         if(array[i]<=key&&i!=j){
             j++;
            temp=array[j];
            array[j]=array[i];
            array[i]=temp;
         }
     }
     quickSort(array,left,j-1);
     quickSort(array,j+1,right);
}
//堆排序
/**
         0
    1        2
  3    4    5   6
 7 8  9 10
*/
var heapSort =(function(){
    function heapAjust(array,len){
      var mid=Math.floor(len/2);
      for (var i = mid; i >=0; i--) {
            var l=2*i+1,r=2*i+2,largest=i;
          if(larray[largest]) largest=l;
          if(rarray[largest]) largest=r;
          if(largest!=i){
            swap(array,i,largest)
          }
       }        
        
    }
    function swap(array,i,j){
            var temp=array[i];
            array[i]=array[j];
            array[j]=temp;
    }
   return function heap(array){
      if(Object.prototype.toString.call(array).slice(8,-1)!="Array"){
        console.error("array is not a Array");
          return;
      }
      var len=array.length;
      for (var i = 0; i < len; i++) {
          heapAjust(array,len-i);
          swap(array,0,len-1-i);
      }
   }
})()


module.exports={
    insertionSort:insertionSort,
    dichotomyInsertSort:dichotomyInsertSort,
    selectionSort:selectionSort,
    quickSort:quickSort,
    heapSort:heapSort
}
测试用例
var common=require("./common.js");

var sort=require("./sort.js")
var l=100000;
var a=common.randomIntegerArray(l),b;
var a1=common.randomIntegerArray(l),b1;
var a2=common.randomIntegerArray(l),b2;
var a3=common.randomIntegerArray(l),b3;
var a4=common.randomIntegerArray(l),b4;
/**************
*插入排序时间测试
***************/
console.time("insert");

 // console.log(a);
 b=sort.insertionSort(a);
 // console.log(b);
console.timeEnd("insert");

/**************
*二分法插入排序时间测试
***************/
console.time("twoinsert");

// console.log(a1);
 b1=sort.dichotomyInsertSort(a);
// console.log(b1);
console.timeEnd("twoinsert");

/**************
*选择排序时间测试
***************/
console.time("selectionSort");

// console.log(a2);
 b2=sort.selectionSort(a2);
// console.log(b2);
console.timeEnd("selectionSort");

/**************
*快速排序时间测试一
***************/
console.time("quickSort1");
// console.log(a3);
 sort.quickSort(a3,0,a3.length-1);
 // console.log(a3);
console.timeEnd("quickSort1");

/**************
*堆排序时间测试一
***************/
console.time("heapSort");
// console.log(a4);
  debugger;
  sort.heapSort(a4);
// console.log(a4);
console.timeEnd("heapSort");
实验结构
100000个随机数字的时候
insert: 7943ms
twoinsert: 96807ms
selectionSort: 21013ms
quickSort1: 56ms
heapSort: 16309ms
github源码位置：地址https://github.com/ddcouples/...