冒泡排序

冒泡排序的过程，就是从第一个元素开始，重复比较相邻的两个项，若第一项比第二项更大，则交换两者的位置；反之不动。

function bubbleSort(arr) {
  // 缓存数组长度
  const len = arr.length  
  // 外层循环用于控制从头到尾的比较+交换到底有多少轮
  for(let i=0;i<len;i++) {  
    // 内层循环用于完成每一轮遍历过程中的重复比较+交换
    for(let j=0;j<len-1;j++) {
      // 若相邻元素前面的数比后面的大
      if(arr[j] > arr[j+1]) {  
        // 交换两者
        [arr[j], arr[j+1]] = [arr[j+1], arr[j]]
      }
    }
  }
  // 返回数组
  return arr
}

上面的代码还可以优化，随着外层循环的进行，数组尾部的元素会渐渐变得有序，走完第 n 轮循环的时候，数组的后 n 个元素就已经是有序的，这数组后的 n 个元素就不要再参与排序了，优化后的代码如下：

function betterBubbleSort(arr) {
  const len = arr.length  
  for(let i=0;i<len;i++) {
    // 注意差别在这行，我们对内层循环的范围作了限制
    for(let j=0;j<len-1-i;j++) {
      if(arr[j] > arr[j+1]) {
        [arr[j], arr[j+1]] = [arr[j+1], arr[j]]
      }
    }
  }
  return arr
}

上面的代码我们还能继续优化，因为给定的数组可能是已经排好序的，优化代码如下：

function betterBubbleSort(arr) {
  const len = arr.length  

  for(let i=0;i<len;i++) {
    // 区别在这里，我们加了一个标志位
    let flag = false
    for(let j=0;j<len-1-i;j++) {
      if(arr[j] > arr[j+1]) {
        [arr[j], arr[j+1]] = [arr[j+1], arr[j]]
        // 只要发生了一次交换，就修改标志位
        flag = true
      }
    }

    // 若一次交换也没发生，则说明数组有序，直接放过
    if(flag == false)  return arr;
  }
  return arr
}

最好的时间复杂度是O(n)，也就是数组本身是有序的，这个时候只需要比较 n-1 次，不需要交换。最坏的时间复杂度是O(n^2)，这种情况下每轮的内循环都要执行。平均时间复杂度为O(n^2)。

插入排序

插入排序的核心思想是“找到元素在它前面那个序列中的正确位置”。
具体来说，插入排序所有的操作都基于一个这样的前提：当前元素前面的序列是有序的。基于这个前提，从后往前去寻找当前元素在前面那个序列里的正确位置。

function insertSort(arr) {
  // 缓存数组长度
  const len = arr.length
  // temp 用来保存当前需要插入的元素
  let temp  
  // i用于标识每次被插入的元素的索引
  for(let i = 1;i < len; i++) {
    // j用于帮助 temp 寻找自己应该有的定位
    let j = i
    temp = arr[i]  
    // 判断 j 前面一个元素是否比 temp 大
    while(j > 0 && arr[j-1] > temp) {
      // 如果是，则将 j 前面的一个元素后移一位，为 temp 让出位置
      arr[j] = arr[j-1]   
      j--
    }
    // 循环让位，最后得到的 j 就是 temp 的正确索引
    arr[j] = temp
  }
  return arr
}

插入排序最好的时间复杂度为O(n)，因为传入的数组可能是已经排好序的。最坏的时间复杂度为O(n2)，因为传入的数组可能是完全逆序的。平均时间复杂度为O(n^2)。

选择排序

选择排序的关键字是“最小值”：循环遍历数组，每次都找出当前范围内的最小值，把它放在当前范围的头部；然后缩小排序范围，继续重复以上操作，直至数组完全有序为止。

排序过程演示：

[5, 3, 2, 4, 1]
 ↑           ↑

在区间 [0, 4] 找到最小值1，和5交换，结果如下：
[1, 3, 2, 4, 5]

[1, 3, 2, 4, 5]
    ↑        ↑
在区间 [1, 4] 找到最小值 2，和 3 进行交换，结果如下：
[1, 2, 3, 4, 5]

在区间 [2, 4] 找到最小值 3，不需要交换
[1, 2, 3, 4, 5]
       ↑     ↑

