排序算法

• 冒泡排序：相邻量元素两两对比，进行元素交换

function bubbleSort(arr){
        var len=arr.length;
        for(var i=0;i<len;i++){
            for(var j=0;j<len-1-i;j++){
                if(arr[j]>arr[i]){
                    var temp=arr[j+1]
                    arr[j+1]=arr[j]
                    arr[j]=temp
                }
            }
        }
    }

• 选择排序：选择排序原理：每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完

function selectionSort(arr){
        var len=arr.length
        var minIndex,temp
        for(var i=0;i<len-1;i++){
            minIndex=i;
            for(var j=i+1;j<len;j++){
                if(arr[j]<arr[minIndex]){
                    
                    minIndex=j
                }   
            }
            temp=arr[i]
            arr[i]=arr[minIndex]
            arr[minIndex]=temp
        }
        return arr
    }

• 插入排序原理：要把排序的数组分成两部分，第一部分包含了这个数组的所有元素，但将最后一个元素除外，而第二部分就只包含这一个元素。在第一部分排序完成后，再将这个最后元素插入到已排好序的第一部分中。

function sort(elements){
  //假设第0个元素是一个有序的数列，第1个以后的是无序的序列，
  //所以从第1个元素开始将无序数列的元素插入到有序数列中
  for(var i = 1; i < elements.length; i++){
    //升序
    if(elements[i] < elements[i-1]){
      //取出无序数列中的第i个作为被插入元素
      var guard = elements[i];
      //记住有序数列的最后一个位置，并且将有序数列位置扩大一个
      var j = i - 1;
      elements[i] = elements[j];
      
      //比大小，找到被插入元素所在的位置
      while(j >= 0 && guard < elements[j]){
        elements[j+1] = elements[j];
        j--;
      }

      //插入
      elements[j+1] = guard;
    }
  }
}

var elements = [10, 9, 8, 7, 6, 5];
console.log('before: ' + elements);
sort(elements);
console.log(' after: ' + elements);

• 希尔排序原理：先将整个待排元素序列分割成若干个子序列分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序时，再对全体元素进行一次插入排序。因为直接插入排序在元素基本有序的情况下，效率是很高的

function shellSort(arr){
        var len=arr.length;
        var gap=Math.floor(len/2)
        while(gap!==0){
            for(var i=gap;i<len;i++){
                var temp=arr[i]
                var j;
                for(var j=i-gap;j>=0&&temp<arr[j];j-=gap){
                    arr[j+gap]=arr[j]
                }
                arr[j+gap]=temp
            }
            gap=Math.floor(gap/2)
        }
        return arr
    }

• 归并排序原理：其基本思想是分治策略，先进行划分，然后再进行合并
  假设要对数组进行归并排序，步骤是：
  1.现将C划分Wie两个数组A和B
  2.再分别对数组A、B重复步骤1的操作，逐步划分，直到不能再划分位置（每个子数组只剩下一个元素），这样划分的过程就结束了
  如： [12 20 30 21 15 33 26 19 40 25]
  划分为: [12 20 30 21 15] [33 26 19 40 25]
  [12 20] [30 21 15] [33 26] [19 40 25]
  [12] [20] [30] [21 15] [33] [26] [19] [40 25]
  [12] [20] [30] [21] [15] [33] [26] [19] [40] [25]
  3.然后从下层往上册更不断合并数组， 每一层合并相邻的两个子数组，合并的过程是每次从待合并的两个子数组中选取一个最小的元素，然后把这个元素放到合并后的数组中，不断重复知道把两个子数组的元素放到合并后的数组为止
  4.依次类推，知道合并到最上层结束

   function merge(left, right) {  
    var result = [];  
    while(left.length > 0 && right.length > 0) {  
       if(left[0] < right[0]) {  
           result.push(left.shift());  
       }  
       else {  
           result.push(right.shift());  
       }  
   }  
   /* 当左右数组长度不等.将比较完后剩下的数组项链接起来即可 */  
   return result.concat(left).concat(right);  
}  
    function mergeSort(arr){  
        if(arr.length==1) {return arr};  
        var mid=Math.floor(arr.length/2);  
        var left_arr=arr.slice(0,mid),right_arr=arr.slice(mid);  
        return merge(mergeSort(left_arr),mergeSort(right_arr));  
    }  
  
    var arr=[12,20,30,21,15,33,26,19,40,25];  
    console.log(mergeSort(arr));  

