前端常见的排序算法算法

冒泡排序

我们先来了解一下冒泡排序算法，它是最慢的排序算法之一，但也是一种最容易实现的排
序算法。
之所以叫冒泡排序是因为使用这种排序算法排序时，数据值会像气泡一样从数组的一端漂浮到另一端。假设正在将一组数字按照升序排列，较大的值会浮动到数组的右侧，而较小的值则会浮动到数组的左侧。之所以会产生这种现象是因为算法会多次在数组中移动，比较相邻的数据，当左侧值大于右侧值时将它们进行互换。

代码实现

function swap(i,j,array){
  let temp = array[j];
  array[j] = array[i];
  array[i] = temp;
}

function bubbleSort(data) {
  let length = data.length, isSwap;
  for (var i = 0; i < length; i++) {            //正序
    isSwap = false;
    for (var j = 0; j < length - 1 - i; j++) {     //正序
      array[j] > array[j+1] && (isSwap = true) && swap(j,j+1,array);
    }
    if(!isSwap)
      break;
  }
  return data;
}

选择排序

我们接下来要看的是选择排序算法。选择排序从数组的开头开始，将第一个元素和其他元素进行比较。检查完所有元素后，最小的元素会被放到数组的第一个位置，然后算法会从第二个位置继续。这个过程一直进行，当进行到数组的倒数第二个位置时，所有的数据便完成了排序。
选择排序会用到嵌套循环。外循环从数组的第一个元素移动到倒数第二个元素；内循环从第二个数组元素移动到最后一个元素，查找比当前外循环所指向的元素小的元素。每次内循环迭代后，数组中最小的值都会被赋值到合适的位置

代码实现

function selectSort(data) {
    let length = data.length;
    let min = 0;
    for(let i = 0; i < length; i++){
        min = i;
        for(let j = i +1; j < length; j++){
            if(data[min] > data[j]){
                swap(min,j,data)
            }
        }
    }
  return data
}

插入排序

插入排序类似于人类按数字或字母顺序对数据进行排序。例如，让班里的每个学生上交一张写有他的名字、学生证号以及个人简介的索引卡片。学生交上来的卡片是没有顺序的，但是我想让这些卡片按字母顺序排好，这样就可以很容易地与班级花名册进行对照了。我将卡片带回办公室，清理好书桌，然后拿起第一张卡片。卡片上的姓氏是 Smith 。我把它放到桌子的左上角，然后再拿起第二张卡片。这张卡片上的姓氏是 Brown 。我把 Smith移右，把 Brown 放到 Smith 的前面。下一张卡片是 Williams ，可把它放到桌面最右边，而不用移动其他任何卡片。下一张卡片是 Acklin 。这张卡片必须放在这些卡片的最前面，因此其他所有卡片必须向右移动一个位置来为 Acklin 这张卡片腾出位置。这就是插入排序的排序原理。

代码实现

function insertSort(data) {
    let length = data.length;
    let index,current;
    for(let i = 0; i<length; i++){
        index = i;
        current = data[i];
        while(index>=0 && (data[index+1] < data[index])){
            swap(index, index+1, data);
            index--;
        }
    }
  return data
}

希尔排序

希尔排序是以它的创造者（Donald Shell）命名的。这个算法在插入排序的基础上做了很大的改善。希尔排序的核心理念与插入排序不同，它会首先比较距离较远的元素，而非相邻的元素。和简单地比较相邻元素相比，使用这种方案可以使离正确位置很远的元素更快地回到合适的位置。当开始用这个算法遍历数据集时，所有元素之间的距离会不断减小，直到处理到数据集的末尾，时算法比较的就是相邻元素了。
希尔排序的工作原理是，通过定义一个间隔序列来表示在排序过程中进行比较的元素之间有多远的间隔。我们可以动态定义间隔序列，不过对于大部分的实际应用场景，算法要用到的间隔序列可以提前定义好。有一些公开定义的间隔序列，使用它们会得到不同的结果。在这里我们用到了 Marcin Ciura 在他 2001 年发表的论文“Best Increments for theAverage Case of Shell Sort”（http:bit.ly/1b04YFv,2001）中定义的间隔序列。这个间隔序列是： 701, 301, 132, 57, 23, 10, 4, 1 。

代码实现

function shellsort(data) {
    let gap = Math.floor(data.length/2);
    while(gap>=1){
        for(let i = gap; i<data.length; i++){
            if(data[i]<data[i-gap]){
                swap(i-gap, i, data);
                shellTime += 1;
            }
        }
        gap = gap/2;
    }
  return data
}

归并排序

归并排序的命名来自它的实现原理：把一系列排好序的子序列合并成一个大的完整有序序列。从理论上讲，这个算法很容易实现。我们需要两个排好序的子数组，然后通过比较数据大小，先从最小的数据开始插入，最后合并得到第三个数组。然而，在实际情况中，归并排序还有一些问题，当我们用这个算法对一个很大的数据集进行排序时，我们需要相当大的空间来合并存储两个子数组。就现在来讲，内存不那么昂贵，空间不是问题，因此值得我们去实现一下归并排序，比较它和其他排序算法的执行效率。

代码实现

function mergeSort(data) {
    if(data.length < 2){
        return data
    }else{
        let mid = Math.floor(data.length/2);
        let left = data.slice(0, mid);
        let right = data.slice(mid);
        return merge(mergeSort(left), mergeSort(right));
    }
}
function merge(left, right) {
    let arr = [];
    while(left.length > 0 && right.length > 0){
        if(left[0] > right[0]) {
            arr.push(right.shift())
        }else{
            arr.push(left.shift())
        }
    }
    return arr.concat(left, right);
}

快速排序

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

代码实现

function quickSort(data) {
    if(data.length === 0){
        return []
    }
    let lesser = [];
    let greater = [];
    let pivot = data[0];
    for(let i = 1; i<data.length; i++){
        if(data[i] < pivot){
            lesser.push(data[i]);
        }else{
            greater.push(data[i]);
        }
    }
    return quickSort(lesser).concat(pivot,quickSort(greater))
}