排序算法

2019更新

function swap(A,i,j){
  [A[i],A[j]] = [A[j],A[i]]
}

冒泡排序（O(n^2)）

从第一个开始俩俩比较，大的放到后边，一轮之后，最大的数字就冒泡到了最后边。
然后开始第二轮比较。。。。。直到所有数字排序完成

代码实现

/*
A:要排序的数组
返回值：无
*/
function bubbleSort(A) {
  for(let i = A.length - 1; i>=0; i--){
    for(let j = 1;j<=i; j++){
      A[j]>A[j-1] && swap(A,j-1,j)
    }
  }
}

选择排序（O(n^2)）

假设第一个是最小的，依次和其他的比较，如果比第一个小，就交换位置。。。。。
最终就按照从大到小的顺序排好了
代码实现

/*
A:要排序的数组
返回值：无
*/
function section_sort(A) {
  for (let i = 0; i < A.length - 1 /*轮数*/; i++) {
    let min = i;
    for (let j = i + 1; j < A.length; j++) {
      if (A[min] > A[j]) {
        min = j;
      }
    }
    swap(A,min,i)
  }
}

插入排序（O(n^2)）

思路，首先来实现一个向已排序的数组中插入一个元素的函数,然后就是遍历了，非常简单

/*
A:已排序的数组
x:要插入的数字
*/

function insert (A,i,x){
  //p:指向下一个需要比较的元素
  //p+1：下一个空位
  let p = i - 1
  while(p>=0 && A[p]>x){
    A[p+1] = A[p]
    p--
  }
  A[p+1] = x
}

//test
let arr= [1,2,4,5,6,7]
let x = 3
insert(arr,arr.length,3)//[1, 2, 3, 4, 5, 6, 7]

代码实现

/*
A:要排序的数组
返回值：无
*/
function insertion_sort(A){
  for(let i = 0;i<A.length;i++){
    insert(A,i,A[i])
  }
}

归并排序 (O(nlogn))

归并排序分为俩部分，拆分和合并，是一种分治法
思路：去一个中心点，把数组分成两个左闭右开区间，递归继续拆分，直到每一部分都是一个元素
然后在合并

/*
A: 数组
p:左边开始
q:右边结束，右边开始
r:右边结束
分成两个左闭右开区间
*/
function merge(A,p,q,r){
  let A1 = A.slice(p,q)
  let A2 = A.slice(q,r)
  //添加哨兵
  A1.push(Number.MAX_SAFE_INTEGER)
  A2.push(Number.MAX_SAFE_INTEGER)
  for(let k = p,i = 0 ,j=0;k < r;k++){
    A[k] = A1[i]< A2[j]? A2[i++]:A2[j++]
  }
}
function merge_sort(A,p=0,r=A.length){
  if(r-p<2) return ;
  const q = Math.ceil((p+r)/2)
  merge_sort(A,p,q)
  merge_sort(A,q,r)
  merge(A,p,q,r)
}

快速排序

function partition(A,lo,hi){
  //小于中心点的范围[lo,i)
  //为确认的区间[i,j)
  //大于中心点的区间
  //中心点
  const pivot = A[hi-1]
  let i = lo, j = hi-1
  while(i!==j){
    if(A[i]<=pivot){
      i++
    }else {
      swap(A,i,--j)
    }
  }
  swap(A,j,hi-1)
  return j
}
function quick_sort(A,lo=0,hi=A.length){
  if(hi-lo<=1) return ;
  const p = partition(A,lo,hi)
  quick_sort(A,lo,p)
  quick_sort(A,p+1,hi)
}

计数排序（O(n+max)）

思路：分为三步，
1.遍历 原数组A,放到数组B中计数
2. 遍历数组 B记录每一个的位置
3. 遍历原数组A,根据B中存的位置，把元素还原到数组C

/*
A:原数组
B:累加数组
C:结果数组
*/
function counting_sort(A){
  const max= Math.max(...A)
  const B = Array(max+1).fill(0)
  const C = Array(A.length)
  for(let i = 0; i < A.length ; i++){
    B[A[i]]++
  }
  for(let i = 1; i < B.length;i++){
    B[i] += B[i-1]
  }
  for(let i = 0; i < A.length;i++){
    const p = --B[A[i]]
    C[p]  = A[i]
  }
  return C;
}

基数排序（O(n+m)）

基数：比如十进制的基数就是 10，所以准备 10 个桶（0-9），判断个位数属于哪个桶，放到对应的桶中，然后出桶（先进先出这样就是从小到大），然后按照 10 位数入桶出桶，依次百位，千位。。。。。。

/*
A:数字
返回值:无
*/
function radix_sort(A) {
  const max = Math.max(...A);
  const buckets = Array.from({ length: 10 }, () => []);
  let m = 1;
  while (m < max) {
    A.forEach(number => {
      const digit = ~~((number % (m * 10)) / m);
      buckets[digit].push(number);
    });

    let j = 0;
    buckets.forEach(bucket => {
      while (bucket.length > 0) {
        A[j++] = bucket.shift();
      }
    });
    m *= 10;
  }
}

桶排序（O(n+max)）

假设每个桶放 10 个数字（比如 1-9，10-19 这样的），判断数字应该属于哪个桶，对每个桶排序，然后出桶放到数组里就可以了

/*
A:数组
K:桶的数量
S:每个桶中的数量
*/

function bucketSort(A,K,S) {
   const buckets = Array.from({ length: k }, () => []);
  for( let i = 0; i<A.length; i++){
    const index = ~~(A[i]/S)
    buckets[index].push(A[i])
  }
  for(let i = 0;i<buckets.length;i++){
    insertion_sort(buckets[i])
  }
  return [].concat(...buckets)
}

希尔排序（O(nlogn)）

分成若干个子数组分别进行插入排序，继续分组排序，最后就所有一起排序
比如一开始分为四组，每组 2 个元素，第二轮分成俩组，每组 4 个元素，最后一次
一组排序

//>>右移运算符，比如，1111（15）右移一位就是111（7）也就类似于除以2，向下取整
function shellSort(arr) {
  var temp;
  var len = arr.length;
  for (var gap = len >> 1; gap > 0; gap = gap >>= 1) {
    for (var i = gap; i < len; i++) {
      temp = arr[i];
      for (j = i - gap; j >= 0 && arr[j] > temp; j -= gap) {
        arr[j + gap] = arr[j];
      }
      arr[j + gap] = temp;
    }
    console.log(arr);
  }
}

堆排序 （O(nlogn)）

利用最大堆让最大的数字到堆顶，思路越简单代码越难写。。。。

var len; // 因为声明的多个函数都需要数据长度，所以把len设置成为全局变量

function buildMaxHeap(arr) {
  // 建立大顶堆
  len = arr.length;
  for (var i = Math.floor(len / 2); i >= 0; i--) {
    heapify(arr, i);
  }
}

function heapify(arr, i) {
  // 堆调整
  var left = 2 * i + 1,
    right = 2 * i + 2,
    largest = i;

  if (left < len && arr[left] > arr[largest]) {
    largest = left;
  }

  if (right < len && arr[right] > arr[largest]) {
    largest = right;
  }

  if (largest != i) {
    swap(arr, i, largest);
    heapify(arr, largest);
  }
}

function swap(arr, i, j) {
  var temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}

function heapSort(arr) {
  buildMaxHeap(arr);

  for (var i = arr.length - 1; i > 0; i--) {
    swap(arr, 0, i);
    len--;
    heapify(arr, 0);
  }
  return arr;
}