您当前的位置:首页 > 电脑百科 > 程序开发 > 算法

简述几种常用的排序算法

时间:2023-03-27 14:11:57  来源:  作者:华为云开发者联盟

本文分享自华为云社区《深入浅出八种排序算法-云社区-华为云》,作者:嵌入式视觉 。

归并排序和快速排序是两种稍微复杂的排序算法,它们用的都是分治的思想,代码都通过递归来实现,过程非常相似。理解归并排序的重点是理解递推公式和 merge() 合并函数。

一,冒泡排序(Bubble Sort)

排序算法是程序员必须了解和熟悉的一类算法,排序算法有很多种,基础的如:冒泡、插入、选择、快速、归并、计数、基数和桶排序等。

冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较,看是否满足大小关系要求,如果不满足就让它俩互换。一次冒泡会让至少一个元素移动到它应该在的位置,重复 n 次,就完成了 n 个数据的排序工作。

总结:如果数组有 n 个元素,最坏情况下,需要进行 n 次冒泡操作。

基础的冒泡排序算法的 C++ 代码如下:

// 将数据从小到大排序
void bubbleSort(int array[], int n){
    if (n<=1) return;
    for(int i=0; i<n; i++){
        for(int j=0; j<n-i; j++){
            if (temp > a[j+1]){
                temp = array[j]
                a[j] = a[j+1];
                a[j+1] = temp;
            }
        }
    }
}

实际上,以上的冒泡排序算法还可以优化,当某次冒泡操作已经不再进行数据交换时,说明数组已经达到有序,就不需要再继续执行后续的冒泡操作了。优化后的代码如下:

// 将数据从小到大排序
void bubbleSort(int array[], int n){
    if (n<=1) return;
    for(int i=0; i<n; i++){
        // 提前退出冒泡循环发标志位
        bool flag = False;
        for(int j=0; j<n-i; j++){
            if (temp > a[j+1]){
                temp = array[j]
                a[j] = a[j+1];
                a[j+1] = temp;
                flag = True; // 表示本次冒泡操作存在数据交换
            }
        }
        if(!flag) break;  // 没有数据交换,提交退出
    }
}

冒泡排序的特点

  1. 冒泡过程只涉及相邻元素的交换,只需要常量级的临时空间,故空间复杂度为O(1),是原地排序算法
  2. 当有相邻的两个元素大小相等的时候,我们不做交换,相同大小的数据在排序前后不会改变顺序,所以是稳定排序算法
  3. 最坏情况和平均时间复杂度都为O(n2),最好时间复杂度是O(n)。

二,插入排序(Insertion Sort)

  1. 插入排序算法将数组中的数据分为两个区间:已排序区间和未排序区间。最初始的已排序区间只有一个元素,就是数组的第一个元素。
  2. 插入排序算法的核心思想就是取未排序区间的一个元素,在已排序区间中找到一个合适的位置插入,并保证已排序区间数据一直有序。
  3. 重复这个过程,直到未排序区间元素为空,则算法结束。

插入排序和冒泡排序一样,也包含两种操作,一种是元素的比较,一种是元素的移动
当我们需要将一个数据 a 插入到已排序区间时,需要拿 a 与已排序区间的元素依次比较大小,找到合适的插入位置。找到插入点之后,我们还需要将插入点之后的元素顺序往后移动一位,这样才能腾出位置给元素 a 插入。

插入排序的 C++ 代码实现如下:

void InsertSort(int a[], int n){
    if (n <= 1) return;
    for (int i = 1; i < n; i++)  // 未排序区间范围
    {
        
        key  = a[i];    // 待排序第一个元素
        int j = i - 1;  // 已排序区间末尾元素
        // 从尾到头查找插入点方法
        while(key < a[j] && j >= 0){  // 元素比较
            a[j+1] = a[j];  // 数据向后移动一位
            j--;
        }
        a[j+1] = key;   // 插入数据
    }
}

插入排序的特点:

  1. 插入排序并不需要额外存储空间,空间复杂度是O(1),所以插入排序也是一个原地排序算法。
  2. 在插入排序中,对于值相同的元素,我们可以选择将后面出现的元素,插入到前面出现元素的后面,这样就可以保持原有的前后顺序不变,所以插入排序是稳定的排序算法。
  3. 最坏情况和平均时间复杂度都为O(n2),最好时间复杂度是O(n)。

三,选择排序(Selection Sort)

