【算法系列 | 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) <= 1:
        return arr
    pivot = arr[0]
    left = []
    right = []
    for i in range(1, len(arr)):
        if arr[i] < pivot:
            left.append(arr[i])
        else:
            right.append(arr[i])
    return quick_sort(left) + [pivot] + quick_sort(right)

思路，

1. 首先检查数组的长度，如果长度小于等于 1，说明该数组已经有序，直接返回即可。
2. 否则，选择一个基准元素（这里选择第一个元素作为基准），将数组分成两个部分，小于基准元素的部分和大于等于基准元素的部分。
3. 然后，递归地对这两个部分进行快速排序，并将它们拼接起来，得到最终的排序结果。

代码实现：

1. 使用了两个辅助数组 left 和 right，分别用于存储小于基准元素和大于等于基准元素的部分。
2. 遍历原数组时，如果当前元素小于基准元素，就将它添加到 left 数组中，否则将它添加到 right 数组中。
3. 最后，递归地对 left 和 right 数组进行排序，并将它们和基准元素拼接起来，得到最终的排序结果。

Java实现

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

public static void quickSort(int[] arr, int left, int right) {
    if (left >= right) {
        return;
    }
    int pivot = arr[left];
    int i = left + 1, j = right;
    while (i <= j) {
        if (arr[i] < pivot) {
            i++;
        } else if (arr[j] >= 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本，评论区随机挑选小伙伴！

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

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

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

中奖名单 

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/黑客灵魂/article/detail/840869