排序：桶排序、冒泡排序、快速排序

拜读《啊哈算法》后的内容笔记。

简易的桶排序

[真正的桶排序并非如此简单]
原理：将数组中的某个数，例如6，则将结果arr[6]+=1
如图：
5，2，4，5，7，2，1
||
/
a[5]=1,a[2]=1,a[4]=4,a[5]=2a[7]=7,a[2]=2,a[1]=1
||
/
a[0,1,2,0,1,2,0,1]
||
/
1,2,2,4,5,5,7

const arrNum = [9, 3, 2, 1, 8, 7, 3]
const arr = []
for (let i = 0; i <= 10; i += 1) {
  arr[i] = 0
}
for (let j = 0; j < arrNum.length; j += 1) {
  arr[arrNum[j]] += 1
}
for (let x = 0; x < arr.length; x += 1) {
  for (let y = 1; y <= arr[x]; y += 1) {
    console.log(x)
  }
}

1 2 3 3 7 8 9 

关于时间复杂度O，你看第三行for循环，可见循环了M次，（M为桶的个数），第6行代码循环N次（N为待排序数的个数），第9，10行，一共循环了M+N次，所以整个排序算法执行M+N+M+N，因此O（2×（M+N）），处理时间复杂度时，可以忽略较小的常数，最终时间复杂度为O（M+N）

冒泡

老生常谈的冒泡
原理：相邻的两个数字进行比较后调换位置

for (let i = 1; i < arrNum.length; i += 1) {
 for (let j = 0; j < arrNum.length - i; j += 1) {
   if (arrNum[j] > arrNum[j + 1]) {
     let tmp
     tmp = arrNum[j]
     arrNum[j] = arrNum[j + 1]
     arrNum[j + 1] = tmp
   }
 }
}
console.log(arrNum)

[ 1, 2, 3, 3, 7, 8, 9 ]

书上提到了关于输入N个人名与分数，如何根据分数进行排序。我就用obj来实现了：

const obj = [{name: 'walk', score: 99}, {name: 'wa1lk', score: 939}, {name: 'wal1k', score: 929}]
for (let i = 1; i < obj.length; i += 1) {
  for (let j = 0; j < obj.length - i; j += 1) {
    if (obj[j].score > obj[j + 1].score) {
      tmp = obj[j]
      obj[j] = obj[j + 1]
      obj[j + 1] = tmp

    }
  }
}
console.log(obj)

[ { name: 'walk', score: 99 },
  { name: 'wal1k', score: 929 },
  { name: 'wa1lk', score: 939 } ]

快速

原理：有点类似于二分法，找到一个基准数，然后与后面的数字进行对比，将小于自己的数字放入左边的数组，大于自己的数字放入右边的数组，然后用concat连接。

const arrNum = [9, 3, 2, 1, 8, 7, 3]
const qSort=(arr)=>{
  if (arr.length===0){
    return []
  }
  let left=[]
  let right=[]
  let pivot=arr[0]
  for (let i=1;i<arr.length;i+=1){
    if (arr[i]<pivot){
      left.push(arr[i])
    }else {
      right.push(arr[i])
    }
  }
  return qSort(left).concat(pivot,qSort(right))
}
console.log(qSort(arrNum))

[ 1, 2, 3, 3, 7, 8, 9 ]