JavaScript数据结构24—简单的排序算法

简单的排序算法包括了

• 冒泡
• 简单选择
• 直接插入

//排序算法
//冒泡
Array.prototype.bubbleSort = function() {
  var flag = true;
  for (var i = 0; i < this.length-1&&flag; i++) {
    flag = false;
    for (var j = this.length-1; j >= i; j--) {
      if(this[i]>this[j+1]){
        var temp = this[i];
        this[i] = this[j+1];
        this[j+1] = temp;
        flag = true;
      }
    }
  }
  console.info('排序后的序列:\n'+this);
};
//简单选择
Array.prototype.selectSort = function(){
  var min;
  for (var i = 0; i < this.length-1; i++) {
    min = i;
    for (var j = i+1; j < this.length; j++) {
      if(this[min]>this[j]){
        min = j;
      }
    }
    if(i!=min){
      var temp = this[i];
      this[i] = this[min];
      this[min] = temp;
    }
  }
  console.info('排序后的序列:\n'+this);
}
//直接插入
Array.prototype.insertSort = function(){
  for (var i = 1; i<this.length ; i++) {
    if(this[i]<this[i-1]){
      var temp = this[i];
      for (var j = i-1; this[j]>temp; j--) {
        this[j+1] = this[j];
      }
      this[j+1] = temp;
    }
  }
  console.info('排序后的序列:\n'+this);
}
function randArray(max,size){
  var a = [];
  for (var i = 0; i < size; i++) {
    a[i] = parseInt(Math.random()*max);
  }
  console.info('(随机情况)生成了序列:\n'+a);
  return a;
}
function bestArray(max,size){
  var a = [];
  var q = 0;
  for (var i = 0; i < size; i++) {
    q += parseInt(Math.random()*max);
    a[i] = q;
  }
  console.info('(最好情况)生成了序列:\n'+a);
  return a;
}
function worstArray(max,size){
  var a = [];
  var q = max;
  for (var i = 0; i < size; i++) {
    q -= parseInt(Math.random()*max);
    a[i] = q;
  }
  console.info('(最坏情况)生成了序列:\n'+a);
  return a;
}
var array1 = randArray(5000,10);
array1.bubbleSort();
var array2 = worstArray(5000,10);
array2.bubbleSort();
var array3 = bestArray(5000,10);
array3.bubbleSort();
var array4 = randArray(5000,10);
array4.selectSort();
var array5 = bestArray(5000,10);
array5.selectSort();
var array6 = worstArray(5000,10);
array6.selectSort();
var array7 = randArray(5000,10);
array7.insertSort();
var array8 = bestArray(5000,10);
array8.insertSort();
var array9 = worstArray(5000,10);
array9.insertSort();

output

(随机情况)生成了序列:
2099,3712,3015,564,160,1963,4359,756,4732,2394
排序后的序列:
160,564,756,1963,2099,2394,4359,3015,4732,3712
(最坏情况)生成了序列:
2266,-915,-1239,-4037,-4885,-5704,-6083,-6644,-8599,-12524
排序后的序列:
-12524,-8599,-6644,-6083,-5704,-4885,-4037,-1239,-915,2266
(最好情况)生成了序列:
829,2664,5136,5983,7477,9677,13823,14841,15536,17049
排序后的序列:
829,2664,5136,5983,7477,9677,13823,14841,15536,17049
(随机情况)生成了序列:
3397,3270,838,732,4196,830,503,2474,3900,1809
排序后的序列:
503,732,830,838,1809,2474,3270,3397,3900,4196
(最好情况)生成了序列:
4619,8459,9709,10888,12046,13674,14885,18939,19094,21715
排序后的序列:
4619,8459,9709,10888,12046,13674,14885,18939,19094,21715
(最坏情况)生成了序列:
4659,2310,-586,-2784,-6562,-6989,-9984,-13033,-16484,-20037
排序后的序列:
-20037,-16484,-13033,-9984,-6989,-6562,-2784,-586,2310,4659
(随机情况)生成了序列:
2497,1520,2311,4395,4348,2938,1978,4191,1546,4961
排序后的序列:
1520,1546,1978,2311,2497,2938,4191,4348,4395,4961
(最好情况)生成了序列:
2535,6264,7224,9153,12233,15759,17180,19071,22544,23599
排序后的序列:
2535,6264,7224,9153,12233,15759,17180,19071,22544,23599
(最坏情况)生成了序列:
1491,-2131,-3944,-6593,-10771,-14487,-15923,-17742,-19641,-24606
排序后的序列:
-24606,-19641,-17742,-15923,-14487,-10771,-6593,-3944,-2131,1491
[Finished in 0.1s]