用JS 做排序算法

var arr = [12,4,6,78,26,8,93,12,34,54,46,87,90]

1. 冒泡排序

比较相邻两个数，大的向后移。

function bubbleSort(arr){
  let temp = 0
  for(let j = arr.length-1;j>0;j--){
    for(let i = 0;i<j;i++){
      if(arr[i]>arr[i+1]){
        temp = arr[i]
        arr[i] = arr[i+1]
        arr[i+1] = temp
      }
    }
  }
}

2. 选择排序

每一轮循环找出最小的数放在前面.

function selectionSort(arr){
  var temp = 0
  var min = 0
  for(var i = 0;i<arr.length-1;i++){
    min = i
    for(var j = i+1;j<arr.length;j++){
      if(arr[min]>arr[j]){
        min = j
      }
    }
    if(min !== i){
      temp = arr[i]
      arr[i] = arr[min]
      arr[min] = temp
    }
  }
}

3. 插入排序

拿出第二个数，记住他的值为本轮循环需要插入的值，如果前一个比这个值大，那么前一个数的位置+1，自己的位置-1。直到比较到位置0的数。如果没他大，则位置正确。再拿第三个数往前插，直到最后一个数插完。

function insetSort(arr){
  var temp = 0
  var position
  for(var i =1;i<arr.length;i++){
    var position = i
    var value = arr[i]
    while(position>0 && arr[position-1]>value){
      arr[position] = arr[position -1]
      position --
    }
    arr[position] = value
  }
}

4. 快速排序

1.以第一个数为基准数，右边开始往左找，找到小于基准数的数停下来,然后左边开始向右找，找到大于基准数的数停下来。
2.交换位置
3.直到两边相遇，交换当前数和基准数位置
4.对基准数左右两边递归执行同样的操作，直到所有基准数到位。
注意! 必须右边先开始，这样相遇时的数必定小于基准数。

function quickSort(arr){
  sort(0,arr.length-1)
 
  function sort(left,right){
    var i = left
    var j = right
    var t
    var temp = arr[left]
    while(i!==j){
      while(i<j && arr[j]>=temp){j--}
      while(i<j && arr[i]<=temp){i++}
      //交换两边的数
      if(i<j){
        t = arr[i]
        arr[i] = arr[j]
        arr[j] = t
      }
    }
    //i和j相等时while循环结束，交换基准数
    arr[left] = arr[i]
    arr[i] = temp
    //继续处理基准数左边和右边
    if(left < i-1){sort(left,i-1)}
    if(i+1 < right){sort(i+1,right)}
  }
} 

5. 计数排序，

把数组里的每个数作为hash的key，相同数出现的次数作为value。最后遍历hash一个个取出来。复杂度为O(n + max) max 为数组里最大的那个数

function countSort(arr){
  var hash = {}
  var temp = []
  var max = arr[0]
  var min = arr[0]
  for(let i = 0;i<arr.length;i++){
    if(!hash[arr[i]]){
      hash[arr[i]] = 1
      if(arr[i]>max){max = arr[i]}
      if(arr[i]<min){min = arr[i]}
    }else{
      hash[arr[i]] +=1
    }
  }
  for(let j = min;j<=max;j++){
    while(hash[j]>0){
      temp.push(j)
      hash[j]--
    }
  }
  return temp
}