选择排序算法的实现思路有点类似插入排序,也分已排序区间和未排序区间。但是选择排序每次会从未排序区间中找到最小的元素,将其放到已排序区间的末尾。

选择排序的最好情况时间复杂度、最坏情况和平均情况时间复杂度都为O(n2),是原地排序算法,且是不稳定的排序算法

选择排序的 C++ 代码实现如下:

void SelectSort(int a[], int n){
    for(int i=0; i<n; i++){
        int minIndex = i;
        for(int j = i;j<n;j++){
            if (a[j] < a[minIndex]) minIndex = j;
        }
        if (minIndex != i){
            temp = a[i]; 
            a[i] = a[minIndex];
            a[minIndex] = temp;
        }
    }
}

冒泡插入选择排序总结

 

这三种排序算法,实现代码都非常简单,对于小规模数据的排序,用起来非常高效。但是在大规模数据排序的时候,这个时间复杂度还是稍微有点高,所以更倾向于用时间复杂度为O(nlogn) 的排序算法。

特定算法是依赖特定的数据结构的。以上三种排序算法,都是基于数组实现的。

四,归并排序(Merge Sort)

归并排序的核心思想比较简单。如果要排序一个数组,我们先把数组从中间分成前后两部分,然后对前后两部分分别排序,再将排好序的两部分合并在一起,这样整个数组就都有序了。

归并排序使用的是分治思想。分治,顾名思义,就是分而治之,将一个大问题分解成小的子问题来解决。小的子问题解决了,大问题也就解决了。

分治思想和递归思想有些类似,分治算法一般用递归实现。分治是一种解决问题的处理思想,递归是一种编程技巧,这两者并不冲突。

知道了归并排序用的是分治思想,而分治思想一般用递归实现,接下来的重点就是如何用递归实现归并排序。写递归代码的技巧就是,分析问题得出递推公式,然后找到终止条件,最后将递推公式翻译成递归代码。所以,要想写出归并排序的代码,得先写出归并排序的递推公式

递推公式:
merge_sort(p…r) = merge(merge_sort(p…q), merge_sort(q+1…r))

终止条件:
p >= r 不用再继续分解,即区间数组元素为 1 

归并排序的伪代码如下:

merge_sort(A, n){
    merge_sort_c(A, 0, n-1)
}
merge_sort_c(A, p, r){
    // 递归终止条件
    if (p>=r) then return
    // 取 p、r 中间的位置为 q
    q = (p+r)/2
    // 分治递归
    merge_sort_c(A[p, q], p, q)
    merge_sort_c(A[q+1, r], q+1, r)
    // 将A[p...q]和A[q+1...r]合并为A[p...r]  
    merge(A[p...r], A[p...q], A[q+1...r])
}

4.1,归并排序性能分析

1,归并排序是一个稳定的排序算法。分析:伪代码中 merge_sort_c() 函数只是分解问题并没有涉及移动元素和比较大小,真正的元素比较和数据移动在 merge() 函数部分。在合并过程中保证值相同的元素合并前后的顺序不变,归并排序排序就是一个稳定的排序算法。

2,归并排序的执行效率与要排序的原始数组的有序程度无关,所以其时间复杂度是非常稳定的,不管是最好情况、最坏情况,还是平均情况,时间复杂度都是O(nlogn)。分析:不仅递归求解的问题可以写成递推公式,递归代码的时间复杂度也可以写成递推公式:

 

一步步分解推导可得T(n)=2k∗T(n/2k)+k∗n 。当T(n/2k)=T(1) 时,也就是n/2k=1,我们得到k=log2n 。我们将k 值代入上面的公式,得到T(n)=Cn+nlog2n 。如果我们用大 O 标记法来表示的话,T(n) 就等于O(nlogn)。所以归并排序的时间复杂度是O(nlogn)。

3,空间复杂度是 O(n)。分析:递归代码的空间复杂度并不能像时间复杂度那样累加。尽管算法的每次合并操作都需要申请额外的内存空间,但在合并完成之后,临时开辟的内存空间就被释放掉了。在任意时刻,CPU 只会有一个函数在执行,也就只会有一个临时的内存空间在使用。临时内存空间最大也不会超过 n 个数据的大小,所以空间复杂度是O(n)。

五,快速排序(Quicksort)