• 堆排序原理
  堆排序分为两个过程：

1.建堆。

堆实质上是完全二叉树，必须满足：树中任一非叶子结点的关键字均不大于（或不小于）其左右孩子（若存在）结点的关键字。

堆分为：大根堆和小根堆，升序排序采用大根堆，降序排序采用小根堆。

如果是大根堆，则通过调整函数将值最大的节点调整至堆根。

2.将堆根保存于尾部，并对剩余序列调用调整函数，调整完成后，再将最大跟保存于尾部-1（-1，-2，...，-i），再对剩余序列进行调整，反复进行该过程，直至排序完成。

//调整函数
function headAdjust(elements, pos, len){
  //将当前节点值进行保存
  var swap = elements[pos];

  //定位到当前节点的左边的子节点
  var child = pos * 2 + 1;

  //递归，直至没有子节点为止
  while(child < len){
    //如果当前节点有右边的子节点，并且右子节点较大的场合，采用右子节点
    //和当前节点进行比较
    if(child + 1 < len && elements[child] < elements[child + 1]){
      child += 1;
    }

    //比较当前节点和最大的子节点，小于则进行值交换，交换后将当前节点定位
    //于子节点上
    if(elements[pos] < elements[child]){
      elements[pos] = elements[child];
      pos = child;
      child = pos * 2 + 1;
    }
    else{
      break;
    }

    elements[pos] = swap;
  }
}

//构建堆
function buildHeap(elements){
  //从最后一个拥有子节点的节点开始，将该节点连同其子节点进行比较，
  //将最大的数交换与该节点,交换后，再依次向前节点进行相同交换处理，
  //直至构建出大顶堆（升序为大顶，降序为小顶）
  for(var i=elements.length/2; i>=0; i--){
    headAdjust(elements, i, elements.length);
  }
}

function sort(elements){
  //构建堆
  buildHeap(elements);

  //从数列的尾部开始进行调整
  for(var i=elements.length-1; i>0; i--){
    //堆顶永远是最大元素，故，将堆顶和尾部元素交换，将
    //最大元素保存于尾部，并且不参与后面的调整
    var swap = elements[i];
    elements[i] = elements[0];
    elements[0] = swap;

    //进行调整，将最大）元素调整至堆顶
    headAdjust(elements, 0, i);
  }
}

var elements = [3, 1, 5, 7, 2, 4, 9, 6, 10, 8];
console.log('before: ' + elements);
sort(elements);
console.log(' after: ' + elements);

• 桶排序原理：桶排序(Bucket sort)是一种基于计数的排序算法，工作的原理是将数据分到有限数量的桶子里，然后每个桶再分别排序（有可能再使用别的排序算法或是以递回方式继续使用桶排序进行排序）。当要被排序的数据内的数值是均匀分配的时候，桶排序时间复杂度为Θ(n)。桶排序不同于快速排序，并不是比较排序，不受到时间复杂度 O(nlogn) 下限的影响

