【算法系列 | 2】深入解析排序算法之——插入排序

序言

你只管努力，其他交给时间，时间会证明一切。

文章标记颜色说明：

• 黄色：重要标题
• 红色：用来标记结论
• 绿色：用来标记一级论点
• 蓝色：用来标记二级论点

  决定开一个算法专栏，希望能帮助大家很好的了解算法。主要深入解析每个算法，从概念到示例。

  我们一起努力，成为更好的自己！

  今天第二讲，讲一下排序算法的插入排序

  1 基础介绍

  排序算法是很常见的一类问题，主要是将一组数据按照某种规则进行排序。

  以下是一些常见的排序算法：

  1. 冒泡排序（Bubble Sort）

  2. 插入排序（Insertion Sort）

  3. 选择排序（Selection Sort）

  4. 归并排序（Merge Sort）

  5. 快速排序（Quick Sort）

  6. 堆排序（Heap Sort）

  插入排序

  原理介绍

  插入排序是一种简单直观的排序算法，其原理是将一个数组分成已排序和未排序两部分，初始时已排序部分只有一个元素，然后将未排序部分的每个元素插入到已排序部分的适当位置，直到所有元素都被排序。

  当将一个元素插入到已排序部分时，需要将已排序部分中所有大于该元素的元素向后移动一位，然后将该元素插入到合适的位置。

  例如，假设已排序部分为 [3, 5, 8]，待插入元素为 4，需要将 5 和 8 向后移动一位，然后将 4 插入到 5 的位置，最终已排序部分变为 [3, 4, 5, 8]。

  这一过程可以使用一个内部循环来实现。从待插入元素的前一个位置开始，向前遍历已排序部分，直到找到第一个小于等于待插入元素的位置，然后将待插入元素插入到该位置之后。

  具体实现时，我们可以使用两个嵌套的循环。外层循环遍历未排序部分中的每个元素，内层循环从待插入元素的前一个位置开始，向前遍历已排序部分，直到找到第一个小于等于待插入元素的位置，然后将待插入元素插入到该位置之后。

  下面是一个伪代码实现：

  for i from 1 to n-1 do
      j = i
      while j > 0 and A[j-1] > A[j] do
          swap A[j] and A[j-1]
          j = j - 1
  

  其中，变量 i 用于遍历未排序部分，变量 j 指向待插入元素在已排序部分中的位置，循环内部的 while 循环用于将待插入元素插入到正确的位置。

  复杂度

  时间复杂度为 O(n^2)，空间复杂度为 O(1)。

  使用场景

  插入排序的优点是对于小规模的数据集，它的效率比较高，而且它的实现比较简单。

  但是对于大规模的数据集，插入排序的效率会比较低，因为它需要进行大量的元素移动操作。

  代码实现

  Python 实现

  下面是一个使用 Python 实现快速排序的示例代码：

  def quick_sort(arr):
      if len(arr) = right) {
          return;
      }
      int pivot = arr[left];
      int i = left + 1, j = right;
      while (i = pivot) {
              j--;
          } else {
              swap(arr, i, j);
              i++;
              j--;
          }
      }
      swap(arr, left, j);
      quickSort(arr, left, j - 1);
      quickSort(arr, j + 1, right);
  }
  private static void swap(int[] arr, int i, int j) {
      int temp = arr[i];
      arr[i] = arr[j];
      arr[j] = temp;
  }
  

  实现思路：

  1. 首先检查左右指针的位置，如果左指针大于等于右指针，说明当前的子数组已经有序，直接返回即可。
  2. 否则，选择一个基准元素（这里选择左端点的元素作为基准），将数组分成两个部分，小于基准元素的部分和大于等于基准元素的部分。
  3. 然后，使用两个指针 i 和 j 分别从左右两端开始遍历，将小于基准元素的元素移动到左边，将大于等于基准元素的元素移动到右边，直到 i 和 j 相遇。
  4. 最后，将基准元素交换到正确的位置上，递归地对左右两个部分进行快速排序。

  代码实现：

  1. 使用了两个辅助指针 i 和 j，分别从左右两端开始遍历数组。
  2. 在遍历过程中，如果 arr[i] 小于 pivot，就将 i 向右移动一位；如果 arr[j] 大于等于 pivot，就将 j 向左移动一位；
  3. 否则，交换 arr[i] 和 arr[j]，然后将 i 向右移动一位，将 j 向左移动一位。当 i 和 j 相遇时，遍历结束，此时 arr[j] 是小于 pivot 的最后一个元素，将 pivot 交换到 arr[j] 的位置上，然后递归地对左右两个部分进行快速排序。

  今天就到这里了，下期见~ 

  图书推荐

  图书名称：

  • Python程序设计：人工智能案例实践 
  • 机器学习 Python版
  • 深度强化学习

    Python程序设计：人工智能案例实践 

    

    图书介绍：

    极简入门Python和AI，读这一本就够了！

    538个实例帮你掌握交互式IPython解释器和JupyterNotebook并应用Python实践人工智能项目。

    作者：[美] 保罗·戴特尔，[Paul，J.Deitel]，[美] 哈维·戴特尔（Harvey 

    译者：王恺、王刚、于名飞 等

    书号：978711167845

    定价：149.00

    机器学习 Python版

    

    图书介绍：

    机器学习初学者入门指南

    使用Python语言以及scikit-learn库，掌握开发机器学习系统所需的流程、模式和策略。

    作者：[美] 马克·E.芬纳（Mark E. Fenner） 

    译者：江红，余青松，余靖 

    书号：9787111706007

    定价：149.00

    深度强化学习

    

    图书介绍：

    谷歌首席科学家力荐！

    深度强化学习软件库开发者力作，无门槛深度强化学习实践指南。

    作者：[美] 劳拉·格雷泽（Laura Graesser） 等 

    译者：许静、过辰楷、金骁、刘磊、朱静雯 等 

    书号：9787111689331

    定价：119.00

    参与方式 

    图书数量：本次送出 3 本   ！！！⭐️⭐️⭐️

    活动时间：截止到 2023-06-09 12:00:00

    抽奖方式：

    • 1本，留言+该留言论赞数的前1名！
    • 2本，评论区随机挑选小伙伴！

      留言内容，以下三种都可以：

      • “放弃不难，但坚持一定很酷！+【你想要的书名】”
      • 努力过后，才知道许多事情，坚持坚持，就过来了。+【你想要的书名】
      • 文章高质量评论

        参与方式：关注博主、点赞、收藏，评论区留言 

        中奖名单 

        🍓🍓 获奖名单🍓🍓

         中奖名单：请关注博主动态

        名单公布时间：2023-06-09 下午