快排的思想是这样的:如果要排序数组中下标从 p 到 r 之间的一组数据,我们选择 p 到 r 之间的任意一个数据作为 pivot(分区点)。我们遍历 p 到 r 之间的数据,将小于 pivot 的放到左边,将大于 pivot 的放到右边,将 pivot 放到中间。经过这一步骤之后,数组 p 到 r 之间的数据就被分成了三个部分,前面 p 到 q-1 之间都是小于 pivot 的,中间是 pivot,后面的 q+1 到 r 之间是大于 pivot 的。

根据分治、递归的处理思想,我们可以用递归排序下标从 p 到 q-1 之间的数据和下标从 q+1 到 r 之间的数据,直到区间缩小为 1,就说明所有的数据都有序了。

递推公式如下:

递推公式:
quick_sort(p,r) = quick_sort(p, q-1) + quick_sort(q, r)
终止条件:
p >= r

归并排序和快速排序总结

归并排序和快速排序是两种稍微复杂的排序算法,它们用的都是分治的思想,代码都通过递归来实现,过程非常相似。理解归并排序的重点是理解递推公式和 merge() 合并函数。同理,理解快排的重点也是理解递推公式,还有 partition() 分区函数。

除了以上 5 种排序算法,还有 3 种时间复杂度是O(n) 的线性排序算法:桶排序、计数排序、基数排序。这八种排序算法性能总结如下图:

 

参考资料

  • 排序(上):为什么插入排序比冒泡排序更受欢迎?
  • 排序(下):如何用快排思想在O(n)内查找第K大元素?


