排序算法

一、冒泡排序（Bubble Sort）

作为最简单的排序算法之一
工作原理：它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。
走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。

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[j+1]){ // 相邻元素两两对比
    var temp = arr[j+1]; // 元素交换
    arr[j+1] = arr[j];
    arr[j] = temp;
   }
  }
 }
 return arr;
}

二、选择排序（Selection Sort）

在时间复杂度上表现最稳定的排序算法之一，因为无论什么数据进去都是o(n²)的时间复杂度。
所以用到它的时候，数据规模越小越好。唯一的好处就是不占用额外的内存空间。
工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，
然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

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;
}

三、插入排序(Insertion Sort)

插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴，但是它的原理应该是最容易理解的了。工作原理：通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序(即只用到o(1)的额外空间的排序)，因而在从后向前扫描过程中，< 需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间

function insertSort(arr){
 var len = arr.length;
 for(i=1; i<len; i++){
  var key = arr[i];
  var j = i - 1;
  while(j>=0 && arr[j]>key){
   arr[j+1] = arr[j]
   j--;
  }
  arr[j+1] = key;
 }
 return arr;
}

四、希尔排序（shell sort）

又名缩小增量排序。希尔排序是插入排序的一种更高效率的实现。它与插入排序的不同之处在于，它会优先比较距离较远的元素。
希尔排序的核心在于间隔序列的设定。即可以提前设定好间隔序列，也可以动态的定义间隔序列。

function shellSort(arr){
    var len = arr.length,
            temp,
            gap = 1;
    while(gap < len/3){ //动态定义间隔序列
        gap = gap*3+1;
    }
    for(gap; gap>0; gap = Math.floor(gap/3)){
        for(var i = gap; i<len; i++){
            temp = arr[i];
            for(var j=i-gap; j>0 && arr[j]>temp; j-=gap){
                arr[j+gap] = arr[j];
            }
            arr[j+gap] = temp;
        }
    }
    return arr;
}

五、归并排序(Merge Sort)

作为一种典型的分而治之思想的算法应用，归并排序的实现由两种方法：
（1）自上而下的递归（所有递归的方法都可以用迭代重写，所以就有了第2中方法）
（2）自下而上的迭代归并排序是一种稳定的排序方法。将已有序的子序列合并，得到完全有序的序列，即先使每个子序列有序，再使子序列段间有序。
若将两个有序表合并成一个有序表，称为二路归并。

function mergeSort(arr){
    var len = arr.length;
    if(len<2){
        return arr
    }
    var middle = Math.floor(len/2);
    var left = arr.slice(0, middle)
    var right = arr.slice(middle)
    return merge(mergeSort(left), mergeSort(right));
}
function merge(left,right){
    var result = [];
    while(left.length && right.length){
        if(left[0] < right[0]){
            result.push(left.shift())
        }else{
            result.push(right.shift())
        }
    }
    while(left.length){
        result.push(left.shift())
    }
    while(right.length){
        result.push(right.shift())
    }
    return result
}

六、快速排序(Quick Sort)

快速排序是处理大数据集最快的排序算法之一。它是一种分而治之的算法，通过递归的方法将数据依次分解为包含较小元素和较大元素的不同子序列。
该算法不断重复这个步骤直到所有数据都是有序的。这个算法首先要在列表中选择一个元素作为基准值。
数据排序围绕基准值进行，将列表中小于基准值的元素移到数组的底部，将大于基准值的元素移到数组的顶部。

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