function bucketSort(array, num) {
　　if (array.length <= 1) {
　　　　return array;
　　}
　　var len = array.length, buckets = [], result = [], min = max = array[0], space, n = 0;

　　var index = Math.floor(len / num) ;
　　while(index<2){

　　　　num--;
　　　　index = Math.floor(len / num) ;
　　}

　　console.time('桶排序耗时');
　　for (var i = 1; i < len; i++) {
　　　　min = min <= array[i] ? min : array[i];
　　　　max = max >= array[i] ? max : array[i];
　　}
　　space = (max - min + 1) / num;  //步长
 　　for (var j = 0; j < len; j++) {
　　　　var index = Math.floor((array[j] - min) / space);
　　　　if (buckets[index]) { // 非空桶，插入排序
 　　　　　　var k = buckets[index].length - 1;
　　　　　　while (k >= 0 && buckets[index][k] > array[j]) {
　　　　　　　　buckets[index][k + 1] = buckets[index][k];
　　　　　　　　k--;
　　　　　　}
　　　　　　buckets[index][k + 1] = array[j];
　　　　} else { //空桶，初始化
 　　　　　　buckets[index] = [];
　　　　　　buckets[index].push(array[j]);
　　　　}
　　}
　　while (n < num) {
　　　　result = result.concat(buckets[n]);
　　　　n++;
　　}
　　console.timeEnd('桶排序耗时');
　　return result;
}
var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(bucketSort(arr,4));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50];

• 基数排序原理：数排序只是针对于数字，思想就是将我们需要待排列的元素按照指定的进制将每一位排列，时间复杂度为：P(N+B)，注：其中P为待排列数字的最大位数，N为待排序列的长度，B为进制数

// 获得每位的数字
function RadixLSDSort (arr, digit) {
    const radix = 10;   // 基数,以10进制来进行排序
    var i = 0, 
        j = 0,
        count = Array(radix), // 0~9的桶
        end = arr.length,
        bucket = Array(end);
    // 利用LSD,也就是次位优先
    for (var d = 1; d <= digit; d++) {
        for (i = 0; i < radix; i++) {
            count[i] = 0;
        }
        // 向各个桶中添加元素,并统计出每个桶中装的个数
        for (i = 0; i < end; i++) {
            j = getDigit(arr[i], d);
            count[j]++;
        }
        // count的越往后值最大,最大值为arr.length
        // count数组的值为,该位数值为该索引的数字总数
        for (i = 1; i < radix; i++) {
            count[i] = count[i] + count[i - 1];
        }
        // 按照桶的顺序将导入temp中
        for (i = end - 1; i >= 0; i--) {
            j = getDigit(arr[i], d);
            bucket[count[j] - 1] = arr[i];
            count[j]--; 
        }
        // 将已经根据相应位数排好的序列导回arr中
        for (i = 0; i < end; i++) {
            arr[i] = bucket[i];
        }
    }   
}

• 计数排序原理：查找待排序数组中最大和最小的元素，统计每个值为i的元素的出现次数，对所有计数开始累加(从min开始,每一项和前一项相加)，反向填充目标数组,将每个元素i放在新数组的第C[i]项,每放一个元素,计数-1.

function countingSort(arr){
  var len = arr.length,
      Result = [],
      Count = [],
      min = max = arr[0];
  console.time('countingSort waste time:');
  /*查找最大最小值,并将arr数置入Count数组中,统计出现次数*/
  for(var i = 0;i<len;i++){
    Count[arr[i]] = Count[arr[i]] ? Count[arr[i]] + 1 : 1;
    min = min <= arr[i] ? min : arr[i];
    max = max >= arr[i] ? max : arr[i];
  }
  /*从最小值->最大值,将计数逐项相加*/
  for(var j = min;j<max;j++){
    Count[j+1] = (Count[j+1]||0)+(Count[j]||0);
  }
  /*Count中,下标为arr数值,数据为arr数值出现次数;反向填充数据进入Result数据*/
  for(var k = len - 1;k>=0;k--){
    /*Result[位置] = arr数据*/
    Result[Count[arr[k]] - 1] = arr[k];
    /*减少Count数组中保存的计数*/
    Count[arr[k]]--;
    /*显示Result数组每一步详情*/
    console.log(Result);
  }
  console.timeEnd("countingSort waste time:");
  return Result;
}
var arr = [3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(countingSort(arr));