排序算法

排序算法可以分为内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。

常见的排序对比：

冒泡排序

冒泡排序是一种简单直观的排序算法，需要重复的走过要排序的数组，一次对比两个元素，根据排序方式对比后将顺序交换，直到没有需要交换的数据为止，说明该数组的排序已经完成，一般通过双层for循环可以实现，所以时间复杂度为O(n^2) 因为排序过程中小的元素会慢慢排在数列的顶端，所以形象的叫做冒泡排序。

算法步骤

1. 从数组的顶部开始对比第一个和第二个元素，如果第一个比第二个元素大，则交换它们的顺序
2. 对相邻的元素做同样的动作，一直到数组的最后一位，这个时候最后的元素会是最大的数
3. 针对所有的元素重复1，2步骤，除了最后一个
4. 重复1，2，3步骤，需要对比的元素会越来越少，直到没有任何可以对比的元素，则该数组的排序完成

代码实现

function sort (arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    for(let j = 0; j < arr.length - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        const next = arr[j + 1];
        arr[j + 1] = arr[j];
        arr[j] = next;
      }
    }
  }
  return arr
}

选择排序

选择排序是一种简单直观的排序算法，主要通过找到当前最小（大）值，放到数组的顶端，然后接下来重复步骤直至完成，同样也是需要双层循环去完成，所以也是O(n^2)的时间复杂度。

算法步骤

1. 定一个指针为0，从当前位置到数组的末尾查询最值，放到数组的起始位置
2. 从剩余未排序的数组中继续寻找，放在已排序的末尾
3. 重复1，2步骤，直到所有元素都排序完成

代码实现

function sort (arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    let cur = arr[i], minIndex // 保留起始index，保留最小索引
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[i] > arr[j]) {
        arr[i] = arr[j]
        minIndex = j
      }
    }
    if (minIndex) {
      arr[minIndex] = cur
    }
  }
  return arr
}

插入排序

插入排序

算法步骤

1. 把数组看成两个序列，第一个元素为有序序列，第二个元素到最后为无序序列
2. 从头到尾依次扫描未排序序列，在已排序序列中从后往前扫描
3. 如果已排序元素大于新元素，则将该元素移动到下一个位置
4. 重复3步骤，直到找到已排序的元素小于或等于新元素的位置
5. 将新元素插入到该位置，重复2，6步骤

代码实现

希尔排序

归并排序

快速排序

堆排序

计数排序

桶排序

桶排序