快速排序

  1. function quicksort(arr) {
  2.   if (arr.length <= 1) return arr;
  3.   let midIndex = arr.length >> 1;
  4.   let mid = arr.splice(midIndex, 1)[0];
  5.   // [4, 3, 5, 2, 1, 6]
  6.   console.log(midIndex,mid);
  7.   let left = [];
  8.   let right = [];
  9.   for (let i = 0; i < arr.length; i++) {
  10.     if (arr[i] <= mid) {
  11.       left.push(arr[i])
  12.     } else {
  13.       right.push(arr[i])
  14.     }
  15.   }
  16.   return quicksort(left).concat(mid, quicksort(right))
  17. }
  19. console.log(quicksort([4, 3, 5, 2, 1, 6]));   //  [1, 2, 3, 4, 5, 6]

归并排序

  1. function merge(left,right){
  2.         let res=[]
  3.         while(left.length>0 && right.length>0){
  4.             if(left[0]<right[0]){
  5.                 res.push(left.shift())
  6.             }else{
  7.                 res.push(right.shift())
  8.             }
  9.         }
  10.         return res.concat(left).concat(right)
  11.     }
  12.     function mergeSort(arr){
  13.         if(arr.length==1) return arr
  14.         // let mid=Math.floor(arr.length/2)
  15.         let mid= arr.length>>1
  16.         let left=arr.slice(0,mid)
  17.         let right=arr.slice(mid)
  18.         return merge(mergeSort(left),mergeSort(right))
  19.     }
  20.     console.log(mergeSort([3,2,4,5,1,7,6]));

插入排序

  1. function insertSort(arr) {
  2.   for (let i = 1; i < arr.length; i++) {
  3.     let j = i - 1    
  4.     const tmp = arr[i]
  5.     while (j >= 0 && arr[j] > tmp) {
  6.       arr[j + 1] = arr[j]// 移动
  7.       j--
  8.     }
  9.     // 放入合适位置
  10.     arr[j + 1] = tmp
  11.   }
  12.   return arr
  13. }
  14. console.log(insertSort([3, 2, 4, 5, 1, 6]));

选择排序

  1. function selectSort(arr){
  2.   for(let i=0;i<arr.length;i++){
  3.     let minIndex=i
  4.     for(let j=i+1;j<arr.length;j++){
  5.       if(arr[j]<arr[minIndex]){
  6.         minIndex=j
  7.       }
  8.     }
  9.     const tmp=arr[i]
  10.     arr[i]=arr[minIndex]
  11.     arr[minIndex]=tmp
  12.   }
  13.   return arr
  14. }  
  15. console.log(selectSort([3,2,4,5,1,7,6]));

希尔排序

  1. function shellSort(array) {
  2.   const len = array.length;
  3.   let gap = Math.floor(len / 2);
  4.   for (gap; gap > 0; gap = Math.floor(gap / 2)) {
  5.     for (let i = gap; i < len; i++) {
  6.       let j = i - gap;
  7.       const temp = array[i];
  8.       while (j >= 0 && array[j] > temp) {
  9.         array[j + gap] = array[j];
  10.         j -= gap;
  11.       }
  12.       array[j + gap] = temp;
  13.     }
  14.   }
  15.   return array;
  16. }

堆排序

  1. function heapSort(array) {
  2.   for (let i = Math.floor(array.length / 2 - 1); i >= 0; i--) {
  3.     adjustHeap(array, i, array.length);
  4.   }
  5.   for (let j = array.length - 1; j > 0; j--) {
  6.     const temp = array[0];
  7.     array[0] = array[j];
  8.     array[j] = temp;
  9.     adjustHeap(array, 0, j);
  10.   }
  11.   return array;
  12. }
  14. function adjustHeap(array, i, length) {
  15.   for (let j = 2 * i + 1; j < length; j = 2 * j + 1) {
  16.     const temp = array[i];
  17.     if (j + 1 < length && array[j] < array[j + 1]) {
  18.       j++;
  19.     }
  20.     if (temp < array[j]) {
  21.       array[i] = array[j];
  22.       array[j] = temp;
  23.       i = j;
  24.     } else break;
  25.   }
  26. }