十大排序

相关概念

• 稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
• 不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。
• 时间复杂度：对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。

• 空间复杂度：是指算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数。

  冒泡排序

  步骤

• 比较相邻的元素。如果第一个比第二个大，就交换它们两个；

• 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
• 针对所有的元素重复以上的步骤，除了最后一个；

• 重复步骤1~3，直到排序完成。

  动图

  

  代码实现

  function bubbleSort(arr) {
    let len = arr.length;
    for(let i = 0; i < len - 1; i++) {
        for(let j = 0; j < len - 1 - i; j++) {
            if(arr[j] > arr[j+1]) {        // 相邻元素两两对比
                let temp = arr[j+1];        // 元素交换
                arr[j+1] = arr[j];
                arr[j] = temp;
            }
        }
    }
    return arr;
  }

  算法复杂度

  
  

  快速排序

  步骤

• 比较相邻的元素。如果第一个比第二个大，就交换它们两个；

• 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
• 针对所有的元素重复以上的步骤，除了最后一个；

• 重复步骤1~3，直到排序完成。

  动图

  

  代码实现

  function bubbleSort(arr) {
    let len = arr.length;
    for(let i = 0; i < len - 1; i++) {
        for(let j = 0; j < len - 1 - i; j++) {
            if(arr[j] > arr[j+1]) {        // 相邻元素两两对比
                let temp = arr[j+1];        // 元素交换
                arr[j+1] = arr[j];
                arr[j] = temp;
            }
        }
    }
    return arr;
  }

  算法复杂度

  
  

  简单插入排序

  步骤

• 取第一个元素开始，该元素被认为已经被排序；

• 取出下一个元素，在已经排序的元素序列中从后向前扫描；
• 如果该元素（已排序）大于新元素，将该元素移到下一位置；
• 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
• 将新元素插入到该位置后；
• 重复步骤2~5。

动图

代码实现

function insertionSort(arr) {
    let len = arr.length;
    let preIndex, current;
      //第一个默认已排序
    for(let i = 1; i < len; i++) {
        //获取前一个
        preIndex = i - 1;
        current = arr[i];
          //前一个元素 大于 当前这个元素
        while(preIndex >= 0 && arr[preIndex] > current) {
              //前一个元素向后移位
            arr[preIndex + 1] = arr[preIndex];
            preIndex--;
        }
          //把当前元素移动到前一个
        arr[preIndex + 1] = current;
    }
    return arr;
}

算法分析

插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

算法复杂度

希尔排序

1959年Shell发明，第一个突破O(n)的排序算法，是简单插入排序的改进版。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。

步骤

• 选择一个增量（d），数组为arr；

增量的范围： 1<= d < 待排序数组的长度 （d 需为 int 值）
增量的取值： 一般的初次取序列（数组）的一半为增量，以后每次减半，直到增量为1。
第一个增量=数组的长度/2,
第二个增量= 第一个增量/2,
第三个增量=第二个增量/2,
以此类推，最后一个增量=1。

• 按d个数，对序列进行排序，第一次排序d为数组的长度/2，比较arr[d]向前数d个元素arr[d-d]，不符合顺序则交换，第二次比较arr[d+1]和arr[d+1-d]，直到d=数组的长度
• 第二次比较将原始d除于2，重复以上步骤，直到d=1

动图

代码实现

function shellSort(arr) {
    var len = arr.length;
         /**
    *首次增量为数组的二分之一         
      *逐次增量/2
    *增量大于0
      */
    for(let gap = Math.floor(len / 2); gap > 0; gap = Math.floor(gap / 2)) {
        // 注意：这里和动图演示的不一样，动图是分组执行，实际操作是多个分组交替执行
        for(let i = gap; i < len; i++) {
            let j = i;
            let current = arr[i];
              //对比增量范围两端的值
            while(j - gap >= 0 && current < arr[j - gap]) {
                   //不符合排序则交换位置
                 arr[j] = arr[j - gap];
                 j = j - gap;
            }
            arr[j] = current;
        }
    }
    return arr;
}

算法分析

希尔排序的核心在于间隔序列的设定。既可以提前设定好间隔序列，也可以动态的定义间隔序列。动态定义间隔序列的算法是《算法（第4版）》的合著者Robert Sedgewick提出的。　

好的增量序列的共同特征：

• 最后一个增量必须为1；
• 应该尽量避免序列中的值(尤其是相邻的值)互为倍数的情况。

算法复杂度

简单选择排序

步骤

• 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置；
• 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾；
• 重复第二步，直到所有元素均排序完毕；

动图

代码实现

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

算法分析

表现最稳定的排序算法之一，因为无论什么数据进去都是O(n)的时间复杂度，所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。理论上讲，选择排序可能也是平时排序一般人想到的最多的排序方法了吧。

算法复杂度

堆排序

二路归并排序

多路归并排序

计数排序

桶排序

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排）。

步骤

• 设置一个定量的数组当作空桶；
• 遍历输入数据，并且把数据放到对应的桶里去；
• 对每个不是空的桶进行排序；
• 从不是空的桶里把排好序的数据拼接起来。

动图

代码实现

function bucketSort(arr, bucketSize) {
    if(arr.length === 0) {
      return arr;
    }

    let i;
    let minValue = arr[0];
    let maxValue = arr[0];
    for(i = 1; i < arr.length; i++) {
      if(arr[i] < minValue) {
          minValue = arr[i];                // 输入数据的最小值
      } else if(arr[i] > maxValue) {
          maxValue = arr[i];                // 输入数据的最大值
      }
    }

    // 桶的初始化
    let DEFAULT_BUCKET_SIZE = 5;            // 设置桶的默认数量为5
    bucketSize = bucketSize || DEFAULT_BUCKET_SIZE;
    let bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;  
    let buckets = newArray(bucketCount);
    for(i = 0; i < buckets.length; i++) {
        buckets[i] = [];
    }

    // 利用映射函数将数据分配到各个桶中
    for(i = 0; i < arr.length; i++) {
        buckets[Math.floor((arr[i] - minValue) / bucketSize)].push(arr[i]);
    }

    arr.length = 0;
    for(i = 0; i < buckets.length; i++) {
        insertionSort(buckets[i]);                      // 对每个桶进行排序，这里使用了插入排序
        for(varj = 0; j < buckets[i].length; j++) {
            arr.push(buckets[i][j]);                     
        }
    }

    return arr;
}

算法分析

桶排序最好情况下使用线性时间O(n)，桶排序的时间复杂度，取决与对各个桶之间数据进行排序的时间复杂度，因为其它部分的时间复杂度都为O(n)。很显然，桶划分的越小，各个桶之间的数据越少，排序所用的时间也会越少。但相应的空间消耗就会增大。
思考：如果利用对象的特点，就会减少空间复杂度

算法复杂度

基数排序