当前位置:首页 > c++ > 三大经典排序 | 冒泡排序,选择排序,快速排序

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

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

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

 

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

稳定:如果 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
    版权声明:本文转载于@汤包的文章:三大经典排序 | 冒泡排序,选择排序,快速排序,请遵守原作者协议。
    标签: C++编程排序

    相关文章

    排序算法-快速排序

    排序算法-快速排序

    排序算法的思想非常简单,在待排序的数列中,我们首先要找一个数字作为基准数(这只是个专用名词)。为了方便,我们一般选择第 1 个数字作为基准数(其实选择第几个并没有关系)。接下来我们需要把这个待排序的数...

    排序算法-冒泡排序

    排序算法-冒泡排序

    冒泡排序也是一种简单直观的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法...

    排序算法-选择排序

    排序算法-选择排序

    选择排序是一种简单直观的排序算法,无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候,数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。时间复杂度O(n²)最坏情况合适发生?...

    大端模式和小端模式的区别以及如何判断大小端

    大端模式和小端模式的区别以及如何判断大小端

    在计算中,字节顺序是指数字的二进制表示内的字节(或有时是位)的顺序。它也可以更普遍地用于指代任何表示的内部排序,例如数字系统中的数字或日期的部分。在最常见的用法中,字节顺序表示多字节数字内的字节顺序,...

    c++使用libcurl实现断点续传

    c++使用libcurl实现断点续传

    libcurl实现断点续传大致需要两个关键点:1:使用GetFileSize接口获取本地已缓存文件的大小。2:通过curl_easy_setopt接口的CURLOPT_RESUME_FROM_LARG...

    std::make_shared有什么好处?

    std::make_shared有什么好处?

    为什么使用std::make_shared,std::make_shared有什么好处?如下: 更美观的代码std::shared_ptr<Node> ptr(new Node);std...

    发表评论

    访客

    ◎欢迎参与讨论,请在这里发表您的看法和观点。