简单排序算法的复杂度

一篇温习手记

推荐一个叫”hello算法”的学习网站 https://www.hello-algo.com/

昨晚看户子直播，户子考了一下连线观众冒泡排序，突然让我回忆起各排序算法，竟记不太清析，显然已是遗忘不少了，于是上网重学，写这篇博客以记录

前置知识

算法时间复杂度

算法的时间复杂度是用大写的“O”来表示的，比如：O(1)，O(n)，O(logn)，O(nlogn)，O(n²) 等等。

概念:时间复杂度的全称是渐进时间复杂度，表示算法的执行时间与数据规模（所谓数据规模，一般指输入的数字个数、输入中给出的图的点数与边数等等）之间的增长关系，上面的这种时间复杂度表示法并不能真正反应一个算法的执行时间，反应的只是一个趋势，所以我们在分析复杂度的时候要关注“变”，忽略“不变”。变指的是变量，也就是一段代码的执行时间是随着变量的变化而变化的，而不变指的是常量，也就是不论我的变量如何改变，执行时间都不会改变。

O(1) 常数阶

O(1) 复杂度算法也称之为常数阶算法。这里的 1 是用来代指常量，也就是说这个算法的效率是固定的，无论你的数据量如何变化，效率都一样，这种是复杂度最优的一种算法。

#include <stdio.h>
int main()
{
    int a = 1;
    int b = 2;
    int c = a + b;
    printf("%d", c);
    return 0;
} 

如上，只要代码不存在循环，递归等循环类调用，不论代码有多少行，其复杂度都是常数阶。

O(n) 线性阶

设每一行代码的执行时间是 T，那执行复杂度就是 T+n*T，也就是 (n+1)T，而在算法中有一个原则，那就是常量可以被忽略，所以就得到了 nT，换成大 O 表示法就是 O(n)。

这里的 n 是用来代指数据量的，也就是数据量的多少会影响到算法的执行时间。

示例如下

#include <stdio.h>
int main()
{
    int a = 1;
    int b = 2;
    int c = a + b;
    for (int i = 0; i < 10; i++)
    {
        printf("%d", c);
    }
    return 0;
}

O(n²) 平方阶

联系上文，双层循环就是平方阶，同理，三次循环就是立方阶，k 次循环就是 k 次方阶。

O(logn) 对数阶

二分查找，二叉树之类的问题中会见到比较多的对数阶复杂度

示例

#include <stdio.h>
int main()
{   int i=1;
    int j=2;
    int n = 100;
    while (i <= n) {
    i = i * j;
    }
    return 0;
}

可以判断 2^x=n ，x=log2n，所以时间复杂度就是 O($\log_{2}{n}$)。

再看下面一个示例

#include <stdio.h>
int main()
{
    int i = 1;
    int n = 100000000000000000000000;
    while (i <= n) {
    i = i * 300;
    }
    return 0;
}

可以判断 300^x=n ，x=log300n，复杂度就是 O($\log_{300}{n}$)。但是 在算法中有一个原则，那就是常量可以被忽略,所以根据对数换底公式可得，$\log_{300}{n}$=$\log_{300}{2}$ * $\log_{2}{n}$，即O($\log_{300}{n}$) = O($\log_{2}{n}$)，所以 O($\log_{300}{n}$) 就是 O(logn)。

对于一个算法的复杂度是否是对数阶，还有一个简易的判断方法：当循环中下标以指定倍数形式衰减，那么这就是一个对数阶。

O(nlogn) 线性对数阶

线性对数阶就是 O(nlogn)，也就是 O(n) * O(logn)，也就是 O(n) 的复杂度乘以 O(logn) 的复杂度。

即在对数阶的算法中再嵌一层循环就是线性对数阶

还有很多其他复杂度，由于不常用，网上资料较少，因此我选择就此而止

时间复杂度类型

根据实际情况，又可以将时间复杂度从以下四个方面来进一步分析：

• 最好时间复杂度

以冒泡算法为例

#include <stdio.h>
int main(){
int ar[10] = { 737, 8080, 80, 443, 101, 502, 404, 114514, 1452, 54188 };
for (int i = 0; i < 10; i++)
{
    bool flag = true;
    for (int j = 0; j < 10 - i - 1; j++)
    {
        if (ar[j] > ar[j + 1])
        {
            int temp = ar[j];
            printf("%d\n", ar[j]);
            ar[j] = ar[j + 1];
            ar[j + 1] = temp;
            printf("%d\n",ar[j]);
            flag = false;
        }
    }
    if (flag)
    {
        break;
    }
}
//迫真写法
printf("%d\n", ar[0]);
printf("%d\n", ar[1]);
printf("%d\n", ar[2]);
printf("%d\n", ar[3]);
printf("%d\n", ar[4]);
printf("%d\n", ar[5]);
printf("%d\n", ar[6]); 
printf("%d\n", ar[7]);
printf("%d\n", ar[8]);
printf("%d\n", ar[9]);
return 0;
}

