前言
排序算法是数据结构和算法之中的基本功，虽说做前端开发不经常用到算法，但在求职或跳槽时的笔试和面试题目中出现频率还是非常高的。所以掌握一些基本的算法，对于技术人员无疑是非常重要的。
这里只介绍四种JS排序算法：冒泡排序、选择排序、插入排序、快速排序。后面看了其他算法的话，再补充。
算法思想的描述是通过我自己的理解之后，说得比较通俗一点，没理解的可以自行百度（谷歌）这些算法。
冒泡排序
冒泡排序是排序算法中最简单的一个算法，因为简单，所以比较好理解和容易实现，适用于性能要求不高和数据量不大的场景。
算法思想：依次比较相邻两个元素，若第一个比第二个大，则交换位置，否则不交换。这样一轮比较过后，最大的数会排在最后一位。然后再对剩下的 n-1 个元素重复此过程。
代码实现如下：
function bubbleSort(arr) {
for(let i = 0, len = arr.length; i < len; i++) {
for(let j = 0; j < len - 1; j++) {
if(arr[j] > arr[j+1]) {
let temp = arr[j]
arr[j] = arr[j+1]
arr[j+1] = temp
}
}
}
return arr
}
冒泡排序的时平均间复杂度为O(n²)，最优时间复杂度为O(n)。
最优时间复杂度的情况是原来的数组本身就是有序数组，可以加一个swapTimes变量，记录相邻两个元素的交换次数。若第一轮两两比较下来，都没有交换过元素位置，证明该数组本身就是有序数组。
最优时间复杂度的代码实现:
function bubbleSort(arr) {
for(let i = 0, len = arr.length; i < len; i++) {
let swapTimes = 0
for(let j = 0; j < len - 1; j++) {
if(arr[j] > arr[j+1]) {
swapTimes++
let temp = arr[j]
arr[j] = arr[j+1]
arr[j+1] = temp
}
}
if(swapTimes < 1) {
break
}
}
return arr
}
选择排序
算法思想：每趟循环找出最大的元素，将其置于数组末尾位置。第一趟找出最大的元素，放置在数组n-1的位置，第二趟放置在n-2的位置，以此类推，直到所有元素都排序完毕。
代码实现：
function selectionSort(arr) {
let len = arr.length
let maxIndex = 0
for(let i = len - 1; i >= 0; i--) {
maxIndex = i
for(let j = 0; j < i; j++) {
if(arr[j] > arr[maxIndex]) {
maxIndex = j
}
}
let temp = arr[maxIndex]
arr[maxIndex] = arr[i]
arr[i] = temp
}
return arr
}
插入排序
插入排序是最好理解的一种排序算法，就是将未排序的元素，插入到已排序的序列里。
算法思想：首先把第一个元素归为已排序序列，然后从第二个元素开始，在已排序的序列中找到第一个小于该元素的值，将元素插入到这个值后面。
代码实现：
function insertionSort(arr) {
for(let i = 1; i < arr.length; i++) {
let unSorted = arr[i]
let j = i - 1;
while(j >= 0 && arr[j] > unSorted) {
console.log(j)
arr[j + 1] = arr[j]
j --;
}
console.log(i)
arr[j + 1] = unSorted
}
return arr
}
快速排序
快速排序基本上是面试必考的排序算法，也是实践中最常用到的算法，公认的最快的排序算法之一。
算法思想：在数组中选择一个元素作为”基准”值（通常为第一个），把小于”基准”的元素放在前面，大于”基准”的元素放在后面，这样就完成一次快速排序。然后对”基准”左边和右边的两个子集，不断重复上述过程，知道所有子集只剩下一个元素为止。
代码实现：
function quickSort(arr, left = 0, right = arr.length - 1) {
let pivot = arr[left] // 基准值
let i = left // 左边界
let j = right // 右边界
while(i < j) {
while(arr[j] > pivot && i < j) {
j--
}
if(arr[j] < pivot) {
swap(arr, i, j)
}
while(arr[i] <= pivot && i < j) {
i++
}
if(arr[i] > pivot) {
swap(arr, i, j)
}
// i 和 j相遇，即产生一个分界点，然后分别对该分界点的左右两个子集重复排序。
if(i === j) {
quickSort(arr, left, i - 1)
quickSort(arr, i + 1, right)
break
}
}
// 交换函数
function swap(arr, i, j) {
let temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}