常用的五大排序算法

冒泡排序

算法思想

冒泡排序只操作相邻的两个数据，每次冒泡会对相邻的两个元素作比较，如果不满足大小关，则交换。一次冒泡至少使得一个元素出现在其该有的位置上，重复N次就完成了数组的排序。

代码实现

function BubbleSort (arr) {
  if(arr.length <= 1) return arr;
  for(let i = 0; i < arr.length; i++) {
    let flag = false;
    for(let j = 0; j < arr.length - i - 1; j++) {
      // 每一次循环一定有一个数值到正确的位置
      if(arr[j] > arr[j + 1]) {
        [arr[j],arr[j + 1]] = [arr[j + 1],arr[j]];
        flag = true;
      }
    }
    // 没有数据交换提前退出
    if(!flag) break;
  } 
  return arr;
}

复杂度分析

冒泡排序只涉及相邻两个元素交换，只需要常量级的临时空间，即空间复杂度为O(1)，并且是一个原地排序算法。

只有交换相邻两个元素才能改变前后顺序，并且当前后两个元素相等时，我们不做交换，即相同大小的元素在排序之后不会改变顺序，所以冒泡排序是一个稳定的排序算法。

最好情况下需要排序的数组已经是排好序的只需要冒泡一次，也就是最好时间复杂度为O(n)，最坏的情况就是需要排序的数组刚好是倒序的，刚好需要冒泡n次，所以最坏的时间复杂度为O(n^2)，平均时间复杂度为O(n^2)。

插入排序

算法思想

将需要排序的数组分为两个部分已排序区域和未排序区域。初始已排序区域为数组的第一个元素。其核心在于取未排序区域中的元素插入到已排序区域的对应位置上，并保证已排序区间的数据一直有序，直至未排序区域没有元素，则排序结束。

代码实现

const InsertSort = (arr:Array<number>) => {
  if(arr.length <= 1) return arr;
  for(let i = 1; i < arr.length; i++) {  // 遍历未排序区域
    let value = arr[i];
    let j = i - 1;
    for(; j >= 0; j--) { // 查找当前元素需要插入的位置上
      if(value > arr[j]) {
        break; // 大于已排序区域直接接在已排序区域后
      } else {
        arr[j + 1] = arr[j] // 需要插入位置的元素后移一位
      }
    }
    // 插入元素 ： 循环结束后j--一次所以插入位置为arr[j + 1];
    arr[j + 1] = value;
  }
  return arr;
}

复杂度分析

插入排序不需要使用额外的临时空间，所以空间复杂度为：O(1)，是一个原地排序算法。

对于值相同的元素我们将后出现的元素插入到前面出现的元素后面，保持原有先后顺序不改变，所以插入排序也是一个稳定的排序算法。

如果需要排序的数组已经是有序的我们不需要搬移任何数据，只需要从头到尾遍历一次，每次比较只需一次就能确定插入位置，所以最好情况的时间复杂度为O(n),如果数组是倒序的，每一次相当于在数组的第一个位置插入新的数据，最坏情况时间复杂度为O(n^2)，平均时间复杂度为O(n^2)。

选择排序

算法思想

选择排序与插入排序思路有点类似，也是分为已排序区域和未排序区域，每次取未排序区域的最小值放到已排序区域的末尾，最开始已排序区域为空。

代码实现

const SelectionSort = (arr:Array<number>) => {
  if(arr.length <= 1) return arr;
  let MinIndex = 0;
  for(let i = 0; i < arr.length; i++) {
    MinIndex = i;
    for(let j = i + 1; j < arr.length; j++) {
      if(arr[j] < arr[MinIndex]) {
        // 更新最小值
        MinIndex = j;
      }
    }
    [arr[i],arr[MinIndex]] = [arr[MinIndex],arr[i]];  // 利用数组结构赋值，无序额外的临时变量来两个元素交换
  }
  return arr;
}

复杂度分析

选择排序与插入排序类似，空间复杂度为O(1)，是一种原地排序算法，但他不是稳定排序算法，因为每次选择排序都需要从未排序区域中找出最小值，并和前面的元素交换，破坏了稳定性，所以选择排序是不稳定排序算法。

时间复杂度，最好情况、最坏情况和平均时间复杂度都为O(n^2)，因为无论是不是排好序的数组，每一次选择都需要遍历未排序区域去找到最小值再交换。

归并排序

算法思想

归并排序的核心就在于，如果要排序一个数组，我们首先从中间将这个数组一分为二，前后两个部分分别继续按照前面的方法分为两部分之后分别排序，最后将排好序的两部分合并成一部分，最后整个数组就成为有序数组。

简而言之就是先将数组分解最最小的一个一个元素，再排序合并，其中包含分治的思想

代码实现

const MergeSort = (arr:Array<number>):any => {
  if(arr.length <= 1) return arr;
  const middle = Math.floor(arr.length / 2);
  return merge(MergeSort(arr.slice(0,middle)),MergeSort(arr.slice(middle)))
}

const merge = (left:Array<number>,right:Array<number>) => {
  let temp = [];
  while(left.length > 0 && right.length > 0) {
    if(left[0] < right[0]) {
      temp.push(left.shift());
    } else {
      temp.push(right.shift());
    }
  }
  return temp.concat(left).concat(right);
}

复杂度分析

归并排序在合并过程中会将元素放入数组中，保证了值相同的元素，在合并前后顺序不变，所以归并排序是一个稳定的排序算法;

时间复杂度，最好情况、最坏情况和平均时间复杂度都为O(nlogn);

在王争老师的数据结构与算法中是这么解释关于归并排序的空间复杂度的：尽管每次合并都需要申请额外的存储空间，但是合并之后临时空间就被释放了，在每一个时刻都CPU都只有一个函数在执行，也就是说只有一个临时空间在使用所以空间复杂度为O(n);

快速排序

算法思想

快速排序我们通常称之为快排，其和归并类似也是用了分治的思想，利用一个哨兵划分为三个区域，首先分为小于哨兵的数组，等于哨兵的数组，大于哨兵的数组，三个区域，再继续对三个区域采取相同的方式，哨兵一般取排序数组的第一个元素或最后一个元素。

代码实现

const QuickSort = (arr:Array<number>):any => {
  if(arr.length <= 1) return arr;
  const pivot = arr[0];  // 哨兵
  const lowerArr:Array<number> = [], pivotArr:Array<number> = [], highterArr:Array<number> = [];
  arr.forEach(item => {
    if(item === pivot) {
      pivotArr.push(item);
    } else if(item < pivot) {
      lowerArr.push(item);
    } else {
      highterArr.push(item);
    }
  });
  return QuickSort(lowerArr).concat(pivotArr).concat(QuickSort(highterArr));
}