Tags:算法   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,如有任何标注错误或版权侵犯请与我们联系(Email:2595517585@qq.com),我们将及时更正、删除,谢谢。
▌相关推荐
本文分享自华为云社区《深入浅出八种排序算法-云社区-华为云》,作者:嵌入式视觉 。归并排序和快速排序是两种稍微复杂的排序算法,它们用的都是分治的思想,代码都通过递归来实现,...【详细内容】
2023-03-27  Tags: 算法  点击:(0)  评论:(0)  加入收藏
近年来,随着算法强势崛起,用户简直被“宠上了天”。比如,打开资讯类APP,“爱看”的信息总是第一时间跃入眼帘;规划出行道路时,算法会把最短或最快的路线推荐给我们;点外卖时,平台会...【详细内容】
2023-03-24  Tags: 算法  点击:(4)  评论:(0)  加入收藏
18:00第1-10道大厂Java面试题:面试官:有了 for 循环 为什么还要 forEach ?面试官:jwt 是什么?java-jwt 呢?懵逼了。。。面试官:谈谈为什么要限流,有哪些限流方案?面试官:HTTPS...【详细内容】
2023-03-15  Tags: 算法  点击:(5)  评论:(0)  加入收藏
大家好,我是前端西瓜哥。今天来讲讲几何算法中,比较经典的算法:矩形碰撞和包含检测算法。矩形碰撞检测是被广泛使用的算法。比如在游戏中,为了优化图形碰撞判断效率(复杂不规则...【详细内容】
2023-03-13  Tags: 算法  点击:(7)  评论:(0)  加入收藏
一、概述三种时间复杂度是O(n)的线性排序算法:桶排序、计数排序、基数排序。二、相似点这三种排序算法都利用了桶的概念,但对桶的使用方法上有明显差异: 基数排序:根据键值的每...【详细内容】
2023-03-13  Tags: 算法  点击:(8)  评论:(0)  加入收藏
数据工程是有效管理大量数据的实践,从存储和处理到分析和可视化。因此,数据工程师必须精通数据结构和算法,以帮助他们有效地管理和操作数据。本文将探讨数据工程师应该熟悉的一...【详细内容】
2023-03-11  Tags: 算法  点击:(12)  评论:(0)  加入收藏
SnowFlake 算法,是 Twitter 开源的分布式 ID 生成算法。其核心思想就是:使用一个 64 bit 的 long 型的数字作为全局唯一 ID。在分布式系统中的应用十分广泛,且 ID 引入了时间戳...【详细内容】
2023-03-09  Tags: 算法  点击:(20)  评论:(0)  加入收藏
一、推荐业务简介首先介绍一下阿里健康的业务背景和对现状的分析。1、推荐场景展示可解释性推荐,举例而言,如下图中当当网“根据您浏览的商品推荐”(告诉用户推荐的理由)及淘宝...【详细内容】
2023-03-08  Tags: 算法  点击:(12)  评论:(0)  加入收藏
常见分布式协议和算法的说明和对比开发分布式系统最关键的就是根据场景特点,选择合适的算法,在一致性和可用性之间妥协折中,而妥协折中的关键就在于能否理解各算法的特点。分布...【详细内容】
2023-03-08  Tags: 算法  点击:(11)  评论:(0)  加入收藏
一、定义同冒泡排序一样,快速排序也属于交换排序,通过元素之间的比较和交换位置来达到排序的目的。不同的是,冒泡排序在每一轮中只把1个元素冒泡到数列的一端,而快速排序则在每...【详细内容】
2023-03-07  Tags: 算法  点击:(10)  评论:(0)  加入收藏
▌简易百科推荐
本文分享自华为云社区《深入浅出八种排序算法-云社区-华为云》,作者:嵌入式视觉 。归并排序和快速排序是两种稍微复杂的排序算法,它们用的都是分治的思想,代码都通过递归来实现,...【详细内容】
2023-03-27  华为云开发者联盟    Tags:算法   点击:(0)  评论:(0)  加入收藏
在PyTorch中有四种类型的乘法运算(位置乘法、点积、矩阵与向量乘法、矩阵乘法),非常容易搞混,我们一起来看看这四种乘法运算的区别。位置乘法先构建两个张量a,b他们都是4行5列。a...【详细内容】
2023-03-21  长颈鹿睡觉  今日头条  Tags:PyTorch   点击:(8)  评论:(0)  加入收藏
大家好,我是前端西瓜哥。今天来讲讲几何算法中,比较经典的算法:矩形碰撞和包含检测算法。矩形碰撞检测是被广泛使用的算法。比如在游戏中,为了优化图形碰撞判断效率(复杂不规则...【详细内容】
2023-03-13   前端西瓜哥  微信公众号  Tags:算法   点击:(7)  评论:(0)  加入收藏
一、概述三种时间复杂度是O(n)的线性排序算法:桶排序、计数排序、基数排序。二、相似点这三种排序算法都利用了桶的概念,但对桶的使用方法上有明显差异: 基数排序:根据键值的每...【详细内容】
2023-03-13  日拱一卒程序猿  今日头条  Tags:算法   点击:(8)  评论:(0)  加入收藏
SnowFlake 算法,是 Twitter 开源的分布式 ID 生成算法。其核心思想就是:使用一个 64 bit 的 long 型的数字作为全局唯一 ID。在分布式系统中的应用十分广泛,且 ID 引入了时间戳...【详细内容】
2023-03-09  雨夜青草  CSDN  Tags:雪花算法   点击:(20)  评论:(0)  加入收藏
很多时候需要用到连续的id进行数据对比,如判断是否连续等问题。那么,生成连续整数的方式有多种,首先容易想到的是逐步循环,如果想生成1kw条记录,则需要循环1kw次进行插入,那么有没...【详细内容】
2023-03-09  数据库干货铺  今日头条  Tags:整数   点击:(16)  评论:(0)  加入收藏
如何确定桶的 区间范围,有很多种不同的方式。我们这里创建的桶数量等于原始数列的元素数量,除最后一个桶只包含数列最大值外, 前面各个桶的区间按照比例来确定。一、定义桶排序...【详细内容】
2023-03-09  日拱一卒程序猿  今日头条  Tags:桶排序   点击:(13)  评论:(0)  加入收藏
一、推荐业务简介首先介绍一下阿里健康的业务背景和对现状的分析。1、推荐场景展示可解释性推荐,举例而言,如下图中当当网“根据您浏览的商品推荐”(告诉用户推荐的理由)及淘宝...【详细内容】
2023-03-08  DataFunTalk    Tags:算法   点击:(12)  评论:(0)  加入收藏
常见分布式协议和算法的说明和对比开发分布式系统最关键的就是根据场景特点,选择合适的算法,在一致性和可用性之间妥协折中,而妥协折中的关键就在于能否理解各算法的特点。分布...【详细内容】
2023-03-08  后端系统和架构  微信公众号  Tags:算法   点击:(11)  评论:(0)  加入收藏
一、定义同冒泡排序一样,快速排序也属于交换排序,通过元素之间的比较和交换位置来达到排序的目的。不同的是,冒泡排序在每一轮中只把1个元素冒泡到数列的一端,而快速排序则在每...【详细内容】
2023-03-07    今日头条  Tags:快速排序   点击:(10)  评论:(0)  加入收藏
站内最新
站内热门
站内头条