经典排序

在日常的开发中，数据结构中介绍的排序算法一直都是比较常用，这里我们以js的形式再做一次总结，提高理解。

归并排序

 // 归并排序(nlogn)
     function mergeSort(arr, key){

         /**
         * @param {array} left 左侧数组, 有序数组
         * @param {array} right 右侧数组, 有序数组
         **/

          var merge =  function(left, right){
             var final = [];
             while(left.length && right.length){
              // 左右因为都是有序数组， 每次只比较第一位就可以了，选择小的一位放进新数组
               final.push(left[0][key] < right[0][key] ? left.shift() : right.shift())
             }
             return final.concat(left.concat(right)) // 返回
          }

          var len = arr.length;

          // 分割数组，直至数组长度为 1，则不再分割
          if (len < 2) return arr;
          var mid = len / 2; 

          return merge(mergeSort(arr.slice(0, parseInt(mid))), mergeSort(arr.slice(parseInt(mid))));
       }

冒泡排序

// 冒泡排序
       function bSort(arr){
           for(var i = 0; i < arr.length - 1; i++){
               var flag = false;
               for(var j = arr.length; j > i; j--){
                if(arr[i] > arr[j]){
                       let temp = arr[i];
                       arr[i] = arr[j];
                       arr[j] = temp;
                       flag = true;
                   }
               }
               if(flag === false){
                   return arr;
               }
           }
           return arr;
       }

简单选择排序

 // 选择排序算法，遍历所有数字， 将最小值和第一个没有排序过的位置交换
        function sortArray(arr, key) {
            if (arr.length < 2) return arr;
            for (var i = 0;  i < arr.length - 1; i++){
                for (var j = i + 1; j < arr.length; j++){
                    let temp;
                    if(arr[i][key] > arr[j][key]){
                        temp = arr[i];
                        arr[i] = arr[j];
                        arr[j] = temp;
                    }
                }
            }
            return arr;
        }

插入排序

// 插入排序(nlogn)
        function insertSortArray(arr,key) {
                if(arr.length < 2 ) return arr;
                for(var i = 1; i < arr.length; i++){  // 假定第一个值为排好的
                    if(arr[i-1][key] > arr[i][key]){
                        let temp = arr[i],  // 把应往前放的值拿出来，准备往前插
                         j;
                        for(j = i - 1; j >=0 && arr[j][key] > temp[key]; j--){
                            arr[j+1] = arr[j]; // 把前面所有小于temp的值位置往后移一位（始终会有一个空位子）
                        }
                        arr[j+1] = temp;  //  把temp值放在这个空位置
                     }
                }
                return arr;       
            }

// 二分插入排序
        function insertSort2(arr){
            if(arr.length && arr.length < 2) return arr;
            for(var i = 0; i < arr.length; i++){
                var temp = arr[i];
                var low = 0, high = i - 1;
                var mid = -1;
                while (low <= high) {            
                    mid = Math.floor((high + low) / 2);            
                    if (arr[mid] > temp) {               
                        high = mid - 1;            
                    } else { // 元素相同时，也插入在后面的位置                
                        low = mid + 1;            
                    }        
                }        
                for(var j = i - 1; j >= low; j--) {            
                    arr[j + 1] = arr[j];        
                }        
                arr[low] = temp;
            }
            return arr;
        }

Js内置排序

// js 内置的排序算法
        function jsSortArray(arr, key) {
                if (arr.length < 2) return arr;
                arr.sort(function(a, b){
                    return a[key] - b[key];
                })
                return arr;
        }

快速排序

        //快速排序 取中间值，大于中间数的放在右边，小于中间数的放在左边
        function quickSort(arr){
           if(arr.length < 2) return arr;
           var left =[] , right = [];
           var mid = arr.splice(Math.floor(arr.length / 2), 1)[0];

           for(var i =0; i < arr.length; i++){
              arr[i] > mid ?  right.push(arr[i]) : left.push(arr[i]);
           }

           return quickSort(left).concat(mid, quickSort(right))
      }

             function quickSort(array , start = 0, end = array.length -1) {
                 if (array.length < 2) return arr;

                var partition = function(array, from, to) {
                    var position = from - 1;
                    var base = array[to];
                    for (var i = from; i < to; i++) {
                        if (array[i] <= base) {
                            position++;
                            var temp = array[position];
                            array[position] = array[i];
                            array[i] = temp;
                        }
                    }
                    var temp = array[position + 1];
                    array[position + 1] = array[to];
                    array[to] = temp;
                    return position + 1;
                }

                 if (start < end) {
                    var position = partition(array, start, end);
                    quickSort(array, start, position - 1);
                    quickSort(array, position + 1, end);
                }
             }

希尔排序

希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本，利用了 '插排 在数组顺序 接近 有序时 此 排序速度最快' 这个特性而产生的'

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