18.初级排序与高级排序

18 极客大学-算法训练营-覃超-第十八课.pdf

排序算法

参考链接

• 十大经典排序算法
• 快速排序代码示例
• 归并排序代码示例
• 堆排序代码示例

  课后作业

  用自己熟悉的编程语言，手写各种初级排序代码，提交到学习总结中。

参考链接

• 十大经典排序算法
• 9 种经典排序算法可视化动画

• 6 分钟看完 15 种排序算法动画展示

  实战题目 / 课后作业

• [x] 数组的相对排序（谷歌在半年内面试中考过）

• 有效的字母异位词（Facebook、亚马逊、谷歌在半年内面试中考过）
• 力扣排行榜（此题选做；Bloomberg 在半年内面试中考过）
• 合并区间（Facebook、字节跳动、亚马逊在半年内面试中常考）
• 翻转对（字节跳动在半年内面试中考过）

• 基础排序算法

  • 冒泡排序

    // 基础版本 O(n^2)
    function bubbleSort(arr){
    for(let i=0; i<arr.length;i++){
     for(let j=0; j<arr.length-1;j++){
       if(arr[j] < arr[j+1]){
         [arr[j], arr[j+1]] = [arr[j+1], arr[j]]
     }
    }
    }
    return arr;
    }
    // 改进版本1 O(n^2) 随着冒泡的进行，后续已经有序，无需对比
    function bubbleSort(arr){
    for(let i=0; i<arr.length;i++){
    // 随着冒泡的进行，后续已经有序，无需对比
     for(let j=0; j<arr.length-1-i;j++){
       if(arr[j] < arr[j+1]){
         [arr[j], arr[j+1]] = [arr[j+1], arr[j]]
     }
    }
    }
    return arr;
    }
    // 改进版本2 O(n)
    function bubbleSort(arr){
    for(let i=0; i<arr.length;i++){
     let flag = true;
    // 随着冒泡的进行，后续已经有序，无需对比
     for(let j=0; j<arr.length-1-i;j++){
       if(arr[j] < arr[j+1]){
         [arr[j], arr[j+1]] = [arr[j+1], arr[j]]
       flag = false;
     }
    }
    // 如果没有发生变更，说明数组有序
    if(flag === true){
       return arr;
    }
    }
    return arr;
    }

  • 插入排序

选择排序的关键字是“最小值”：循环遍历数组，每次都找出当前范围内的最小值，把它放在当前范围的头部；然后缩小排序范围，继续重复以上操作，直至数组完全有序为止。

function selectSort(arr){
    let len = arr.length;
  let minIndex = 0;
  for(let i=0; i<len-1;i++){
    minIndex = i;
      for(let j=i;j<len;j++){
        if(arr[j]<arr[minIndex]){
          minIndex = j;
      }
    }
    if(minIndex !== i){
      [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]]
    }
  }
    return arr;
}

• 选择排序
  • 进阶排序算法
• 归并排序
• 快速排序