【算法系列 | 1】深入解析排序算法之冒泡排序网站首页 其他

【算法系列 | 1】深入解析排序算法之冒泡排序

颜淡慕潇 2024-08-09 00:01:02

简介【算法系列 | 1】深入解析排序算法之冒泡排序

序言

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

文章标记颜色说明：

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

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

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

今天第一讲，讲一下排序算法

1 基础介绍

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

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

冒泡排序（Bubble Sort）

插入排序（Insertion Sort）

选择排序（Selection Sort）

归并排序（Merge Sort）

快速排序（Quick Sort）

堆排序（Heap Sort）

这些排序算法各有特点，可以根据具体需求选择适合的算法。在实际应用中，常常需要综合考虑时间复杂度、空间复杂度、稳定性等因素进行选择。

今天先来看一下比较简单的冒泡排序

冒泡排序

原理介绍

冒泡排序（Bubble Sort）是一种简单的排序算法，其基本思想是对待排序的元素从前向后依次比较相邻的两个元素，如果顺序不对则交换它们的位置，一轮比较下来，最大的元素就会“冒泡”到数组的末尾。

重复这个过程，直到没有需要交换的元素为止，排序完成。

时间复杂度

冒泡排序的时间复杂度是O(n^2)，空间复杂度是O(1)，

适用场景

冒泡排序，它是一种稳定的排序算法，适用于处理小规模数据。不适合处理大规模数据，对于大规模数据的排序效率不高，不推荐使用。

当需要对大规模数据进行排序时，可以考虑其他排序算法，如归并排序、快速排序等。

示例讲解

下面是一个冒泡排序的示例，对如下数组进行排序：[5, 3, 8, 4, 2]

第一轮比较：

5, 3, 8, 4, 2 -> 3, 5, 8, 4, 2

3, 5, 8, 4, 2 -> 3, 5, 4, 8, 2

3, 5, 4, 8, 2 -> 3, 5, 4, 2, 8

第一轮比较结束，最大的元素 8 已经被移动到了数组的末尾。

第二轮比较：

3, 5, 4, 2, 8 -> 3, 4, 5, 2, 8

3, 4, 5, 2, 8 -> 3, 4, 2, 5, 8

第二轮比较结束，次大的元素 5 已经被移动到了数组的倒数第二个位置。

第三轮比较：

3, 4, 2, 5, 8 -> 3, 2, 4, 5, 8

第三轮比较结束，次次大的元素 4 已经被移动到了数组的倒数第三个位置。

第四轮比较：

3, 2, 4, 5, 8 -> 2, 3, 4, 5, 8

第四轮比较结束，最小的元素 2 已经被移动到了数组的第一个位置。

经过四轮比较，数组已经被排好序了。

代码实现

python实现

def bubble_sort(arr):
    n = len(arr)
    # 外层循环控制排序的轮数
    for i in range(n):
        # 内层循环控制每一轮的比较和交换
        for j in range(0, n-i-1):
            # 如果前一个元素大于后一个元素，则交换它们的位置
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]

# 测试代码
arr = [5, 3, 8, 4, 2]
bubble_sort(arr)
print(arr)

执行结果

java 实现

public class BubbleSort {
    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        // 外层循环控制排序的轮数
        for (int i = 0; i < n; i++) {
            // 内层循环控制每一轮的比较和交换
            for (int j = 0; j < n-i-1; j++) {
                // 如果前一个元素大于后一个元素，则交换它们的位置
                if (arr[j] > arr[j+1]) {
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }
    }

    // 测试代码
    public static void main(String[] args) {
        int[] arr = {5, 3, 8, 4, 2};
        bubbleSort(arr);
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }
}

运行结果

今天算法就到这里啦，下期见~

图书推荐

图书名称：

《算法导论（原书第3版）》
《程序员必会的40种算法》
《计算机网络：自顶向下方法（原书第7版）》
《TCP/IP详解》

《算法导论（原书第3版）》

作者：Thomas H.Cormen, Charles E.Leiserson, Ronald L.Rivest, Clifford Stein

推荐语：

影响全球千万程序员的“算法圣经”！MIT四大名师联手铸就，将严谨性和全面性融为一体深入讨论各类算法。

麻省理工学院、卡内基梅隆大学、斯坦福大学、加州大学伯克利分校、康奈尔大学、伊利诺伊大学厄巴纳-香槟分校等国内外千余所高校采用教材！

《程序员必会的40种算法》

作者：

[加] 伊姆兰·艾哈迈德

推荐语：

致力于利用算法求解实际问题，帮助初学者理解算法背后的逻辑和数学知识。

算法一直在计算科学和计算实践中发挥着重要作用。除了传统计算之外，使用算法解决现实问题的能力是开发人员和程序员必须具备的一项重要技能。本书不仅能帮助你拓展技能，选择强有力的算法解决现实世界的问题，还能帮助你了解算法原理。

本书内容丰富，涉及算法基础、设计技术、分析方法、排序算法、查找算法、图算法、线性规划算法、机器学习算法、推荐算法、数据算法、密码算法和并行算法等内容，重点讲述如何使用Python进行算法实现和算法性能的比较与分析。

《计算机网络：自顶向下方法（原书第7版）》

推荐语：

本书是经典的计算机网络教材之一，采用了作者独创的自顶向下方法来讲授计算机网络的原理及其协议。自首次出版以来，已被译为14种语言，世界上数百所大学采用本书作为教材，有几十万学生和从业人员利用本书系统学习计算机网络的知识。本书已成为学习计算机网络知识的必读教材之一。

第7版保持了以前版本的特色，继续关注因特网和计算机网络的现代处理方式，注重原理和实践，为计算机网络教学提供了一种新颖和与时俱进的方法。

《TCP/IP详解》

作者：Kevin R. Fall, W. Richard Stevens, Gary R. Wright

推荐语：

网络专家、著名技术作家W. Richard Stevens的传世之作，内容详尽且极具权威，被誉为TCP/IP领域的不朽名著。

Stevens经典网络名著的整体重组和彻底更新，掌握当代网络协议原理及实现技术的必备参考书，全面阐述和透彻分析网络常用协议的工作过程和实现细节。涵盖最新的网络协议和最佳的实践方法，显著加强安全方面内容

等不及的小伙伴，可以点击下方链接先睹为快：

图书链接

参与方式

图书数量：本次送出 3 本！！！⭐️⭐️⭐️
活动时间：截止到 2023-06-06 12:00:00

抽奖方式：

1本，留言+该留言论赞数的前1名！
2本，评论区随机挑选小伙伴！
留言内容：“那些看似不起波澜的日复一日，一定会在某一天让你看见坚持的意义！+【你想要的书名】”

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