排序算法可以分为内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。

一、 冒泡排序

冒泡排序（Bubble Sort）也是一种简单直观的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。冒泡排序对n个项目需要O(n²)的比较次数，且可以原地排序。尽管这个算法是最简单了解和实现的排序算法之一，但它对于包含大量的元素的数列排序是很没有效率的。

  • 算法步骤

    1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
    2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
    3. 针对所有的元素重复以上的步骤，除了最后一个。
    4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

  • 动图演示

    冒泡排序

  • 代码实现

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    function bubbleSort(arr) {
      var len = arr.length;
      for (var i = 0; i < len - 1; 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;
    }

二、选择排序

选择排序是一种简单直观的排序算法，无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。

  • 算法步骤

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

  • 动图演示

    选择排序

  • 代码实现

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    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;
    }

三、插入排序

插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴，但它的原理应该是最容易理解的了，因为只要打过扑克牌的人都应该能够秒懂。插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

插入排序和冒泡排序一样，也有一种优化算法，叫做拆半插入。

  • 算法步骤

    1. 将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
    2. 从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。。
    3. 如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。

  • 动图演示

    插入排序

  • 代码实现

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    function insertionSort(arr) {
      var len = arr.length;
      var preIndex, current;
      for (var 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;
    }

四、希尔排序

希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

  • 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；
  • 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位；

希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录”基本有序”时，再对全体记录进行依次直接插入排序。

  • 算法步骤

    1. 选择一个增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；
    2. 按增量序列个数 k，对序列进行 k 趟排序；
    3. 每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

  • 动图演示

    希尔排序

  • 代码实现

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    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）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

作为一种典型的分而治之思想的算法应用，归并排序的实现由两种方法：

  • 自上而下的递归（所有递归的方法都可以用迭代重写，所以就有了第 2 种方法）；

  • 自下而上的迭代；

  • 算法步骤

    1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
    2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置；
    3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
    4. 重复步骤 3 直到某一指针达到序列尾；
    5. 将另一序列剩下的所有元素直接复制到合并序列尾。

  • 动图演示

    归并排序

  • 代码实现

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    function mergeSort(arr) {  // 采用自上而下的递归方法
        var len = arr.length;
        if(len < 2) {
            return arr;
        }
        var middle = Math.floor(len / 2),
            left = arr.slice(0, middle),
            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;
    }

六、快速排序

快速排序的最坏运行情况是 O(n²)，比如说顺序数列的快排。但它的平摊期望时间是 O(nlogn)，且 O(nlogn) 记号中隐含的常数因子很小，比复杂度稳定等于 O(nlogn) 的归并排序要小很多。所以，对绝大多数顺序性较弱的随机数列而言，快速排序总是优于归并排序。

  • 算法步骤

    1. 从数列中挑出一个元素，称为 “基准”（pivot）。
    2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
    3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

  • 动图演示

    快速排序

  • 代码实现

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    function quickSort(arr, left, right) {
      var len = arr.length,
          partitionIndex,
          left = typeof left != 'number' ? 0 : left,
          right = typeof right != 'number' ? len - 1 : right;

      if (left < right) {
          partitionIndex = partition(arr, left, right);
          quickSort(arr, left, partitionIndex-1);
          quickSort(arr, partitionIndex+1, right);
      }
      return arr;
    }

    function partition(arr, left ,right) {     // 分区操作
        var pivot = left,                      // 设定基准值（pivot）
            index = pivot + 1;
        for (var i = index; i <= right; i++) {
            if (arr[i] < arr[pivot]) {
                swap(arr, i, index);
                index++;
            }        
        }
        swap(arr, pivot, index - 1);
        return index-1;
    }

    function swap(arr, i, j) {
        var temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    function partition2(arr, low, high) {
      let pivot = arr[low];
      while (low < high) {
        while (low < high && arr[high] > pivot) {
          --high;
        }
        arr[low] = arr[high];
        while (low < high && arr[low] <= pivot) {
          ++low;
        }
        arr[high] = arr[low];
      }
      arr[low] = pivot;
      return low;
    }

    function quickSort2(arr, low, high) {
      if (low < high) {
        let pivot = partition2(arr, low, high);
        quickSort2(arr, low, pivot - 1);
        quickSort2(arr, pivot + 1, high);
      }
      return arr;
    }

七、堆排序

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法：

大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；
小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；
堆排序的平均时间复杂度为 Ο(nlogn)。

  • 算法步骤

    1. 创建一个堆 H[0……n-1]。
    2. 把堆首（最大值）和堆尾互换。
    3. 把堆的尺寸缩小 1，并调用 shift_down(0)，目的是把新的数组顶端数据调整到相应位置。
    4. 重复步骤 2，直到堆的尺寸为 1。

  • 动图演示

    堆排序

  • 代码实现

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    var len;    // 因为声明的多个函数都需要数据长度，所以把len设置成为全局变量

    function buildMaxHeap(arr) {   // 建立大顶堆
        len = arr.length;
        for (var i = Math.floor(len/2); i >= 0; i--) {
            heapify(arr, i);
        }
    }

    function heapify(arr, i) {     // 堆调整
        var left = 2 * i + 1,
            right = 2 * i + 2,
            largest = i;

        if (left < len && arr[left] > arr[largest]) {
            largest = left;
        }

        if (right < len && arr[right] > arr[largest]) {
            largest = right;
        }

        if (largest != i) {
            swap(arr, i, largest);
            heapify(arr, largest);
        }
    }

    function swap(arr, i, j) {
        var temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    function heapSort(arr) {
        buildMaxHeap(arr);

        for (var i = arr.length-1; i > 0; i--) {
            swap(arr, 0, i);
            len--;
            heapify(arr, 0);
        }
        return arr;
    }

八、计数排序

计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

  • 算法步骤

    1. 找出待排序的数组中最大和最小的元素。
    2. 统计数组中每个值为i的元素出现的次数，存入数组C的第i项
    3. 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）
    4. 反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1

  • 动图演示

    计数排序

  • 代码实现

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
      function countingSort(arr, maxValue) {
        var bucket = new Array(maxValue+1),
            sortedIndex = 0;
            arrLen = arr.length,
            bucketLen = maxValue + 1;

        for (var i = 0; i < arrLen; i++) {
            if (!bucket[arr[i]]) {
                bucket[arr[i]] = 0;
            }
            bucket[arr[i]]++;
        }

        for (var j = 0; j < bucketLen; j++) {
            while(bucket[j] > 0) {
                arr[sortedIndex++] = j;
                bucket[j]--;
            }
        }

        return arr;
    }

九、桶排序

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效，我们需要做到这两点：

  • 在额外空间充足的情况下，尽量增大桶的数量
  • 使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中

同时，对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要。

  • 算法步骤

    1. 设置一个定量的数组当作空桶子
    2. 寻访序列，并且把项目一个一个放到对应的桶子去。
    3. 对每个不是空的桶子进行排序。
    4. 从不是空的桶子里把项目再放回原来的序列中。

  • 动图演示

    元素分布在桶中：
    桶排序
    然后，元素在每个桶中排序：
    桶排序

  • 代码实现

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    function bucketSort(arr, bucketSize) {
        if (arr.length === 0) {
          return arr;
        }

        var i;
        var minValue = arr[0];
        var 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];                // 输入数据的最大值
          }
        }

        //桶的初始化
        var DEFAULT_BUCKET_SIZE = 5;            // 设置桶的默认数量为5
        bucketSize = bucketSize || DEFAULT_BUCKET_SIZE;
        var bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;  
        var buckets = new Array(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 (var j = 0; j < buckets[i].length; j++) {
                arr.push(buckets[i][j]);                      
            }
        }

        return arr;
    }

十、基数排序

基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。

  • 基数排序 vs 计数排序 vs 桶排序

    基数排序有两种方法：

    这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：

    基数排序：根据键值的每位数字来分配桶；
    计数排序：每个桶只存储单一键值；
    桶排序：每个桶存储一定范围的数值；

  • LSD 基数排序动图演示

基数排序

  • 代码实现

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    var counter = [];
    function radixSort(arr, maxDigit) {
        var mod = 10;
        var dev = 1;
        for (var i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
            for(var j = 0; j < arr.length; j++) {
                var bucket = parseInt((arr[j] % mod) / dev);
                if(counter[bucket]==null) {
                    counter[bucket] = [];
                }
                counter[bucket].push(arr[j]);
            }
            var pos = 0;
            for(var j = 0; j < counter.length; j++) {
                var value = null;
                if(counter[j]!=null) {
                    while ((value = counter[j].shift()) != null) {
                          arr[pos++] = value;
                    }
              }
            }
        }
        return arr;
    }