结果：
可以看到，由于数组的元素实际上不确定的，这个循环体到底会循环多少次是不确定的，可能是 1 次，也可能是 n（假设数组的长度） 次，所以假如我们要找的元素就在数组中的第一个位置，那么我循环一次就找到了，这个算法的复杂度就是 O(1)，这就是最好情况时间复杂度。

• 最坏时间复杂度

即数组中不存在我要找到元素，或者说最后一个值才是我要找的元素，那么这样我就必须循环完整个数组，那么时间复杂度就是 O(n)，这也就是最坏时间复杂度。

• 平均时间复杂度

平均时间复杂度就是将所有可能的输入实例等概率出现的情况下，该算法的期望运行时间。

• 均摊时间复杂度

均摊时间复杂度是一种特殊的平均时间复杂度。

空间复杂度

空间复杂度全称就是渐进空间复杂度，用来表示算法的存储空间与数据规模之间的增长关系。空间复杂度也是用大 O 进行表示。

主要就看我们在一个算法当中到底有没有使用到了额外的空间来进行存储数据，然后判断这个额外空间的大小会不会随着 n 的变化而变化，从而得到空间复杂度。(与时间复杂度很相似)

简单排序算法

• 冒泡排序

概念:

重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法名是因为越小的元素会经由交换慢慢”浮”到数列的顶端，像泡泡一样。（优化版如下，立个标志即可）时间复杂度为$O(n)$~$O(n^2)$

例

    #include <stdio.h>
        int main(){
        int ar[10] = { 737, 8080, 80, 443, 101, 502, 404, 114514, 1452, 54188 };
        for (int i = 0; i < 10; i++)
        {
            bool flag = true;
            for (int j = 0; j < 10 - i - 1; j++)
            {
                if (ar[j] > ar[j + 1])
                {
                    int temp = ar[j];
                    printf("%d\n", ar[j]);
                    ar[j] = ar[j + 1];
                    ar[j + 1] = temp;
                    printf("%d\n",ar[j]);
                    flag = false;
                }
            }
            if (flag)
            {
                break;
            }
        }
        //迫真写法
        printf("%d\n", ar[0]);
        printf("%d\n", ar[1]);
        printf("%d\n", ar[2]);
        printf("%d\n", ar[3]);
        printf("%d\n", ar[4]);
        printf("%d\n", ar[5]);
        printf("%d\n", ar[6]); 
        printf("%d\n", ar[7]);
        printf("%d\n", ar[8]);
        printf("%d\n", ar[9]);
        return 0;
        }

结果：

• 选择排序

概念:

开启一个循环，每轮从未排序区间选择最小（大）的元素，将其放到已排序区间的开头/末尾。 时间复杂度为 $O(n²)$。

示例

    #include <stdio.h>

    void swap(int* a, int* b)
        {
        int temp = *a;
        *a = *b;
        *b = temp;
        }
    void selection_sort(int arr[], int len)
    {
            int i, j;

        for (i = 0; i < len - 1; i++)
        {
            int min = i;
            for (j = i + 1; j < len; j++)     
                if (arr[j] < arr[min])    
                    min = j;    
                swap(&arr[min], &arr[i]);  
        }
    }
    int main()
    {
        int tmp;
        int ar[10] = { 737, 8080, 80, 443, 101, 502, 404, 114514, 1452, 54188 };
        selection_sort(ar,10);
        printf("%d\n", ar[0]);
        printf("%d\n", ar[1]);
        printf("%d\n", ar[2]);
        printf("%d\n", ar[3]);
        printf("%d\n", ar[4]);
        printf("%d\n", ar[5]);
        printf("%d\n", ar[6]);
        printf("%d\n", ar[7]);
        printf("%d\n", ar[8]);
        printf("%d\n", ar[9]);
        return 0;
    }

} 

• 插入排序

概念:

将数组中的数据分为两个区间，已排序区间和未排序区间。初始已排序区间只有一个元素，就是数组的第一个元素。插入算法的核心思想是取未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入，并保证已排序区间数据一直有序。重复这个过程，直到未排序区间中元素为空，算法结束。(有一些类似整理扑克牌的过程)
时间复杂度为 $O(n)$~$O(n^2)$

示例

    #include<iostream>

    void InsertSort(int a[], int l)
    {
        int temp;
        int j;
        for (int i = 1; i < l; i++)
        {
            if (a[i] < a[i - 1])
            {
                temp = a[i];
                for (j = i - 1; j >= 0 && temp < a[j]; j--)
                {
                    a[j + 1] = a[j];
                }
            a[j + 1] = temp;

            }
            for (int k = 0; k < l; k++)
                std::cout << a[k] << " ";
            std::cout << std::endl;

        }
    }


    int main()
    {
        int a[10] = { 114514,1452,1024,54188,1453,911,114,514,101,404 };
        int b[10] = { 1,2,3,4,5,6,7,8,9 };
        int len = 10;
        InsertSort(a, len);
        for (int m = 0; m < 10; m++) {
            std::cout << std::endl<< a[m] << std::endl;
        }
    }

• 希尔排序

  概念:

希尔排序（Shell sort）是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至 1 时，整个文件恰被分成一组，算法便终止。

• 归并排序

• 快速排序

• 堆排序

• 计数排序

• 桶排序

• 基数排序