[TOC]

排序算法

1. 直接插入排序

直接插入排序的核心思想就是：将数组中的所有元素依次跟前面已经排好的元素相比较，如果选择的元素比已排序的元素小，则交换，直到全部元素都比较过。因此，从上面的描述中我们可以发现，直接插入排序可以用两个循环完成：

第一层循环：遍历待比较的所有数组元素
第二层循环：将本轮选择的元素(selected)与已经排好序的元素(ordered)相比较。如果：selected > ordered，那么将二者交换

代码实现：

function insertSort(arr) {
  const len = arr.length || 0;
  let tmp = null;
  // 第一层循环，遍历一遍元素，默认第一个是拍好序的
  for (let i = 1; i < len; i++) { 
    // 第二层 从后到前循环，拿未排序的第一个元素跟拍好序的对比
    for (let j = i-1; j >= 0; j--) {
      // 如果前一个元素大于跟后一个元素，则交换他们
      if (arr[j] > arr[j+1]) {
        tmp = arr[j+1];
        arr[j+1] = arr[j];
        arr[j] = tmp;
      }
    }
  }
}

let arr = [3, 1, 8, 2, 7, 10, 9, 0, 20, 11];
insertSort(arr);
console.log('arr:', arr);

2. 选择排序

简单选择排序的基本思想：比较+交换。

从待排序序列中，找到最小的元素；
如果最小元素不是待排序序列的第一个元素，将其和第一个元素互换；
从余下的 N - 1 个元素中，找出最小的元素，重复(1)、(2)步，直到排序结束。

因此我们可以发现，简单选择排序也是通过两层循环实现。第一层循环：依次遍历序列当中的每一个元素第二层循环：将遍历得到的当前元素依次与余下的元素进行比较，符合最小元素的条件，则交换。

function insertSort(arr) {
  const len = arr.length || 0;
  let tmp = null, key = null;
  // 遍历数组，每次假设第i个元素是这次最小的
  for (let i = 0; i < len; i++) {
    key = i;
    // 遍历未排序的部分，跟假设的元素进行对比，找到最小的元素索引
    for (let j = i + 1; j < len; j++) {
      if (arr[key] > arr[j]) {
        key = j;
      }
    }
    // 把找到的最小元素跟第i个元素交换
    tmp = arr[i];
    arr[i] = arr[key];
    arr[key] = tmp;
  }
}
//        [ 0, 1, 2, 3, 7, 8, 9, 10, 11, 20 ]
let arr = [3, 1, 8, 2, 7, 10, 9, 0, 20, 11];
insertSort(arr);
console.log('arr:', arr);

3. 冒泡排序

冒泡排序思路比较简单：

将序列当中的左右元素，依次比较，保证右边的元素始终大于左边的元素；（第一轮结束后，序列最后一个元素一定是当前序列的最大值；）
对序列当中剩下的n-1个元素再次执行步骤1。
对于长度为n的序列，一共需要执行n-1轮比较（利用while循环可以减少执行次数）

function insertSort(arr) {
  const len = arr.length || 0;
  let tmp = null;
  // 遍历一遍数组
  for (let i = 0; i < len; i++) {
    // 遍历数组，找到最大的元素移到最后一位。下一次遍历都少一位
    for (let j = 1; j < len - i; j++) {
      if (arr[j] < arr[j-1]) { // 把大的数字移到后面
        tmp = arr[j];
        arr[j] = arr[j-1];
        arr[j-1] = tmp;
      }
    }
    
  }
}
//        [ 0, 1, 2, 3, 7, 8, 9, 10, 11, 20 ]
let arr = [3, 1, 8, 2, 7, 10, 9, 0, 20, 11];
insertSort(arr);
console.log('arr:', arr);

4. 快速排序

快速排序的基本思想：挖坑填数+分治法

从序列当中选择一个基准数(pivot)，假设为a 在这里我们选择序列当中第一个数最为基准数
将序列当中的所有数依次遍历，比基准数大的位于其右侧，比基准数小的位于其左侧
在分好的左右两边递归重复步骤1、2。直到所有子集当中只有一个元素为止。

function swap(arr, i, j) { // 交换数据
  var temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;
}
function quickSort(arr, left, right) {
  const len = arr.length;
  left = typeof left != "number" ? 0 : left,
  right = typeof right != "number" ? len - 1 : right;
  let partitionIndex = null; // 基点
  if (left < right) {
    let pivot = left; // 设定基准值（pivot）
    let index = pivot + 1;
    // 遍历数据，如果数据小于基点的数据，则移到左边，然后下一个基点位置后移
    for (let i = index; i <= right; i++) {
      if (arr[i] < arr[pivot]) {
        swap(arr, i, index);
        index++;
      }
    }
    swap(arr, pivot, index - 1);
    partitionIndex = index - 1;
    quickSort(arr, left, partitionIndex - 1);
    quickSort(arr, partitionIndex + 1, right);
  }
  return arr;
}

let arr = [3, 1, 8, 2, 7, 10, 9, 0, 20, 11];
quickSort(arr);
console.log("arr:", arr);

参考资料

66道前端算法面试题附思路分析助你查漏补缺

十大经典排序算法：

https://www.cnblogs.com/onepixel/articles/7674659.html

https://www.cnblogs.com/beli/p/6297741.html

https://www.cnblogs.com/liyongshuai/p/7197962.html

# 排序算法

# 1. 直接插入排序

# 2. 选择排序

# 3. 冒泡排序

# 4. 快速排序