1. 冒泡排序

算法步骤：

  • 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
  • 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
  • 针对所有的元素重复以上的步骤，除了最后一个。
  • 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
  1. /**
  2.  * 算法步骤：
  3.  * 1.比较相邻的元素。如果第一个比第二个大，交换他们两个
  4.  * 2.对每一对相邻元素做同样的操作，从开始第一对到结尾的最后一对。这步做完，最后的元素会是最大的数。
  5.  * 3.针对所有的元素重复以上操作，除了最后一个
  6.  * 4. 持续每次对越来越少的元素重复上面的步骤，直到没有仍和一对数字需要比较。
  7.  */
  9. function bubbleSort(arr) {
  10.     let len = arr.length;
  12.     for(let i=0;i<len -1 ; i++) {
  13.         for(let j=0;j<len -1 -i;j++) {
  14.             if(arr[j] > arr[j+1]) {
  15.                 let temp = arr[j+1];
  16.                 arr[j+1] = arr[j];
  17.                 arr[j] = temp;
  18.             }
  19.         }
  20.     }
  22.     return arr
  23. }
  25. console.log(bubbleSort([1,3,9,12,4,5]))

2. 选择排序

选择排序是一种简单直观的排序算法，无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候，数据规模越小越好。

算法步骤：

  • 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
  • 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
  • 重复第二步，直到所有元素均排序完毕。

排序算 - 图1

function selectionSort(arr) {
    var len = arr.length;
    var minIndex, temp;

    for(var i=0;i<len-1;i++) {
        minIndex=i;
        for(var j=i+1;j<len;j++) {
            if(arr[j]<arr[minIndex]) {
                minIndex = j
            }
        }

        temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }

    return arr
}

console.log(selectionSort([1,3,9,12,4,5]))

3. 插入排序

它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入，从而达到排序的效果。
排序算 - 图2
算法步骤：

  • 将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
  • 从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）

https://zhuanlan.zhihu.com/p/120693682

const a = [1, 3, 6, 3, 23, 76, 1, 34, 222, 6, 456, 221];

function insertSort(arr) {
  const len = arr.length;
  let current, prevIndex;
  for (let i = 1; i < len; i++) {
    current = arr[i];
    prevIndex = i - 1;
    // 当前一个大于当前项时
    while (prevIndex >= 0 && arr[prevIndex] > current) {
      arr[prevIndex + 1] = arr[prevIndex];
      prevIndex--;
    }

    arr[prevIndex + 1] = current;
  }

  return arr;
}

console.log(insertSort(a));

4. 快速排序

  • 快排为啥叫快排，快排是所有排序里面性能最好的吗？
  • 快排适合什么情况呢，还是无论什么情况下快排总是最好？
  • 快排算法的思想是什么？其性能优良的原因是依赖于算法中的哪个部分？


快排的性能在所有排序算法里面是最好的，数据规模越大快速排序的性能越优。快排在极端情况下会退化成 排序算 - 图3 的算法，因此假如在提前得知处理数据可能会出现极端情况的前提下，可以选择使用较为稳定的归并排序。

算法步骤

  1. 从数列中挑出一个元素，称为 “基准”（pivot）;
  2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
  3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序； ```javascript const arr = [5, 2, 7, 8, 34, 7, 39, 12, 56, 9, 1]

function quickSort(arr) { if(arr.length<=1) { return arr }

const middleIndex = Math.floor(arr.length / 2);

const middle = arr.splice(middleIndex,1)[0];

let leftArr = [], rightArr = []; for(let i=0; i < arr.length; i++) { const current = arr[i]; current < middle ? leftArr.push(current) : rightArr.push(current) }

return quickSort(leftArr).concat(middle,quickSort(rightArr)) } ```

https://www.runoob.com/w3cnote/ten-sorting-algorithm.html