冒泡排序

思路：每一轮都将最大的元素放到最后面。

function bubbleSort(arr) {
  // 控制交换多少轮
  for (let i = 0, len = arr.length; i < len; i++) {
    // 标志位，用于判断是否已经是升序数组了
    let flag = false
    // 控制每一轮的比较和交换
    // 在区间 [0, len - 1 - 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]]
        // 发生了交换，说明数组不是升序数组
        flag = true
      }
      // 没有发生交换，说明数组已经是升序数组了，无需排序，直接返回即可
      if (!flag) return arr
    }
  }
  // 返回排序后的数组
  return arr
}
const arr = [5, 4, 3, 2, 1]
bubbleSort(arr) // [ 1, 2, 3, 4, 5 ]

冒泡排序最好的时间复杂度为 O(n)；最坏的时间复杂度为 O(n^2)；平均时间复杂度为 O(n^2)。

选择排序

思路：遍历数组，每次找到当前范围内的最小值，把它放到前面。然后缩小范围，重复前面的操作，直到数组遍历完。

function selectSort(arr) {
  // 控制轮数
  // i < len - 1 是因为最后一个数字不用管
  for (let i = 0, len = arr.length; i < len - 1; i++) {
    // 用于记录最小值索引，初始为 i 的值
    let minIndex = i
    // 在区间 [i, j] 中对比
    for (let j = i; j < len; j++) {
      // 如果索引为 j 的值比当前设定的最小元素还小，就将 j 赋值给 minIndex，更新最小值索引
      if (arr[j] < arr[minIndex]) minIndex = j
    }
    // 如果最小值索引发生了变化，则说明需要发生袁术的交换
    if (minIndex !== i) [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]]
  }
  // 返回排序后的数组
  return arr
}
const arr = [5, 4, 3, 2, 1]
console.log(selectSort(arr))

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

插入排序

将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。- 菜鸟教程

function insertSort(arr) {
  for (let i = 1, len = arr.length; i < len; i++) {
    let j = i
    const temp = arr[i]
    while (j > 0 && arr[j - 1] > temp) {
      arr[j] = arr[j - 1]
      j--
    }
    arr[j] = temp
  }
  return arr
}

插入排序的最好时间复杂度为 O(n)，最坏的时间复杂度为 O(n^2)，平均时间复杂度为 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,len))  
  // 合并左右两个有序数组
  arr = mergeArr(leftArr, rightArr)  
  // 返回合并后的结果
  return arr
}

function mergeArr(arr1, arr2) {  
  // 初始化两个指针，分别指向 arr1 和 arr2
  let i = 0, j = 0   
  // 初始化结果数组
  const res = []    
  // 缓存arr1的长度
  const len1 = arr1.length  
  // 缓存arr2的长度
  const len2 = arr2.length  
  // 合并两个子数组
  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))。

快速排序

思路：

1. 从数组中选一个元素作为基准值
2. 对数组进行排序，左边的值都小于或等于基准值，右边的值都大于基准值
3. 递归上面的步骤

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
}

const arr = [5, 4, 3, 2, 1]
console.log(quickSort(arr))

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

排序链表-148

给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

示例 1：


输入：head = [4,2,1,3]
输出：[1,2,3,4]
示例 2：


输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]
示例 3：

输入：head = []
输出：[]


提示：

链表中节点的数目在范围 [0, 5 * 104] 内
-105 <= Node.val <= 105


进阶：你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？

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

方法一：
思路：遍历链表，将链表中的元素存入一个数组，将这个数组排序，然后再用这个数组中的元素创建一个新的链表。

var sortList = function (head) {
    if (!head) return head
    const res = []
    while (head) {
        res.push(head.val)
        head = head.next
    }
    res.sort((a, b) => a - b)
    const node = new ListNode()
    let cur = node
    res.forEach((item) => {
        cur.next = new ListNode(item)
        cur = cur.next
    })
    return node.next
};

方法二：
思路：

排序数组剑指-912

给你一个整数数组 nums，请你将该数组升序排列。

示例 1：

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

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


提示：

1 <= nums.length <= 5 * 104
-5 * 104 <= nums[i] <= 5 * 104


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

方法一：快排

var sortArray = function(nums) {
    return quickSort(nums)
};
function quickSort(arr, start = 0, end = arr.length - 1) {
    if (end - start < 1) return arr
    const index = partition(arr, start, end)
    quickSort(arr, start, index - 1)
    quickSort(arr, index + 1, end)
    return arr
}
function partition(arr, start, end) {
    let j = start;
    const povit = arr[end];
    for (let i = start; i <= end; i++) {
        if (arr[i] <= povit) {
            [arr[i], arr[j]] = [arr[j], arr[i]]
            j++
        }
    }
    return j - 1
}

更快的快排写法：

var sortArray = function (nums) {
  if (nums == null || nums.length === 0) {
    return
  }
  quickSort(nums, 0, nums.length - 1)
  return nums
}

function quickSort(nums, start, end) {

  if (start >= end) {
    return
  }

  let left = start,
      right = end,
      mid = nums[Math.floor((start + end) / 2)];

  while (left <= right) {
    while (left <= right && nums[left] < mid) {
      left++;
    }
    while (left <= right && nums[right] > mid) {
      right--;
    }

    if (left <= right) {
      [nums[left], nums[right]] = [nums[right], nums[left]]
      left++;
      right--;
    }

  }

  quickSort(nums, start, right);
  quickSort(nums, left, end);
}

调整数组顺序使奇数位于偶数前面-Offer 21

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数在数组的前半部分，所有偶数在数组的后半部分。

