前言

一些常用的排序算法：快速排序、冒泡排序、插入排序

JS中的排序

  1. const arr = [1,22,3,11];
  2. // 先转成字符串，按照 ASCII 的码进行排序
  3. arr.sort(); // [1,11,22,3]
  4. // 升序排序
  5. arr.sort((a, b)=> a - b)
  6. // 降序排序
  7. arr.sort((a, b)=> b - a)
  8. // 反序 arr.reverse()
  9. // 返回其他值，不排序
  10. arr.sort(()=> -1)
  11. // 自定义排序
  12. arr.sort((a, b)=>{
  13.   // 升序
  14.     if(a - b > 0) return 1;
  15.   // 降序
  16.   if(a - b < 0) return -1;
  17.   return 0
  18. })
  19. // 非 ASCII 排序
  20. arr.sort((a, b)=>{
  21.     return a.localeCompare(b);
  22. })

快速排序

平均时间复杂度是nlogn 1、挑选一个基准值 2、分割：比基准值小的放左边，比基准值大的放右边，这个过程基准值的排序就完成了 3、递归排列左右子序列

  1. function sort(arr=[]) {
  2.     if (!Array.isArray(arr) || arr.length <= 1) return arr;
  3.     const left = []
  4.       , right = [];
  5.     const midIndex = Math.floor(arr.length / 2);
  6.     const mid = arr[midIndex];
  7.     let midCount = 0;
  8.     for (let i = 0; i < arr.length; i++) {
  9.         const item = arr[i];
  10.         if (item < mid) left.push(item)
  11.         else if (item > mid) right.push(item)
  12.         else midCount++;
  13.     }
  14.     return sort(left).concat(new Array(midCount).fill(mid), sort(right));
  15. };

插入排序

时间复杂度是n2。 1、从第一个元素开始，该元素可认为已排序 2、取出下一个元素，在已排序的序列里面从后往前扫描。 3、如果该元素大于新元素，将该元素移到下一位置。 4、重复步骤三，直到找到已排序的元素小于或者等于新元素。 5、将新元素插入到该位置。 6、重复步骤 2-5

  1. function sort(arr = []){
  2.   const len = arr.length;
  3.     for(let i = 1; i < len; i++){
  4.     // 取出下一个元素
  5.       let cur = arr[i];
  6.     // 前面序列的位置，初始化是最后一个
  7.     let prevIndex = i - 1;
  8.     // 前面是已排序的，只需要找到下一个元素在已排序列的位置。
  9.     while(prevIndex >= 0 && arr[prevIndex] > cur){
  10.         arr[prevIndex + 1] = arr[prevIndex];
  11.       prevIndex--;
  12.     }
  13.     arr[prevIndex + 1] = cur;
  14.   }
  15.   return arr;
  16. }
  18. // 另一种解法
  19. function sort(arr = []){
  20.     return arr.reduce((acc, cur, curIndex)=>{
  21.       if(!acc.length) return [cur];
  22.     acc.some((prev, prevIndex)=>{
  23.       // 前面序列有大于当前值，则把当前值放置在其前面
  24.         if(prev >= cur){
  25.           acc.splice(prevIndex, 0, cur);
  26.         return true;
  27.       }
  28.       // 前面序列没有大于当前值的，把当前值放置在最后面
  29.       if(prevIndex === acc.length - 1){
  30.           acc.splice(prevIndex + 1, 0, cur);
  31.         return true;
  32.       }
  33.       return false;
  34.     })
  35.     return acc;
  36.   }, [])
  37. }

冒泡排序

时间复杂度是 n2。 1、比较相邻的元素，如果左边比右边大，交换顺序 2、每一对都执行上述比较，从开始到结束，一轮结束，最右边元素是最大元素。 3、针对所有元素执行上面操作，每轮比较元素越来越少，直到没有需要比较元素。

  1. function sort(arr = []){
  2.   const len = arr.length;
  3.   let temp = 0;
  4.     for(let i = len - 1; i > 0; i--){
  5.       let index = 0;
  6.     while(index < i){
  7.         if(arr[index] > arr[index + 1]){
  8.           temp = arr[index];
  9.         arr[index] = arr[index + 1];
  10.         arr[index + 1] = temp;
  11.       }
  12.       index++;
  13.     }
  14.   }
  15.   return arr;
  16. }

