javascriptよくある並べ替えアルゴリズムのまとめ

6377 ワード

javascriptよくある並べ替えアルゴリズムの総括アルゴリズムはプログラムの魂です.フロントエンドの開発環境では、並べ替えアルゴリズムはあまり使われていませんが、一般的な並べ替えアルゴリズムはやはりマスターすべきです.私はここでネットでよくある並べ替えアルゴリズムを整理しました.Javascriptが実現しました.後で調べるのに便利です.
並べ替え:
function merge(left, right){
     var result  = [],
         il      = 0,
         ir      = 0;
 
     while (il < left.length && ir < right.length){
         if (left[il] < right[ir]){
             result.push(left[il++]);
         } else {
             result.push(right[ir++]);
         }
     }
 
     return result.concat(left.slice(il)).concat(right.slice(ir));
 }
function mergeSort(items){
 
     //     :       2 
     if (items.length < 2) {
         return items;
     }
 
     var middle = Math.floor(items.length / 2),
         left   = items.slice(0, middle),
         right  = items.slice(middle);
 
     return merge(mergeSort(left), mergeSort(right));
 }
function mergeSort2(items){
 
     if (items.length < 2) {
         return items;
     }
 
     var middle = Math.floor(items.length / 2),
         left   = items.slice(0, middle),
         right  = items.slice(middle),
         params = merge(mergeSort(left), mergeSort(right));
     
     params.unshift(0, items.length);
     items.splice.apply(items, params);
     return items;
 }
並べ替えの挿入:
function insertionSort(items) {

    var len = items.length,    
        value,                    
        i,                        
        j;                         
    
    for (i=0; i < len; i++) {
        value = items[i];
        for (j=i-1; j > -1 && items[j] > value; j--) {
            items[j+1] = items[j];
        }
        items[j+1] = value;
    }
    return items;
}
並べ替えを選択:
function swap(items, firstIndex, secondIndex){
     var temp = items[firstIndex];
     items[firstIndex] = items[secondIndex];
     items[secondIndex] = temp;
 }
function selectionSort(items){
 
     var len = items.length,
         min;
 
     for (i=0; i < len; i++){
         min = i;
         for (j=i+1; j < len; j++){
             if (items[j] < items[min]){
                 min = j;
             }
         }
 
         if (i != min){
             swap(items, i, min);
         }
     }
 
     return items;
 }
泡の並べ替え:
function swap(items, firstIndex, secondIndex){
     var temp = items[firstIndex];
     items[firstIndex] = items[secondIndex];
     items[secondIndex] = temp;
 }
function bubbleSort(items){
 
     var len = items.length,
         i, j, stop;
 
     for (i=0; i < len; i++){
         for (j=0, stop=len-i; j < stop; j++){
             if (items[j] > items[j+1]){
                 swap(items, j, j+1);
             }
         }
     }
 
     return items;
 }
クイックソート:
var quickSort = function(arr) {
  if (arr.length <= 1) { return arr; }
  var pivotIndex = Math.floor(arr.length / 2);
  var pivot = arr.splice(pivotIndex, 1)[0];
  var left = [];
  var 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 binarySearch(items, value){
 
     var startIndex  = 0,
         stopIndex   = items.length - 1,
         middle      = Math.floor((stopIndex + startIndex)/2);
 
     while(items[middle] != value && startIndex < stopIndex){
 
         if (value < items[middle]){
             stopIndex = middle - 1;
         } else if (value > items[middle]){
             startIndex = middle + 1;
         }
 
         middle = Math.floor((stopIndex + startIndex)/2);
     }
 
     return (items[middle] != value) ? -1 : middle;
 }
ベースの並べ替え:
var countSort = function(array) {
   var i, z = 0, count = [],
   min = Math.min.apply({}, array),
   max = Math.max.apply({}, array),
   size = array.length;
   //        
   for (i = min; i <= max; i++) {
     count[i] = 0;
   }
   for (i=0; i < size; i++) {
     count[array[i]]++;
   }
  
   for (i = min; i <= max; i++) {
     while (count[i]-- > 0) {//     ,     ,  i  array
       array[z++] = i;
     }
   }
   return array;
 }
ヒルの並べ替え:
function shellSort(array) {
    var j, i, v, h=1, s=3, k,n = array.length;
    var result = "";
    var count = 0;
    while(h < n)
        h=s*h+1;
   
    while(h > 1) {
        h=(h-1)/s;
          for (k=0; k= 0 && array[j] > v)
                        array[j+h]=array[j];
                    else
                        break;
                array[j+h]=v;
                
            }
            count++;
            result += "
" + count + " :"; for (var n = 0; n < array.length; n++) { result += array[n] + ","; } } return result; }
組み合わせのソート:
var combSort = function(array){
   var gap = array.length;
   do{
     gap = gap * 10 / 13
     if(gap === 9 || gap === 10)
       gap = 11
     if(gap < 1){
       gap = 1
     }
     var swapped = false;
     for(var i=0;iarray[j]){
         var temp = array[i];
         array[i] = array[j];
         array[j] = temp;
         test(array)
         swapped = true
       }
     }
     if(gap == 1 && !swapped){
       break;
     }
   }while(1);
 }
カクテルの並べ替え:
var cocktailSort= function(array) {
  var top = array.length - 1, bottom = 0,flag = true,i, j;
  while (flag) {
    flag = false;
    //      ,              
    for (i = bottom; i < top; i++) {
      if (array[i] > array[i + 1]) {
        swap(array, i, i + 1);
        flag = true;
      }
    }
    top--;
    //     ,              
    for (j = top; j > bottom; j--) {
      if (array[j] < array[j - 1]) {
        swap(array, j, j - 1);
        flag = true;
      }
    }
    bottom++;
  }
}
 
var swap = function(array,a,b){
  var tmp = array[a];
  array[a] = array[b]
  array[b] = tmp;
}
回転:http://www.cnblogs.com/chenguangyin/archive/2012/11/19/2777757.html