在区间 [3, 4] 找到最小值 4，不需要交换
[1, 2, 3, 4, 5]
          ↑  ↑

代码如下：

function selectSort(arr)  {
  // 缓存数组长度
  const len = arr.length 
  // 定义 minIndex，缓存当前区间最小值的索引，注意是索引
  let minIndex  
  // i 是当前排序区间的起点
  for(let i = 0; i < len - 1; i++) { 
    // 初始化 minIndex 为当前区间第一个元素
    minIndex = i  
    // i、j分别定义当前区间的上下界，i是左边界，j是右边界
    for(let j = i; j < len; j++) {  
      // 若 j 处的数据项比当前最小值还要小，则更新最小值索引为 j
      if(arr[j] < arr[minIndex]) {  
        minIndex = j
      }
    }
    // 如果 minIndex 对应元素不是目前的头部元素，则交换两者
    if(minIndex !== i) {
      [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]]
    }
  }
  return arr
}

选择排序的时间复杂度为O(n^2)。

归并排序

“分治”，分而治之。其思想就是将一个大问题分解为若干个子问题，针对子问题分别求解后，再将子问题的解整合为大问题的解。

利用分治思想解决问题，我们一般分三步走：

分解子问题
求解每个子问题
合并子问题的解，得出大问题的解

function mergeSort(arr) {
  const len = arr.length;

  if (len <= 1) return arr

  const mid = Math.floor(len / 2)
  const leftArr = mergeSort(arr.slice(0, mid))
  const rightArr = mergeSort(arr.slice(mid))
  arr = mergeArr(leftArr, rightArr)

  return arr
}

function mergeArr(arr1, arr2) {
  let i = 0, j = 0
  const len1 = arr1.length, len2 = arr2.length, res = []

  while (i < len1 && j < len2) {
    if (arr1[i] < arr2[j]) {
      res.push(arr1[i])
      i++
    }else {
      res.push(arr2[j])
      j++
    }
  }

  if (i < len1) {
    return res.concat(arr1.slice(i))
  }else {
    return res.concat(arr2.slice(j))
  }
}

归并排序的时间复杂度是 O(nlog(n)) 。

快速排序

快速排序的时间复杂度由基准值决定。

以下代码来自手写算法并记住它：快速排序（5行代码简单版）。

function quickSort(arr) {
  const len = arr.length;
  if (len < 2) return arr;
  const pivot = arr[len - 1];
  const leftArr = arr.filter((item, index) => item <= pivot && index !== len - 1);
  const rightArr = arr.filter(item => item > pivot);
  return [...quickSort(leftArr), pivot, ...quickSort(rightArr)]
}

上面这种方式的空间复杂度为 O(nlogn)，时间复杂度为 O(nlogn)。

以下代码来自手写算法并记住它：快速排序（最易理解版）。

function quickSort(arr, start = 0, end = arr.length - 1) {
    if (end - start < 1) return arr;
    const pivotIndex = partition(arr, start, end);
    quickSort(arr, start, pivotIndex - 1);
    quickSort(arr, pivotIndex + 1, end);
    return arr;
}

function partition(arr, start, end) {
    let j = start;
    const pivot = arr[end];
    for (let i = start; i <= end; i++) {
        if (arr[i] <= pivot) {
            [arr[i], arr[j]] = [arr[j], arr[i]];
            j++;
        }
    }
    return j - 1;
}

快速排序的平均时间复杂度为 O(nlogn)，最坏情况的下的时间复杂度为 O(n^2)

练习

通过删除字母匹配到字典里最长单词-524

颜色分类-75

给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

必须在不使用库的sort函数的情况下解决这个问题。



示例 1：

输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]
示例 2：

输入：nums = [2,0,1]
输出：[0,1,2]


提示：

n == nums.length
1 <= n <= 300
nums[i] 为 0、1 或 2


进阶：

你可以不使用代码库中的排序函数来解决这道题吗？
你能想出一个仅使用常数空间的一趟扫描算法吗？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sort-colors
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

var sortColors = function(nums) {
    const len = nums.length;
    for (let i = 0; i < len; i++) {
        for (let j = 0; j < len - i - 1; j++) {
            if (nums[j] > nums[j + 1]) {
                [nums[j], nums[j + 1]] = [nums[j + 1], nums[j]];
            }
        }
    }
};

20.排序