1、什么是排序

无序数字按顺序排列、

2、冒泡排序

重复从左右对比，交换顺序 O(n2)

  1. let arr = [5,4,1,3,6,7,8,9,0,6]
  2. function sortFun(arr){
  3.    for(let i=0;i<arr.length-1;i++){
  4.        for(let j=i+1; j< arr.length; j++){
  5.              if(arr[i]>arr[j]){
  6.                 [arr[i],arr[j]] = [arr[j],arr[i]]
  7.              }
  8.        }
  9.    }
  10. }
  11. sortFun(arr)

3、选择排序

重复从数组中查找最小值

  1. let arr = [5, 4, 1, 3, 6, 7, 8, 9, 0, 6, 1, 222];
  2. function sortFun(arr) {
  3.   let length = arr.length - 1;
  4.   let temp = [];
  5.   while (length--) {
  6.     let minItem = Math.min(...arr);
  7.     arr.splice(arr.findIndex(el=>el === minItem),1)
  8.     temp.push(minItem);
  9.   }
  10.   console.log(temp);
  11.   return temp;
  12. }
  13. sortFun(arr);

4、插入排序

思想： 双循环，拿出一张牌进行比较如果大于 handle中每一张 插入后面 ， 如果都不大于 放最前面 ， 下一轮比较

  1. let arr = [5, 4, 1, 3, 6, 7, 8, 9, 0, 6, 1, 222];
  2. function sortFun(arr) {
  3.   let handle = [];
  4.   handle.push(arr[0]);
  5.   for (let i = 0; i < arr.length; i++) {
  6.     // 随便拿出一张牌
  7.     let A = arr[i];
  8.     for (let j = handle.length - 1; j >= 0; j--) {
  9.       let B = handle[j];
  10.       if (A > B) {
  11.         // 插入到后面
  12.         handle.splice(j + 1, 0, A);
  13.         // 结束本次
  14.         break;
  15.       }
  16.       // 比到最后一张都没有比B大的，所以是最后一张放到最前面
  17.       if (j === 0) {
  18.         handle.unshift(A);
  19.       }
  20.     }
  21.   }
  22.   console.log(handle);
  23. }
  24. sortFun(arr);

5、堆排序

6、归并排序

7、快速排序

思想 通过递归 二分的形式进行排序 终止条件是arr.length == 0

  1. let arr = [5, 4, 1, 3, 6, 7, 8, 9, 0, 6, 1, 222];
  2. function sortFun(arr) {
  3.     if(arr.length === 0 ) return arr
  4.     let leftArr=[];
  5.     let rightArr = []
  6.     let midIndex  =  Math.floor(arr.length/2)
  7.     // 数组中原地删除这个值 
  8.     midValue = arr.splice(midIndex,1)[0]
  9.     for(let i=0;i<arr.length;i++){
  10.         if(arr[i]< midValue){
  11.             // console.log(left)
  12.             leftArr.push(arr[i])
  13.         }else{
  14.             rightArr.push(arr[i])
  15.         }
  16.     }
  17.     return sortFun(leftArr).concat(midValue, sortFun(rightArr));
  18. }
  19. console.log(sortFun(arr))