快速排序

快速排序就是在一个数组中选择一个基准数值，为了方便理解一般选择数组中间的数值，然后循环数组，将小于基数的数值放在基数的左边，大于基数的数值放在基数的右边。然后将左右两边的数值同时重复以上操作，就能够实现排序的目的了。
快速排序是最常用的一种排序方式，因为它使用起来的时间复杂度较之其它的排序方式比起来更简单。具体代码如下

  1. function quicksort (arr) {
  2.   // 如果数组中数值的数量小于等于1，说明这个数组已经完成排序，直接返回该数组。
  3.   if (arr.length <= 1) {
  4.     return arr;
  5.   }
  6.   const index = Math.floor(arr.length / 2); // 数组的中间值的索引
  7.   const pivot = arr.splice(index, 1)[0]; // 数组的中间值 也就是排序的基数
  8.   const left = []; // 用来保存小于基数部分的数组
  9.   const right = []; // 用来保存大于基数部分的数组
  10.   // 循环遍历数组，如果小于基数就追加到左半部分，如果大于基数就追加到右半部分
  11.   for (let i = 0; i < arr.length; i++) {
  12.       if (arr[i] < pivot) {
  13.       left.push(arr[i]);
  14.     } else {
  15.       right.push(arr[i]);
  16.       }
  17.   }
  18.   // 通过递归调用的方式，返回排序之后的数值，同时使用扩展运算符展开并拼接数组
  19.   return [...quicksort(left), pivot, ...quicksort(right)]
  20. }
  22. // 使用第一个元素为基数可以简化代码空间
  23. function sort(num) {
  24.   if (num.length <= 1) {return num}
  25.   let index =  num.shift(),left = [], right = [];
  26.   num.forEach(val => val > index ? right.push(val) : left.push(val));
  27.   return [...sort(left), index, ...sort(right)]
  28. }

快速选择

如果我们只需要对应位置的数据，那么排序好再取出是一件浪费的事情，更好的做法是使用快速选择，基于快速排序的原理，进行选择上的优化，例如当我们想要选择第七位的数字时

  • 如果左侧数组长度为 6 时，我们当前选择的数字正好是第七位，那么我们直接返回当前数字即可
  • 如果左侧数组长度小于 6，代表我们想要选择的数字在右侧的数组中，那么我们只需要递归右侧数组即可
  • 如果左侧数组长度大于 6，代表我们想要选择的数字在左侧的数组中，我们仅需要递归左侧数组即可
    1. function quickQuery(num, index) {
    2.   let reference = num.shift(), left=[], right=[];
    3.   num.forEach(val => val > reference ? right.push(val) : left.push(val));
    4.   return left.length === index - 1 ? reference : left.length < index ? quickQuery(right, index - left.length - 1) : quickQuery(left, index);
    5. }

    冒泡排序

    冒泡排序就是从第一个数开始遍历，遇到小的位置不变继续向下循环，遇到大的则交换位置后再往前循环，因为是一层一层的从前往后遍历，看起来就像冒泡一样，所以称为冒泡排序。
    1. function buttlesort (arr) {
    2. for (let i = 0; i < arr.length - 1; i++) {
    3.   let flag = true; // 定义一个节流阀，当节流阀为true时，即表示当前循环无需交换位置，代表着所有数值已经全部排好序了。
    4.   for (let j = 0; j < arr.length - 1 - i; j++){
    5.     // 此处因为当i交换到最后一位时，即代表它为当前数组的最大值，下次循环时无需再和它做断。
    6.     if (arr[j] > arr[j + 1]) {
    7.       [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
    8.       flag = false;
    9.     }
    10.   }
    11.   if (flag) {
    12.     break;
    13.   }
    14. }
    15. return arr;
    16. }

    选择排序

    选择排序可以说是最简单直观的排序算法了。它是一遍遍的循环数组，找到整个数组中的最小值，然后放到数组的起始位往后
    1. function selectionSort (arr) {
    2.   let minIndex;  // 用来保存数组中的最小值索引
    3. // 这里因为当我们循环到倒数第二轮时，因为倒数第二位已经和倒数第一个比较过了，所以没有必要再进行一次循环了
    4.   for (let i = 0; i < arr.length - 1; i++) {
    5.       minIndex = i;  // 将当前i的值赋值为最小值
    6.   // 我们的i之前的所有数已经按照从小到大的顺序排好了，所以第二层循环从i + 1 开始就行了
    7.       for (var j = i + 1; j < arr.length; j++) {
    8.           if (arr[j] < arr[minIndex]) {
    9.               minIndex = j;
    10.           }
    11.       }
    12.       [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
    13.   // 如果当前位置的值小于最小值，那么我们就将当前的值标记为最小值。在循环结束后将此最小值交换到循环最前端以按序排列
    14.   }
    15.   return arr
    16. }

    插入排序

    插入排序也是非常直观的一种排序方式，就是将数组按序扫描，将已扫描的数值按序排列，然后将未扫描的数值在已排序好的数值中从后往前扫描，找到自己的相应位置后插入进去
    1. function insertionSort (arr) {
    2. // 将数组中的第一个值当成已排好序的数值，从第二个数值开始循环，从后往前扫描，
    3. // 遇到大于自身的数值，两者交换位置，遇到小于自己数值的数据时，停止循环，当前位置即为按序排列好的相应位置
    4. for (let i = 1; i < arr.length; i++) {
    5.   for (let j = i; j > 0 ; j--) {
    6.     if (arr[j] >= arr[j - 1]) {
    7.       break;
    8.     }
    9.     [arr[j], arr[j - 1]] = [arr[j - 1], arr[j]]
    10.   }
    11. }
    12. return arr
    13. }
    小小的优化
    1. function insertionSort (arr) {
    2. let current, index
    3. for (let i = 1; i < arr.length; i++) {
    4.   // 对于寻找相对位置来说，不需要那么频繁的交换位置，用一个变量保存当前值，
    5.   // 遇到大于自身的，将那个值的索引加一，遇到小于自身值时，将变量的值保存在该值之后即可
    6.   index = i - 1
    7.   current = arr[i]
    8.   while (index >= 0 && arr[index] > current) {
    9.     arr[index + 1] = arr[index]
    10.     index--
    11.   }
    12.   arr[index + 1] = current
    13. }
    14. return arr
    15. }