1 冒泡

冒泡排序的过程，就是从第一个元素开始，重复比较相邻的两个项，若第一项比第二项更大，则交换两者的位置；反之不动。
每一轮操作，都会将这一轮中最大的元素放置到数组的末尾。假如数组的长度是 n，那么当我们重复完 n 轮的时候，整个数组就有序了。
冒泡排序的时间复杂度
我们分最好、最坏和平均来看：

  • 最好时间复杂度：它对应的是数组本身有序这种情况。在这种情况下，我们只需要作比较（n-1 次），而不需要做交换。时间复杂度为 O(n)
  • 最坏时间复杂度： 它对应的是数组完全逆序这种情况。在这种情况下，每一轮内层循环都要执行，重复的总次数是 n(n-1)/2 次，因此时间复杂度是 O(n^2)
  • 平均时间复杂度：这个东西比较难搞，它涉及到一些概率论的知识。实际面试的时候也不会有面试官摁着你让你算这个，这里记住平均时间复杂度是 O(n^2) 即可。
  1. function bubbleSort(arr) {
  2.     const len = arr.length;
  3.     for (let i = 0; i < len; i++) {
  4.         for (let j = 0; j < len - 1; j++) {
  5.             if (arr[j] > arr[j + 1]) {
  6.                 [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]
  7.             }
  8.         }
  9.     }
  10.     return arr
  11. }
  13. //改进  数组的后n个元素 已经有序了
  14. function bubbleSort2(arr) {
  15.     const len = arr.length;
  16.     for (i = 0; i < len; i++) {
  17.         for (let j = 0; j < len - 1 - i; j++) {
  18.             if (arr[j] > arr[j + 1]) {
  19.                 [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]
  20.             }
  21.         }
  22.     }
  23.     return arr
  24. }
  26. //最好情况
  27. function bubbleSort3(arr){
  28.     const len = arr.length;
  29.     for(let i=0;i<len;i++){
  30.         let flag = false;
  31.         for(let j=0;j<len-1-i;j++){
  32.             if(arr[j]>arr[j+1]){
  33.              [arr[j],arr[j+1]]=[arr[j+1],arr[j]]
  34.              flag =true
  35.             }
  36.         }
  37.         if(flag == false) return arr;
  38.     }
  39.    return arr
  40. }

2 选择排序

选出最小值 和该序列的第一个交换位置
选择排序的时间复杂度
在时间复杂度这方面，选择排序没有那么多弯弯绕绕：最好情况也好，最坏情况也罢，两者之间的区别仅仅在于元素交换的次数不同，但都是要走内层循环作比较的。因此选择排序的三个时间复杂度都对应两层循环消耗的时间量级： O(n^2)。

  1. function selectSort(arr)  {
  2.   // 缓存数组长度
  3.   const len = arr.length 
  4.   // 定义 minIndex，缓存当前区间最小值的索引，注意是索引
  5.   let minIndex  
  6.   // i 是当前排序区间的起点
  7.   for(let i = 0; i < len - 1; i++) { 
  8.     // 初始化 minIndex 为当前区间第一个元素
  9.     minIndex = i  
  10.     // i、j分别定义当前区间的上下界，i是左边界，j是右边界
  11.     for(let j = i; j < len; j++) {  
  12.       // 若 j 处的数据项比当前最小值还要小，则更新最小值索引为 j
  13.       if(arr[j] < arr[minIndex]) {  
  14.         minIndex = j
  15.       }
  16.     }
  17.     // 如果 minIndex 对应元素不是目前的头部元素，则交换两者
  18.     if(minIndex !== i) {
  19.       [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]]
  20.     }
  21.   }
  22.   return arr
  23. }

3 插入排序

前面的都是有序的 拿到一个数后 开始往前比较 如果遇到比它 大的则将大的移到它的位置 然后前面的位置空出来 在继续往前比较 知道找到正确的 位置

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

插入排序的时间复杂度

  • 最好时间复杂度：它对应的数组本身就有序这种情况。此时内层循环只走一次，整体复杂度取决于外层循环，时间复杂度就是一层循环对应的 O(n)。
  • 最坏时间复杂度：它对应的是数组完全逆序这种情况。此时内层循环每次都要移动有序序列里的所有元素，因此时间复杂度对应的就是两层循环的 O(n^2)
  • 平均时间复杂度：O(n^2)

归并排序

从中间分割 在分割 分割到最小单元在有序合并
log(n) 轮对应 log(n) 次合并操作，因此归并排序的时间复杂度就是 O(nlog(n))

  1. function mergeSort(arr) {
  2.     const len = arr.length
  3.     // 处理边界情况
  4.     if(len <= 1) {
  5.         return arr
  6.     }   
  7.     // 计算分割点
  8.     const mid = Math.floor(len / 2)    
  9.     // 递归分割左子数组，然后合并为有序数组
  10.     const leftArr = mergeSort(arr.slice(0, mid)) 
  11.     // 递归分割右子数组，然后合并为有序数组
  12.     const rightArr = mergeSort(arr.slice(mid,len))  
  13.     // 合并左右两个有序数组
  14.     arr = mergeArr(leftArr, rightArr)  
  15.     // 返回合并后的结果
  16.     return arr
  17. }
  19. function mergeArr(arr1, arr2) {  
  20.     // 初始化两个指针，分别指向 arr1 和 arr2
  21.     let i = 0, j = 0   
  22.     // 初始化结果数组
  23.     const res = []    
  24.     // 缓存arr1的长度
  25.     const len1 = arr1.length  
  26.     // 缓存arr2的长度
  27.     const len2 = arr2.length  
  28.     // 合并两个子数组
  29.     while(i < len1 && j < len2) {
  30.         if(arr1[i] < arr2[j]) {
  31.             res.push(arr1[i])
  32.             i++
  33.         } else {
  34.             res.push(arr2[j])
  35.             j++
  36.         }
  37.     }
  38.     // 若其中一个子数组首先被合并完全，则直接拼接另一个子数组的剩余部分
  39.     if(i<len1) {
  40.         return res.concat(arr1.slice(i))
  41.     } else {
  42.         return res.concat(arr2.slice(j))
  43.     }
  44. }

快速排序

选基线条件 大于 小于分组 递归
平均O(nlogn) 最糟：O(n2)

  1. function quickSort(array) {
  2.       if (array.length <= 1) {
  3.         return array;
  4.       }
  5.       const pivotIndex = Math.floor(array.length / 2)
  6.       console.log(pivotIndex);
  7.       const pivot = array.splice(pivotIndex,1)[0] 
  8.       // 0 数组扁平化
  9.       const left = [], right = [];
  10.       array.forEach(element => {
  11.         if (element < pivot) {
  12.           left.push(element);
  13.         } else {
  14.           right.push(element);
  15.         }
  17.       });
  18.       return quickSort(left).concat([pivot], quickSort(right));
  19.     }