示例：

输入：nums = [1,2,3,4]
输出：[1,3,2,4] 
注：[3,1,2,4] 也是正确的答案之一。

提示：

0 <= nums.length <= 50000
0 <= nums[i] <= 10000

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/diao-zheng-shu-zu-shun-xu-shi-qi-shu-wei-yu-ou-shu-qian-mian-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

方法一：
遍历数组，如果当前是数字是奇数就放新数组的前面，否则放新数组的后面，遍历完成后，返回新数组

var exchange = function(nums) {
  const res = [];
  for (let i = 0, len = nums.length; i < len;  i++) {
    if (nums[i] % 2 !== 0) {
      res.unshift(nums[i])
    }else {
      res.push(nums[i])
    }
  }
  return res;
};

方法二：

var exchange = function(nums) {
  var i = 0, j = nums.length - 1;
  var tmp;
  while(i < j){
    while(i < j && nums[i] % 2 == 1){
      i++;
    }
    while(i < j && nums[j] % 2 == 0){
      j--;
    }
    [nums[i], nums[j]] = [nums[j], nums[i]]
  }
  return nums;
};

x&1 位运算 等价于 x \% 2x%2 取余运算，它们都能用于判断数字奇偶性。

最小K个数-面试题 17.14.

设计一个算法，找出数组中最小的k个数。以任意顺序返回这k个数均可。

示例：

输入： arr = [1,3,5,7,2,4,6,8], k = 4
输出： [1,2,3,4]
提示：

0 <= len(arr) <= 100000
0 <= k <= min(100000, len(arr))

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

将数组升序排序，然后返回前 k 个数字即可

var smallestK = function(arr, k) {
  arr.sort((a, b) => (a - b))
  return arr.slice(0, k)
};

颜色分类-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/problems/sort-colors
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

方法一：快速排序

var sortColors = function(nums) {
    return quickSort(nums)
};
function quickSort(arr, start = 0, end = arr.length - 1) {
    if (end - start < 1) return arr
    const index = partition(arr, start, end)
    quickSort(arr, start, index - 1)
    quickSort(arr, index + 1, end)
    return arr
}
function partition(arr, start, end) {
    let j = start
    const povit = arr[end]
    for (let i = start; i <= end; i++) {
        if (arr[i] <= povit) {
            [arr[i], arr[j]] = [arr[j], arr[i]]
            j++
        }
    }
    return j - 1
}

方法二：

var sortColors = function(nums) {
    let L=0;
    let R=nums.length-1;
    let idx=0
    while(idx<=R){
        if(nums[idx]==0){
            swap(nums,idx++,L++)
        }else if(nums[idx]==2){
            swap(nums,idx,R--)
        }else{
            idx++;
        }
    }

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

最长单词-面试题 17.15

给定一组单词words，编写一个程序，找出其中的最长单词，且该单词由这组单词中的其他单词组合而成。若有多个长度相同的结果，返回其中字典序最小的一项，若没有符合要求的单词则返回空字符串。

示例：

输入： ["cat","banana","dog","nana","walk","walker","dogwalker"]
输出： "dogwalker"
解释： "dogwalker"可由"dog"和"walker"组成。
提示：

0 <= len(words) <= 200
1 <= len(words[i]) <= 100

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

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

给你一个字符串 s 和一个字符串数组 dictionary ，找出并返回 dictionary 中最长的字符串，该字符串可以通过删除 s 中的某些字符得到。

如果答案不止一个，返回长度最长且字母序最小的字符串。如果答案不存在，则返回空字符串。

示例 1：

输入：s = "abpcplea", dictionary = ["ale","apple","monkey","plea"]
输出："apple"
示例 2：

输入：s = "abpcplea", dictionary = ["a","b","c"]
输出："a"

提示：

1 <= s.length <= 1000
1 <= dictionary.length <= 1000
1 <= dictionary[i].length <= 1000
s 和 dictionary[i] 仅由小写英文字母组成

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

方法一：双指针
遍历 dictionary 拿到其中的每一项，定义两个指针分别为 i 和 j , i 指向遍历到的字符串 t 的起始位置，j 指向 s 字符串的起始位置

var findLongestWord = function (s, dictionary) {
  // 存储结果
  let res = "";
  // 遍历字典
  for (const t of dictionary) {
    // 双指针 i 指向字典中某个元素 j 指向字符串 s
    let i = 0, j = 0;
    // 字符串 t 和 s 都没遍历完
    while (i < t.length && j < s.length) {
      // 字符串 t 中的元素和 s 中的元素相等
      if (t[i] === s[j]) {
        // 移动 i 指针
        ++i;
      }
      // 移动 j 指针
      ++j;
    }
    // 当 i === t.length 表明 i 遍历到了末尾，找到了一个 s 的子串
    if (i === t.length) {
      // 当前字符串的长度大于结果字符串的长度或者当前字符串的长度等于结果字符串的长度且当前字符串的字典序小于结果字符串，更新结果字符串
      if (t.length > res.length || (t.length === res.length && t < res)) {
        res = t;
      }
    }
  }
  // 返回结果
  return res;
};

var findLongestWord = function (s, dictionary) {
  dictionary.sort((word1, word2) => {
    if (word1.length !== word2.length) {
      return word2.length - word1.length;
    } else {
      return word1.localeCompare(word2);
    }
  });

  for (const t of dictionary) {
    let i = 0, j = 0;
    while (i < t.length && j < s.length) {
      if (t[i] === s[j]) {
        ++i;
      }
      ++j;
    }
    if (i === t.length) {
      return t;
    }
  }
  return "";
};