排序算法总结

冒泡排序

---

function maopao(arr){
      let  len = arr.length
      for (let i = 0; i < len-1; i++) {
          for (let j = i; j < len-1-i; j++) {
                if(arr[j]>arr[j+1]){
                  let temp = arr[j]
                  arr[j] = arr[j+1]
                  arr[j+1] = temp
                }
          }
      }
      return arr
}
// console.log(maopao([4,1,2,5,7]))

选择排序

---

function selectSort(arr){
      let len = arr.length
      let minIndex
      let temp
      for (let i = 0; i < len-1; i++) {
            minIndex = i
            for (let j = 1+i; j < len; j++) {
                  if(arr[j]<arr[minIndex]){
                        minIndex = j
                  }
            }
            temp = arr[i]
            arr[i] = arr[minIndex]
            arr[minIndex] = temp
      }
      return arr
}
// console.log(selectSort([3,1,2,5,3,8]))

插入排序

---

function insertSort(arr){
      let len = arr.length
      let preIndex
      let current
      let temp
      for (let i = 1; i < len; i++) {
            preIndex = i-1
            current =arr[i] 
            while(preIndex>=0&&arr[preIndex]>current){
                  arr[preIndex+1] = arr[preIndex]
                  preIndex--
            }
            arr[preIndex+1] = current
      }
      return arr
}
// console.log(insertSort([3,1,5,2,6]))

归并排序

---

function mergeSort(arr){
      let len = arr.length
      if(len<2){
            return arr
      }
      let middle = Math.floor(len/2)
      let left = arr.slice(0,middle)
      let right = arr.slice(middle)
     return merge(mergeSort(left),mergeSort(right))
}
function merge(left,right){
      var result = []
      while(left.length && right.length){
            if(left[0]<=right[0]){
                  result.push(left.shift())
            }else{
                  result.push(right.shift())
            }
      }
      while(left.length){
            result.push(left.shift())
      }
      while(right.length){
            result.push(right.shift())
      }
     return result
}

希尔排序

---

function shellSort(arr){
      let len = arr.length
      let temp
      let gap = 1
      while(gap<len/3){
            gap = gap*3+1
      }
      for (gap; gap>0; gap = Math.floor(gap/3)) {
            for (let i = gap; i < len; i++) {
                  temp = arr[i]
                  let j
                  for ( j = i-gap; j>=0&&arr[j]>temp; j-=gap) {
                        arr[j+gap] = arr[j]
                  }
                  arr[j+gap] = temp
            }
      }
      return arr
}
// console.log(shellSort([3,1,2,5,4,6,9,7]))

快速排序

---

function quickSort(arr){
    let len = arr.length
    if(len<2){
        return arr
    }
    let pivotIndex = Math.floor(len/2)
    let pivot = arr.splice(pivotIndex,1)[0]
    let left = []
    let right = []
    arr.forEach(e => {
        if(e<pivot){
            left.push(e)
        }else{
            right.push(e)
        }
    });
    return quickSort(left).concat(pivot,quickSort(right))
}
// console.log(quickSort([4,2,6,1,8,7]))

堆排序

---

function swap(A,i,j){
    let temp = A[i]
    A[i] = A[j]
    A[j] = temp
}
function shiftDown(A,i,length){
    let temp = A[i]
    for (let j=2*i+1; j<length; j=2*j+1) {
        temp = A[i]
        if(j+1<length&&A[j]<A[j+1]){
            j++
        }
        if(temp<A[j]){
            swap(A,i,j)
            i=j
        }else{
            break
        }        
    }
}
function heapSort(A){
    for(let i=Math.floor(A.length/2-1);i>=0;i--){
        shiftDown(A,i,A.length);
    }
    for (let i = Math.floor(A.length-1); i>0;i--) {
        swap(A,0,i)
        shiftDown(A,0,i)
    }
}
var aa = [5,1,3,6,3,7,5]
heapSort(aa)
console.log(aa)