选择排序

时间复杂度是n2。 1、从未排序中找出最小值，放在第一个位置 2、从剩余未排序中找出最小值，放在已排序的末尾

  1. function sort(arr = []){
  2.   let min = arr[0], minIndex = -1,temp = 0;
  3.   const len = arr.length;
  4.     for(let i = 0; i < len; i++){
  5.     min = arr[i];
  6.     minIndex = i;
  7.         for(let j = i; j < len; j++){
  8.         if(arr[j] < min){
  9.           min = arr[j];
  10.         minIndex = j;
  11.       }
  12.     }
  13.     temp = arr[i];
  14.     arr[i] = arr[minIndex];
  15.     arr[minIndex] = temp;
  16.   }
  17.   return arr;
  18. }
  20. // 先写出书面逻辑，在用代码实现，注意边界条件。
  21. function sort(arr = []){
  22.     for(let i = 0; i < arr.length; i++){
  23.     // 求解剩余数组的最小值索引
  24.       const min = arr.slice(i + 1).reduce((index, cur, curIndex)=>{
  25.         if(arr[index] > cur) return curIndex + i + 1;
  26.       return index;
  27.     }, i);
  28.     if(i !== min) [arr[i],arr[min]] = [arr[min],arr[i]];
  29.   }
  30.   return arr;
  31. }

堆排序

时间复杂度是nlogn。 https://www.cnblogs.com/chengxiao/p/6129630.html

  1. function sort(arr = []){
  2.     const len = arr.length;
  3.   // 构造一个大顶堆：堆定最大，堆尾最小
  4.   function heapify(arr, i){
  5.       const left = i * 2 + 1; // 二叉树左节点在数组下标
  6.     const right = i * 2 + 2; // 二叉树右节点在数组下标
  7.     let max = i;
  8.     if(left < len && arr[left] > arr[max]) max = left;
  9.     if(right < len && arr[right] > arr[max]) max = right;
  10.     if(max !== i){
  11.       // 最大值为堆定
  12.         [a[i], a[max]] = [a[max], a[i]];
  13.       heapify(arr, max);
  14.     }
  15.   }
  16.   for(let i = Math.floor(len / 2); i >= 0; i--){
  17.       heapify(arr, i);
  18.   };
  19.   for(let i = len - 1; i > 0; i--){
  20.     // 堆尾和堆定互换，最后一个最大
  21.       [arr[0],arr[i]] = [arr[i], arr[0]];
  22.     i--;
  23.     // 调整堆定，使其继续符合堆定义
  24.     heapify(arr, 0);
  25.   }
  26.   return arr;
  27. }

归并排序

时间复杂度是nlogn。 1、分治 2、归并排序

  1. function sort(arr = []){
  2.     if(arr.length <= 1) return arr;
  3.   const mid = Math.floor(arr / 2);
  4.   const l = sort(arr.slice(0,mid));
  5.   const r = sort(arr.slice(mid));
  6.   return Array.from({length:l.length+r.length},()=>{
  7.       if(!l.length) return r.shift();
  8.     if(!r.length) return l.shift();
  9.     return l[0] > r[0] ? r.shift() : l.shift();
  10.   })
  11. }

桶排序
  1. function sort(arr = [], size){
  2.     const min = Math.min(...arr);
  3.   const max = Math.max(...arr);
  4.   const bucks = Array.from({length:Math.floor((max - min) / size + 1)},()=>[]);
  5.   arr.forEach(item=>{
  6.       bucks[Math.floor((item - min) / size)].push(item);
  7.   });
  8.      return arr.reduce((acc, cur) => [...arr, ...cur.sort((a, b) => a - b)], [])
  9. }