1. 什么叫做排序？

排序就是将数组从小到大，或者从大到小顺序排列

2.常见的排序算法 （要背）

InkedQQ截图20210826113846_LI.jpg

注： 这里有 马士兵老师的宋词记忆法 （恩老： nlog2n, 恩一三: n^1.3）

  1.                          ![QQ截图20210826114502.png](https://cdn.nlark.com/yuque/0/2021/png/12864711/1629949506827-367440bf-7a84-4a28-aea0-b84753b409ef.png#clientId=u4d2cc51a-ab91-4&from=drop&id=u25ae89c9&margin=%5Bobject%20Object%5D&name=QQ%E6%88%AA%E5%9B%BE20210826114502.png&originHeight=310&originWidth=273&originalType=binary&ratio=1&size=122513&status=done&style=none&taskId=uf2231a80-5839-4264-846d-22102a755a1)

3.如何写算法程序

3.1 由简单到复杂

3.1.1 验证一步走一步

3.1.2 多打印中间内容

3.2 先局部后整体

3.2.1 没思路时先细分

3.3 先粗糙后精细

3.3.1 变量更名

3.3.2 语句合并

3.3.3 边界处理

4. 算法讲解

4.1 选择排序

4.1.1 最简单但是最没用的排序算法

将数组第一位和数组第二位进行对比，哪个比较小，将坐标记录下来，再将第二位和第三位进行对比，比较大小，更改坐标记录，重复操作，知道数组遍历完，将做小的数放在数组最前面。之后再去掉第一位，遍历之后的数组数字，重复以上操作。

4.1.2 写法

  1. const arr = [5, 3, 6, 8, 7, 9];
  3. const select = () => {
  4.     for(let i = 0; i<arr.length - 1; i++){
  5.     //记录当前坐标
  6.     let minPos = i;
  7.     //比较当前坐标 minPos 与 minPos + 1 的大小，如果前者较大，则更改坐标。 
  8.     for(let j = i + 1; j<arr.length;j++) {
  9.       if(arr[j] < arr[minPos]) minPos = j;
  10.     }
  12.     //将数组内容交换
  13.     let temp = arr[i];
  14.     arr[i] = arr[minPos];
  15.     arr[minPos] = tmp;
  16.   }
  17. }
  19. // 优化代码
  20. //设置做大数据坐标，最小数据坐标
  21. //将较大的数放在后面，将较小的数放在前面
  22. const better = () => {
  23.      let left = 0;
  24.     let right = arr.length - 1;
  25.     while(left < right) {
  26.         let minPos = left;
  27.         let maxPos = right;
  29.         for(let i = left; i <= right; i++) {
  30.             if(arr[ i ] < arr[minPos]) {
  31.                 minPos = i;
  32.             }
  34.             if(arr[ i ] > arr[maxPos]) {
  35.                 maxPos = i;
  36.             }
  37.         }
  39.         let minTemp = arr[minPos]
  40.         arr[minPos] = arr[left];
  41.         arr[left] = minTemp;
  43.         if(left == maxPos) {
  44.             minPos = maxPos;
  45.         }
  47.         let maxTemp = arr[maxPos]
  48.         arr[maxPos] = arr[right];
  49.         arr[right] = maxTemp;
  51.         left++;
  52.         right--;
  53.     }
  55.     return arr
  56. }

4.1.3 大O分析

  1. const arr = [5, 3, 6, 8, 7, 9];  //初始化，不计入算法时间
  3. const select = () => {
  4.   //  执行 n 次   执行 n-1 次    执行 n 次
  5.     for(let i = 0; i<arr.length - 1; i++){
  6.     //执行 n 次
  7.     let minPos = i;
  8.     //    执行 n 次     执行 n^2 次  执行 n^2 次
  9.     for(let j = i + 1; j<arr.length;j++) {
  10.       //当 j = i+1时 执行 n-1 次 
  11.       // n^2
  12.       if(arr[j] < arr[minPos]) minPos = j;
  13.     }
  14.     // 执行 n 次
  15.     let temp = arr[i];
  16.     arr[i] = arr[minPos];
  17.     arr[minPos] = tmp;
  18.   }
  19. }

4.2 冒泡排序

4.2.1 介绍

将数字[0]与数组[1]比较，如果[0]比较大，将两者交换位置，再将[1]和[2]比较，如果[1]比较大，两者交换位置，循环，知道不能交换为止。
QQ截图20210828191926.png

4.2.2 写法

  1. function sort(arr){
  2.     for(let i = arr.length - 1; i > 0; i--) {
  3.     //循环，每次交换位置，则去掉最后一个数据
  4.       for(let j = 0; j<i; j++) {
  5.       //找到最大值，并将最大值放到数组的最后
  6.         if(a[j] > a[j+1]) {
  7.         //交换数组数据
  8.           let temp = a[j]
  9.         a[j] = a[j+1]
  10.         a[j+1] = a[j]
  11.       }
  12.     }
  13.   }
  14. }

4.3 插入排序

4.3.1 插入排序

对于基本有序的数组最好用
从数组[1]开始和数组[0]比较大小，如果[1]比较大，交换位置，然后从[2]开始，和[1]比较大小，同理，之后循环， dddd

4.3.2 图例

QQ截图20210828195635.png

4.3.3 写法

  1.  function sort(arr) {
  2.         //i 是当前坐标
  3.         for(i = 1; i < arr.length; i++){
  4.             //当前坐标 - i
  5.            for(let j = i; j > 0; j--) {
  6.                   //将当前坐标 与 坐标之前的比较，如果较小则交换位置
  7.                if(arr[j] < arr[j-1]) {
  8.                     swap(arr, j, j-1);
  9.                }
  10.            }
  12.         }
  13.         return arr
  14.     }
  16.     function swap(arr, i, j) {
  17.         let temp = arr[i]
  18.         arr[i] = arr[j]
  19.         arr[j] = arr[i]
  20.     }

简单排序算法总结：

冒泡：基本不用，太慢

选择： 基本不用，不稳

插入： 样本小且基本有序的时候效率比较高

5、希尔排序

5.1 介绍

改进的插入排序
在排序的时候需要加入间隔，比如说 gap = 4， 则相隔4个数，选择一个数，将这些数用插入排序排列，
在往后挪移一位在排序，后面同理，排完之后，大致小的数都在数组的前面，大致大的数都在数组后面
之后，缩小间隔为2，在进行上述排序，直到间隔为1排序完成

5.2 图解

QQ截图20210828203157.png
QQ截图20210828203339.png

5.3 写法

  1.          let arr = [5, 3, 6, 8, 7, 9]; 
  2.     //希尔排序
  3.     function sort(arr) {
  4.           //采用knuth序列
  5.           let h = 1;
  6.           while(h < arr.length / 3) {
  7.             h = h * 3 + 1
  8.         }
  10.            for(let gap = h; gap > 0; gap = (gap-1)/3) {
  11.             Insert(arr, gap)
  12.         }
  14.         return arr
  15.     }
  17.     //插入排序
  18.     function Insert(arr, gap) {
  19.         //i 是当前坐标
  20.         for(i = gap; i < arr.length; i++){
  21.             //当前坐标 - i
  22.             for(let j = i; j > gap-1; j -= gap) {
  23.                 if(arr[j] < arr[j-gap]) {
  24.                     swap(arr, j, j-gap);
  25.                 }
  26.             }
  28.         }
  29.         return arr
  30.     }
  32.     function swap(arr, i, j) {
  33.       let temp = arr[i]
  34.       arr[i] = arr[j]
  35.       arr[j] = arr[i]
  36.     }

6. 归并排序(merge sort)

6.1 递归

QQ截图20210828205736.png

6.2 介绍

将数组分为两个子数组，如果子数组不是有序的，则将子数组在分为两个数组，同上，排到数组就两数或者只有一个数为止，之后再合并成两个数组。设置三个指针，i 为第一个数组头， j 为第二个数组头， k 为新数组头，将arr[i] 和 arr[j] 比较，如果前者较小，则把前者放在arr2[0]里，在比较 arr[i+1] 和 arr[j]，那个小就把那个推到 arr2 里去，如此重复
QQ截图20210828221421.png

6.3 写法

  1. //两个子数组已经排好序
  2. let arr = [1,4,7,8,3,6,9]
  3. function sort(arr) {
  4.     merge(arr)
  5. }
  7. function merge(arr) {
  8.   //第二个子数组的开头
  9.     let mid = arr.length / 2
  11.   //定义指针
  12.   let i = 0;
  13.   let j = mid + 1;
  14.   let k = 0;
  15.   let temp = [];
  17.   while(i <= mid && j <= arr.length) {
  18.     //当数组相同时，取前面子数组的数据，为了稳定性
  19.       if(arr[i] <= arr[j]) {
  20.         temp[k++] = arr[i++];
  21.     }else {
  22.         temp[k++] = arr[j++];
  23.       //j++;
  24.       //k++;
  25.     }
  26.   }
  27.   //当一个子数组遍历完了，另一个还没遍历完时
  28.   while(i <= mid) {
  29.       temp[k++] = arr[i++];
  30.   }
  32.   while(j <= arr.length) {
  33.       temp[k++] = arr[j++]
  34.   }
  36.   return temp;
  37. }
  1. //优化
  2. function sort(arr, left, right) {
  3.     if(left == right) return;
  4.   //分成两半
  5.   let mid = left + (right-left)/2;
  6.   //左边排序
  7.   sort(arr,left,mid);
  8.   //右边排序
  9.   sort(arr,mid+1,right);
  10.   merge(arr,left,mid+1,right)
  11. }
  14. //leftPtr 左子数组头
  15. //rightPtr 右子数组头
  16. //rightBound 右数组边界
  17. function merge(arr, leftPtr, rightPtr, rightBound) {
  19.   let mid = rightPtr - 1;
  20.   //定义指针
  21.   let i = leftPtr;
  22.   let j = rightPtr;
  23.   let k = 0;
  24.   let temp = [];
  26.   while(i <= mid && j <= rightBound) {
  27.     //当数组相同时，取前面子数组的数据，为了稳定性
  28.       if(arr[i] <= arr[j]) {
  29.         temp[k++] = arr[i++];
  30.     }else {
  31.         temp[k++] = arr[j++];
  32.       //j++;
  33.       //k++;
  34.     }
  35.   }
  36.   //当一个子数组遍历完了，另一个还没遍历完时
  37.   while(i <= rightPtr) {
  38.       temp[k++] = arr[i++];
  39.   }
  41.   while(j <= rightBound) {
  42.       temp[k++] = arr[j++]
  43.   }
  45.   return temp;
  46. }

6.4 java对象排序

6.4.1 介绍

对象排序一般要求稳定

7 快速排序

双轴快排

7.1 介绍

寻找一个数作为轴，比这个轴小的排前面，比这个轴高的排后面，之后将轴两边进行分区，左子区和右子区，之后再对左右两个分区进行相应的规则排序。

7.2 图例

QQ截图20210830112212.png

7.3 算法

  1. let arr = [7,3,2,6,8,1,9,5,4,10]
  2. function partition(arr, leftBound, rightBound){
  3.     //一般来说，轴都是最后一个数
  4.   let pivot = arr[rightBound];
  5.   let left = 0;
  6.   let right = rightBound-1;
  7.   //两边同时和轴比较，直到左边找到比轴大的数，右边找到比轴小的数，那么将这两个数的位置交换
  8.   //并将轴的位置放到 left + 1 
  9.   while(left <= right) {
  10.       while(left <= right && arr[left] < pivot) left++;
  11.     while(left <= right && arr[right] > pivot) right--;
  13.     if(left < right) {
  14.         swap(arr, left, right);
  15.     }
  16.   }
  17.   swap(arr, left, rightBound);
  19.   return left;
  20. }
  22. function sort(arr, left, right) {
  23.     if(arr.length ===0 && left > right) return;
  24.   //获取到轴的位置
  25.   let mid = partition(arr, left, right);
  26.   //再排序轴左边和轴右边
  27.   sort(arr, left, mid-1);
  28.   sort(arr, mid+1, right);
  29. }

7.4 双轴快排

7.4.1 介绍

找两个数作为轴，把数组分成三个区域，比第一个数小的放左边，比第二个数大的放右边，在两个数中间的放中间。

8. 计数排序

8.1 介绍

非比较排序 桶思想的一种 用于取值范围比较小，但是量大
比如 某大型企业数万名员工年龄排序
如何快速得知高考名次
取一个新的数组进行计数，这个数组的大小则是可以取值的范围
当我们读到0的时候，我们给0坐标的数组+1 同理，每个数出现了多少次，再以这个数作为一个下标值，把他记录下来

8.2 写法

  1. function sort(arr) {
  2.     let result = [];
  3.   let count = [];
  4.   for(let i = 0; i< arr.length; i++){
  5.     //以该数组为下表的值++，来获取计数数组
  6.       count[arr[i]]++;
  7.   }
  8.   //来还原排序数组
  9.   for(let i=0,j=0; i<count.length;i++) {
  10.       while(count[i]-- > 0) {
  11.         result[j++] = i;
  12.     }
  13.   }
  15.   return result;
  17. }
  1. //优化
  2. //使用累加数组，来记录每个数最后的一个的坐标
  3. function sort(arr) {
  4.     let result = [];
  5.   let count = [];
  6.   for(let i = 0; i< arr.length; i++){
  7.     //以该数组为下表的值++，来获取计数数组
  8.       count[arr[i]]++;
  9.   }
  11.   //累加数组
  12.   for(let i = 1; i<count.length; i++) {
  13.       count[i] = count[i-1] + count[i];
  14.   }
  17.   //倒叙筛选,迭代排列
  18.   for(let i = arr.length-1; i > 0;i--) {
  19.       result[--count[arr[i]]] = arr[i]
  20.   }
  22.   return result;
  24. }

9. 基数排序

9.1 介绍

  • 非比较排序
  • 桶思想的一种
  • 多关键字排序
  • 按最长的数来排，比如说四位数，就排4次，不足四位的，前面补0
  • 举例，全是三位数的排序，首先先排个位数，再排十位数，再排百位数

9.2 写法

  1. //算出每个位上的数，放入一个累加数组中，然后计数排序

10. 桶排序

10.1 图例QQ截图20210831102807.png

之后再在每个桶中单独排序，再把整个桶的数组对外输出。

11. 大数据解题思路

QQ截图20210923204222.png