【算法系列 | 2】深入解析排序算法之插入排序网站首页 学无止境

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

颜淡慕潇 2024-08-15 00:01:06

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

序言

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

文章标记颜色说明：

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

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

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

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

1 基础介绍

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

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

冒泡排序（Bubble Sort）

插入排序（Insertion Sort）

选择排序（Selection Sort）

归并排序（Merge Sort）

快速排序（Quick Sort）

堆排序（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，说明该数组已经有序，直接返回即可。
否则，选择一个基准元素（这里选择第一个元素作为基准），将数组分成两个部分，小于基准元素的部分和大于等于基准元素的部分。
然后，递归地对这两个部分进行快速排序，并将它们拼接起来，得到最终的排序结果。

代码实现：

使用了两个辅助数组 left 和 right，分别用于存储小于基准元素和大于等于基准元素的部分。
遍历原数组时，如果当前元素小于基准元素，就将它添加到 left 数组中，否则将它添加到 right 数组中。
最后，递归地对 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;
}

实现思路：

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

代码实现：

使用了两个辅助指针 i 和 j，分别从左右两端开始遍历数组。
在遍历过程中，如果 arr[i] 小于 pivot，就将 i 向右移动一位；如果 arr[j] 大于等于 pivot，就将 j 向左移动一位；
否则，交换 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本，评论区随机挑选小伙伴！

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

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

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