当前位置:首页 > c++ > 正文内容

三大经典排序 | 冒泡排序,选择排序,快速排序

xuwenyan2年前 (2021-02-05)c++249

排序算法是日常使用最频繁的一个算法,生活中也很常见什么排队呀按照高矮次序呀,分数按照一个从高到低的排序等等,但是如果是要设计出来面对基数很大又要很快的排序方法这就是需要很大难度了,先给大家看看排序的种类有哪些,和其对应的时间空间复杂度。

 

最后一栏有个稳定性给看官解释一下:

稳定:如果 a 原本在 b 前面,而 a=b,排序之后 a 仍然在 b 的前面。
不稳定:如果 a 原本在 b 的前面,而 a=b,排序之后 a 可能会出现在 b 的后面。

1.冒泡排序

冒泡排序(Bubble Sort) 最为简单的一种排序,通过重复走完数组的所有元素,通过打擂台的方式两个两个比较,直到没有数可以交换的时候结束这个数,再到下个数,直到整个数组排好顺序。因一个个浮出所以叫冒泡排序。双重循环时间 O(n^2)

算法描述:

  1. 比较相邻两个数据如果。第一个比第二个大,就交换两个数

  2. 对每一个相邻的数做同样1的工作,这样从开始一队到结尾一队在最后的数就是最大的数。

  3. 针对所有元素上面的操作,除了最后一个。

  4. 重复1~3步骤,知道顺序完成。

代码可视化

 

代码实现:

 

2.选择排序

选择排序(Select Sort) 是直观的排序,通过确定一个 Key 最大或最小值,再从带排序的的数中找出最大或最小的交换到对应位置。再选择次之。双重循环时间复杂度为 O(n^2)

算法描述:

  1. 在一个长度为 N 的无序数组中,第一次遍历 n-1 个数找到最小的和第一个数交换。

  2. 第二次从下一个数开始遍历 n-2 个数,找到最小的数和第二个数交换。

  3. 重复以上操作直到第 n-1 次遍历最小的数和第 n-1 个数交换,排序完成。

算法可视化:

 

代码实现:

 

3.快速排序

快速排序(QuickSort)是排除稳定性因素后最常用的排序。给看官介绍两种使用方法,一种值直接在我文件 stdlib.h 头文件中的 qsort 函数实现是和正常写代码一样的。通过使用qsort(数组名,长度,sizeof(第一个数长度),compInc/comoDec) 进行实现数组的排序。后面的是通过递归调用的形式。

算法描述:

  1. 从数列中挑出一个元素作为基准。

  2. 重新排列数列,把所有的比基准小的放在基准前面,反之放在后面(一样大可任意一边)完成后基准处在分区的中间位置。

  3. 通过递归调用把小于基准元素和大雨基准元素的子序列进行排序。

算法可视化:

 

代码实现:

 

本文转载于知乎汤包:三大经典排序 | 冒泡排序,选择排序,快速排序

    文章作者:xuwenyan
    版权声明:本文转载于@汤包的文章:三大经典排序 | 冒泡排序,选择排序,快速排序,请遵守原作者协议。

    扫描二维码推送至手机访问。

    版权声明:本文由艺文笔记发布,如需转载请注明出处。

    本文链接:https://www.xuwenyan.com/archives/104

    标签: C++编程排序
    分享给朋友:

    “三大经典排序 | 冒泡排序,选择排序,快速排序” 的相关文章

    C++隐藏程序崩溃,让程序优雅的崩溃

    C++隐藏程序崩溃,让程序优雅的崩溃

    我们的程序并不能保证是完全稳定的,当程序崩溃时会展示一个崩溃提示框给用户,这给用户带来的感觉非常不友好。当我们的程序是一个服务程序时(没有ui界面),用户可能根本就感知不到这个程序的存在,这种情况下如果程序崩溃,在不显示崩溃提示的前提下,我们只需要将这个服务程序重启就可以了,这对用户来说可能会友好...

    C++指针*为什么靠后会比较好?

    C++指针*为什么靠后会比较好?

    大多数书中和大神的代码里,往往指针的*都是靠变量而不是靠类型的,这主要是为了不造成我们第一眼对变量类型的误解和对指针类型的误解,比如: int* p1,p2 我们一眼看上去是不是通常会觉得p1、p1都是一个int*的指针呢?因为我们通常会误把int*当作一个类型,然而无论int*还是i...

    C++如何获取控制台程序的输出内容?

    C++如何获取控制台程序的输出内容?

    很多工具程序(如ffmpeg)的进度显示往往都是以控制台字符显示的方法,我们可能需要调用这种控制台工具去完成工作,但同时又希望以友好的ui界面去显示当前的工作状态(如进度)。此时我们能想到的就是运行控制台程序,然后以某种方式去获取到控制台程序的输出,然后转换到我们的ui界面上去显示。 有多种...

    VC的ATL工程向导同时生成一个PS工程是做什么的?可以不要吗?

    VC的ATL工程向导同时生成一个PS工程是做什么的?可以不要吗?

    例如,我用VC2015的工程向导新建一个ATL的工程名字叫myAtl,那么VC会同时给我生成一个叫做myAtlPS的工程。这个myAtlPS工程是做什么的?什么情况下可以不需要它?什么情况下它又是必须存在的? PS工程是什么?可以不要吗? 这个PS工程叫做代理与存根(proxy&nbs...

    c++函数模板参数类型限定

    c++函数模板参数类型限定

    函数模板函数模板可以实现对不同数据类型做统一操作,比如比较两个数据的大小:template<typename T> bool compare(T& a,T& b) {   return a...

    static_assert和assert有什么区别?

    static_assert和assert有什么区别?

    static_assert和assert都是断言,都可用于判断一个条件是否成立,并且在条件不成立时及时给出错误提示。那它们用什么不同和需要注意的地方呢? 1:static_assert在编译期执行,而assert在运行期执行。2:static_assert无论在debug模式还是relea...