经典排序算法之js实现

2013 - 3 - 31 作者 : Jimco 分类 : 技巧资源

    在博客园看到一篇关于几种排序算法的介绍,图文并茂,深入浅出,几乎给出了每一步的状态,是至今看过的最有助于理解算法的文章!点击传送

    这边给出几种算法的 js 实现,大都是网上收集而来,建议初学者对照博客园的算法介绍来看代码,会有更深刻的认识。如果有更好的实现,请一定告诉我,本文将持续更新...

Array.prototype.swap = function(i, j){
  var temp = this[i];
  this[i] = this[j];
  this[j] = temp;
}

/* 快速排序 */
function quickSort(arr){
  if(arr.length <= 1) return arr;

  var pivotIndex = Math.floor(arr.length/2)
    , pivot = arr.splice(pivotIndex, 1)[0]
    , left = []
    , right = [];

  for(var i = 0; i < arr.length; i++){
    if(arr[i] < pivot){
      left.push(arr[i]);
    }else{
      right.push(arr[i]);
    }
  }
  return quickSort(left).concat([pivot], quickSort(right));
}

/* 插入排序 */
function insertSort(arr){
  var len = arr.length
    , i = 1
    , j, key;

  for(; i < len; i++){
    j = i;
    key = arr[j];  
    while(--j > -1){ 
      if(arr[j] > key){  
        arr[j + 1] = arr[j];  
      }else{
        break;  
      }  
    }  
    arr[j + 1] = key;  
  }  
  return arr;  
}

/* 冒泡排序 */
function bubbleSort(arr){
  var len = arr.length
    , i, j;

  for(i = len - 1; i >= 1; i--){  
    for(j = 0; j <= i - 1; j++){  
      if(arr[j] > arr[j + 1]){  
        d = arr[j + 1];
        arr[j + 1] = arr[j];
        arr[j] = d;
      }
    }
  }
  return arr;  
}

/* 堆排序 */
function heapSort(arr){
  for(var i = 1; i < arr.length; ++i){
    for (var j = i, k = (j - 1) >> 1; k >= 0; j = k, k = (k - 1) >> 1){
      if(arr[k] >= arr[j]) break;
      arr.swap(j, k);
    }
  }
  for(var i = arr.length - 1; i > 0; --i){
    arr.swap(0, i);
    for(var j = 0, k = (j + 1) << 1; k <= i; j = k, k = (k + 1) << 1){
      if(k == i || arr[k] < arr[k - 1]) --k;
      if(arr[k] <= arr[j]) break;
      arr.swap(j, k);
    }
  }
  return arr;
}

/* 希尔排序 */
function ShellSort(arr){ //插入排序->希儿排序
  var st = new Date();
  var increment = arr.length;
  do {
   increment = (increment/3|0) + 1;
   arr = ShellPass(arr, increment);
  }
  while (increment > 1)

  status = (new Date() - st) + ' ms';
  return arr;
}

function ShellPass(arr, d){ //希儿排序分段执行函数
  var temp, j;
  for(var i = d; i < arr.length; i++) {
    if((arr[i]) < (arr[i-d])) {
      temp = arr[i]; j = i - d;
      do {
        arr[j+d] = arr[j];
        j = j-d;
      }
      while (j >- 1 && (temp) < (arr[j]));
      arr[j + d] = temp;
    }
  }
  return arr;
}

12557 人围观 / 10 条评论 ↓快速评论↓

  • 博客不错,学习了,赞

    host 2013-08-20 15:35 回复

  • 博客不错,学习了,赞

    环法 2013-06-20 14:04 回复

  • 能弱弱的问下 能求主题不

    李可迪博客 2013-04-06 10:30 回复

    • @李可迪博客:emlog官网、论坛都可以下载。

      Jimco 2013-04-06 22:57 回复

  • 好有深度的内容,让我受益匪浅

    hostgator 2013-04-03 15:22 回复

(必须)

(必须,保密)

阿狸1 阿狸2 阿狸3 阿狸4 阿狸5 阿狸6 阿狸7 阿狸8 阿狸9 阿狸10 阿狸11 阿狸12 阿狸13 阿狸14 阿狸15 阿狸16 阿狸17 阿狸18

Powered by Jimco

©2013 前端那些事儿 Designed by Jimco

About me|意见反馈