数据结构和算法(1)

2025年05月07日 1k 字大概 4 分钟

算法、大O记法

数据结构和算法(1)

什么是算法？

算法，即解决某个问题的一套流程。例如最简单的一个问题，如何把大象装进冰箱？第一步，打开冰箱；第二步，将大象装进冰箱；第三步，关上冰箱。而这整个的流程，就叫算法。但是每个人都有不同的方法，比如小明在装大象时，把大象切成块，多了一个步骤，现在小明需要四步才能把大象装进去，而之前的方法只需要三步，这就叫做时间复杂度。随着要装的大象越来越多，小明所用的步骤越来越多，即n*3步，在这里我们使用大O记法来描述步骤，即O(3n)。但是在大O记法中，我们忽略常数。所以，小明装大象的时间复杂度为O(n)。在程序设计中，我们会想方设法的优化我们的算法，以此来让程序运行相应得更快，发挥代码的极限性能。因此，学习算法是很有必要的。

大O记法的规则：
1、忽略常数
2、只关注最高阶的N

排序算法和其效率

现在我们要对数组 int arr[5] = {4, 2, 7, 1 ,3}进行排序

冒泡排序

void BubbleSort()
{
    for (int i = 0; i < 5 - 1; ++i)
    {                         // 外层循环控制轮次（n-1轮）
        bool swapped = false; // 优化：标记是否发生交换
        for (int j = 0; j < 5 - 1 - i; ++j)
        { 
            // 内层循环比较相邻元素
            if (arr[j] > arr[j + 1])
            {                      // 如果前一个元素更大
                int temp = arr[j]; // 交换相邻元素                    arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swapped = true; // 标记发生交换
            }
        }
        if (!swapped)
            break; // 如果一轮未发生交换，说明已有序，提前终止
    }

    printArr(arr);
}

原理

核心思想：通过多次遍历数组，每次比较相邻的两个元素，如果顺序错误就交换它们，直到数组有序。
每一轮排序后，最大的元素会“冒泡”到数组末尾（类似气泡上浮）。

N个元素	最多步数	$N^2$
5	20	25
10	90	90
20	380	400
40	1560	1600
80	6320	6400

最坏的情况下，时间复杂度为O($n^2$) (完全逆序)

插入排序

void InsertSort()
{
    for (int i = 1; i < 5; ++i)
    {
        int index = i;
        int temp_value = arr[i];

        while (index > 0 && arr[index - 1] > temp_value)
        {
            arr[index] = arr[index - 1];
            --index;
        }
        arr[index] = temp_value;
    }

    printArr(arr);
}

原理

核心思想：将数组分为已排序和未排序两部分，逐个将未排序元素插入到已排序部分的正确位置。
类似扑克牌排序：每次抓一张牌，插入到手中已排序牌的合适位置。
最坏情况下，时间复杂度为O($n^2$) (完全逆序时需全部移动)

选择排序

void SectionSort()
{

    for (int i = 0; i < 5; ++i)
    {
        int arr_min_index = i;
        for (int j = i + 1; j < 5; ++j)
        {
            if (arr[j] < arr[arr_min_index])
            {
                arr_min_index = j;
            }
        }
        if (arr_min_index != i)
        {
            int temp = arr[i];
            arr[i] = arr[arr_min_index];
            arr[arr_min_index] = temp;
        }
    }
    printArr(arr);
}

原理

核心思想：每次从未排序部分选择最小（或最大）的元素，放到已排序部分的末尾。
分为两部分：左侧已排序，右侧未排序。

N个元素	最多步数	选择排序最多步数
5	20	14
10	90	54
20	380	199
40	1560	819
80	6320	3239

时间复杂度始终为O($n^2$)

总结

事实上，因为大O记法的规则，我们并不能通过大O比较冒泡排序和选择排序，我们通过具体分析得到选择排序是要快于冒泡排序的。但是大O还是重要的，它能够区分不同算法的长期增长率。当数据增长到一定程度，O(N)永远比O($N^2$)快。通过以上排序算法的介绍，我们能够通过大O去判断各种算法的效率。在日常的情况下，我们遇到大多是平均情况，其出现频率呈正态分布。而在选择上，我们也要根据情况来选择合适的算法。