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

排序算法-快速排序

xuwenyan1年前 (2021-12-13)c++248

排序算法的思想非常简单,在待排序的数列中,我们首先要找一个数字作为基准数(这只是个专用名词)。为了方便,我们一般选择第 1 个数字作为基准数(其实选择第几个并没有关系)。接下来我们需要把这个待排序的数列中小于基准数的元素移动到待排序的数列的左边,把大于基准数的元素移动到待排序的数列的右边。这时,左右两个分区的元素就相对有序了;接着把两个分区的元素分别按照上面两种方法继续对每个分区找出基准数,然后移动,直到各个分区只有一个数时为止。

这是典型的分治思想,即分治法。

快速排序由于排序效率在同为O(N*logN)的几种排序方法中效率较高,因此经常被采用。在平均状况下,排序 n 个项目要 Ο(nlogn) 次比较。在最坏状况下则需要 Ο(n2) 次比较,但这种状况并不常见。事实上,快速排序通常明显比其他 Ο(nlogn) 算法更快,因为它的内部循环(inner loop)可以在大部分的架构上很有效率地被实现出来。

起源

东尼·霍尔(C.R.A.Hoare)于1962年提出。

思想

分治法

时间复杂度

平摊O(N*logN),最坏O(n²)

最坏情况何时发生?

数组已是排好序的(无论是正序,还是倒序,或者相等)。

步骤

  • 先从数列中取出一个数作为基准数。

  • 分区过程,将比这个数大的数全放到它的右边,小于或等于它的数全放到它的左边。

  • 再对左右区间重复第二步,直到各区间只有一个数。

动图演示

 

代码实现

int Paritition(int num[], int l, int r) {
  int pivot = num[l];
  while (l < r) {
    while (l < r && num[r] >= pivot) {
      --r;
    }
    num[l] = num[r];
    while (l < r && num[l] <= pivot) {
      ++l;
    }
    num[r] = num[l];
  }
  num[l] = pivot;

  return l;
}

void QuikSort(int num[], int l, int r) {
  if (l < r) {
    int pivot = Paritition(num, l, r);
    QuikSort(num, l, pivot - 1);
    QuikSort(num, pivot + 1, r);
  }
}

void main(){
  int num[5] = {1,5,4,2,3};
  QuikSort(num,0,4);
}
    文章作者:xuwenyan
    版权声明:本文为本站原创文章,转载请注明出处,非常感谢,如版权漏申明或您觉得任何有异议的地方欢迎与本站取得联系。

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

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

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

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

    “排序算法-快速排序” 的相关文章

    C++实现任务栏图标进度条显示

    C++实现任务栏图标进度条显示

    ITaskbarList3* m_pTaskBarlist; VOID CALLBACK OnTimer(HWND hWnd, UINT, UINT_PTR id, DWORD) { if (id == 1) { static int progress = 0; if (pro...

    C++智能指针基本原理

    C++智能指针基本原理

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

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

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

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

    使用GDI、MFC_GDI、GDI+绘制数组RGBA序列

    使用GDI、MFC_GDI、GDI+绘制数组RGBA序列

    学习ffmpeg时遇到一个问题,ffmpeg解码出RGB颜色后怎么绘制到屏幕上,于是将GDI、MFC_GDI、GDI+等方式都记录一下 1:注意按windows的要求,R、G、B、A顺序要调整为B、G、R、A 。 2:GDI不支持透明通道A,透明通道A的值读进去以后没有作用。想要支持透...

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

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

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

    ATL实现windows右键菜单扩展(ContextMenu)

    ATL实现windows右键菜单扩展(ContextMenu)

    右键菜单,即用户右击shell对象时弹出的上下文菜单(context menu)。本文记录了如何创建右键菜单的基本过程,跟着步骤一步一步来,即可创建出一个右键菜单工程。第一步,新建一个ATL工程Visual Studio—>新建项目—>ATL—>使用默认配置(一直按下一步即可)。注...