当前位置:首页 > c++ > 排序算法-快速排序

排序算法-快速排序

xuwenyan10个月前 (12-13)c++750

排序算法的思想非常简单,在待排序的数列中,我们首先要找一个数字作为基准数(这只是个专用名词)。为了方便,我们一般选择第 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
    版权声明:本文为本站原创文章,转载请注明出处,非常感谢,如版权漏申明或您觉得任何有异议的地方欢迎与本站取得联系。
    标签: C++编程排序

    相关文章

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

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

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

    排序算法-冒泡排序

    排序算法-冒泡排序

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

    排序算法-选择排序

    排序算法-选择排序

    选择排序是一种简单直观的排序算法,无论什么数据进去都是 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...

    发表评论

    访客

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