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

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

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

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

 

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

稳定:如果 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++智能指针基本原理

    什么是智能指针? 最简单来说就是会自动释放内存的指针,使用方便,不用担心内存泄漏问题。它其实就是通过封装,利用对象的析构函数释放申请的内存,基本上自动释放的用法都是利用析构函数去做一些释放工作。如:自动释放的句柄 智能指针的基本实现 class TestClass { publ...

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

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

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

    解决程序在xp系统总是莫名奇妙的崩溃问题(/Zc:threadSafeInit- )

    解决程序在xp系统总是莫名奇妙的崩溃问题(/Zc:threadSafeInit- )

    现象:程序在xp系统上面总是莫名其妙的崩溃,检查代码看不出任何问题,感觉代码都很好。即使你远程调试,找到了崩溃的点,当你注释了崩溃点之后,还是会崩溃到别的地方。当你遇到了这种情况的时候,不妨参照一下下面的方法看看,说不定可以解决问题。如何解决?将崩溃程序相关的所有工程代码全部关闭全局变量的线程安全检...

    uafxcwd.lib(afxmem.obj) : error LNK2005:

    uafxcwd.lib(afxmem.obj) : error LNK2005: "void * __cdecl operator new(unsigned int)"解决办法

    如果在编译MFC程序的时候出现下列及类似的错误: 1˃uafxcwd.lib(afxmem.obj) : error LNK2005: "void * __cdecl operator new(unsigned int)" (??2@YAPAXI@Z) 已经在 LIBCMTD.lib(new...

    C++ 获取进程所在目录(进程全路径)

    C++ 获取进程所在目录(进程全路径)

    打开windows任务管理器,会看到很多的进程在运行,随机挑选一个,如何通过c++代码获取某一个进程的所在全路径呢?这也是在windows软件开发中经常遇到的需求。通过进程名获取进程全路径由于可能很多进程叫同一个名字,所以获得的结果也有可能是多个#include <windows.h...

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

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

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