常见排序算法

插入排序

  1. function sort(arr) {
  2.     if (!arr.length || arr.length <=1) return arr
  3.   for (let i = 1; i< arr.length; i++) { // 假设第一个已经被定了
  4.       let j = i - 1 // 找到上一位已经排序好的项目进行开始对比
  5.     let item = arr[i] // 记录一下当前这个值
  6.     while(j >=0 && arr[j] > item ) { // 往前对比，j>=0;且所对比的数值如果大于当前数值的话
  7.          // 说明还可以往下走、并且将对比的值和当前值调换一下位置
  8.       arr[j+1] = arr[j]
  9.       j--
  10.     }
  11.     // 直到遍历完，确认到j的值、将当前的值赋给j所在的位置
  12.     arr[j+1] = item // 因为最后一下j--，所以当前的值需要补多一位才是真实的j位置
  13.   }
  14. }

快速排序

  1. function sort(arr) {
  2.   let len = arr.length
  3.     if (len <=1) return (arr || [])
  4.   let left = [], right = [], pivot = Math.floor(len/2);
  5.   for (let i =0; i< len; i++) {
  6.       if (arr[i] <=arr[pivot]) {
  7.         left.push(arr[i])
  8.     } else {
  9.         right.push(arr[i])
  10.     }
  11.   }
  12.   return sort(left).concat(arr[pivot], sort(right))
  13. }



冒泡排序

  1. // 从前面往后面确认
  2. function sort(arr) {
  3.   let len = arr.length
  4.     if (len <=1) return (arr || [])
  5.     for (let i =0; i<len; i++) {
  6.       for (let j= i+1; j< len; j++) {
  7.         if (arr[i] > arr[j]) {
  8.           [arr[i], arr[j]] = [arr[j], arr[i]] // 交换值
  9.       }
  10.     }
  11.   }
  12.   return arr
  13. }
  16. // 相近的两两对比
  17. function sort(arr) {
  18.     let len = arr.length
  19.     if (len <=1) return (arr || [])
  20.     for(let i = 0; i<len - 1; i++) {
  21.       for (let j = 0; j< len - 1 -i; j++) { // 因为在对比中会出现arr[j+1]，往后取多一位，所以len-1是需要的，不然会报错
  22.         if (arr[j] > arr[j+1]) {
  23.           [arr[j], arr[j+1]] = [arr[j+1], arr[j]]
  24.       }
  25.     }
  26.   }
  27.   return arr
  28. }



选择排序

  1. function sort () {
  2.   let len = arr.length
  3.     if (len <=1) return (arr || [])
  4.     for (let i=0; i<len; i++) {
  5.     let index = i
  6.       for (let j=i+1; j<len;j++) {
  7.         if (arr[j]<arr[i]) {
  8.           index = j
  9.       }
  10.     }
  11.     [arr[i], arr[index]] = [arr[index], arr[i]]
  12.   }
  13.   return arr
  14. }

希尔排序

  1. function shellsort(arr) {
  2.     let len = arr.length
  3.   if(len<=1) return arr
  4.   for(let gap = Math.floor(len/2); gap >=1;gap = Math.floor(gap/2)) { // 遍历gap
  5.       // 拿到gap后，针对分组进行按照插入排序法处理
  6.     for(let i = gap; i<len; i++) {
  7.       // 下面思维是插入算法的思维，获取当前下标数据和上一个进行大小对比
  8.        let current_ele = arr[i] // 第一次循环获取这一组中的下标为1的数，往前对比；后续循环可以理解为获取下一个
  9.        let before_index = i - gap // 第一次循环获取这一组中上一个0个，后续循环可以理解为相对i的上一个，
  10.        while (before_index >= 0 && arr[before_index] > current_ele) {
  11.         arr[before_index + gap] = arr[before_index] // 将大的数据往后挪一个空位
  12.         before_index -= gap
  13.       }
  14.       arr[before_index + gap] = current_ele // 将数据插入合适的index位置
  15.     }
  16.   }
  17.   return arr
  18. }


归并排序

  1. function merge (left, right) {
  2.   let result = []
  3.     while(left.length && right.length) {
  4.     // 获取数组的第一个，并且改变原有数组的长度
  5.       if (left[0] < right[0]) {
  6.         reuslt.push(left.shift()) 
  7.     } else {
  8.             reuslt.push(right.shift())    
  9.     }
  10.   }
  11.   if (left.length) result = result.concat(left)
  12.   if (right.length) result = result.concat(right)
  13.   return result
  14. }
  15. function sort(arr) {
  16.     let len = arr.length
  17.   if (len < 2) return arr
  18.   // 找到二分位置
  19.   let midIndex = Math.floor(len/2)
  20.   let left = arr.slice(0, midIndex)
  21.   let right = arr.slice(midIndex, len)
  22.   return merge(sort(left), sort(right)) // 递归调用
  23. }


参考：图文详解_