1. 冒泡排序

var arr = [1,56,9,6,3,5,8,2]
function sort(arr){
  for(let i = 0;i<arr.length-1;i++){
    for(let j = 0;j<arr.length-1-i;j++){
      if(arr[j]>arr[j+1]){
        let temp = arr[j+1];
        arr[j+1] = arr[j];
        arr[j] = temp
      }
    }
  }
  return arr
}
sort(arr)
console.log(arr);

2. 插入排序

var arr = [1,56,9,6,3,5,8,2]
function sort(arr){
  for(var i =1;i<arr.length;i++){
    var val = arr[i];
    var last = i-1;
    while(last>=0 && arr[last]>val){
      arr[last+1] = arr[last]
      last--
    }
    arr[last+1] = val
  }
  return arr
}
sort(arr)
console.log(arr);

3. 快速排序

var arr = [1,56,9,6,3,5,8,2]
function quickSort(arr){
  if(arr.length<2){
    return arr
  }
  var mid = Math.floor(arr.length/2)
  var pivot = arr.splice(mid,1)[0]
  var left = [];
  var right = [];
  for(var i = 0;i<arr.length;i++){
    if(arr[i]<pivot){
      left.push(arr[i])
    } else {
      right.push(arr[i])
    }
  }
  return quickSort(left).concat(pivot,quickSort(right))
}

console.log(quickSort(arr));

4. 归并排序

var arr = [1,56,9,6,3,5,8,2];
function mergeSort(arr) {
  var len = arr.length
  if(len<2){
    return arr
  }
  var mid = Math.floor(arr.length/2)
  var left = arr.slice(0,mid)
  var right = arr.slice(mid)
  return merge(mergeSort(left),mergeSort(right))
}
function merge(left,right) {
  var result = []
  while(left.length>0 && right.length>0){
    if(left[0]>right[0]){
      result.push(right.shift())
    } else {
      result.push(left.shift())
    }
  }
  while(left.length){
    result.push(left.shift())
  }
  while(right.length){
    result.push(right.shift())
  }
  arr = result
  return arr
}
mergeSort(arr)
console.log(arr);

5. 希尔排序

var arr = [1,56,9,6,3,5,8,2]
function sort(arr){
  var gap = arr.length
  for(gap = Math.floor(arr.length/2);gap>0;gap = Math.floor(gap/2)){
    for(var i=gap;i<arr.length;i++){
      var val = arr[i];
      var  j = i;
      while(j-gap>=0 && arr[j-gap]>val){
        arr[j] = arr[j-gap]
        j = j-gap
      }
      arr[j] = val
    }
  }
  return arr
}
sort(arr)
console.log(arr);

6. 堆排序

var arr = [1,56,9,6,3,5,8,2]
var len; 
function buildMaxHeap(arr) {
  len = arr.length
  for(var i = 0;i<Math.floor(arr.length/2);i++){
    heapify(arr,i)
  }
}
function heapify(arr,i){
  var left = i*2+1;
  var right = i*2+2;
  var 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--){
    len-=1;
    swap(arr,0,i)
    heapify(arr,0)
  }
  return arr
}
console.log(heapSort(arr));

7. 计数排序

var arr = [1,56,9,6,3,5,8,2];
function countingSort(arr, maxValue){
  var bucket = new Array(maxValue+1)
  var index = 0
  for(var i =0;i<arr.length;i++){
    if(!bucket[arr[i]]){
      bucket[arr[i]] = 0
    }
    bucket[arr[i]]++
  }
  for(var j = 0;j<bucket.length;j++){
    while(bucket[j]>0){
      arr[index++] = j
      bucket[j]--
    }
  }
  return arr
}
console.log(countingSort(arr,56));

8. 选择排序

var arr = [1,56,9,6,3,5,8,2]
function sort(arr){
  for(let i =0;i<arr.length-1;i++){
    var index
    let min = i
    for(let j = i+1;j<arr.length;j++){
      if(arr[j]<arr[min]){
        min = j
      }
    }
      var temp = arr[i];
      arr[i] = arr[min];
      arr[min] = temp
  }
  return arr
}
sort(arr)
console.log(arr);