快速排序

快速排序是对冒泡排序的一种改进。它的基本思想是,通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。

       假设待排序的序列为{a[L],a[L+1],a[L+2],……,a[R]},首先任意选取一个记录(通常可选中间一个记作为枢轴或支点),然后重新排列其余记录,将所有关键字小于它的记录都放在左子序列中,所有关键字大于它的记录都放在右子序列中。由此可以将该“支点”记录所在的位置mid作分界线,将序列分割成两个子序列和。这个过程称作一趟快速排序(或一次划分)。

        一趟快速排序的具体做法是:附设两个指针i和j,它们的初值分别为L和R,设枢轴记录取mid,则首先从j所指位置起向前搜索找到第一个关键字小于的mid的记录,然后从i所指位置起向后搜索,找到第一个关键字大于mid的记录,将它们互相交换,重复这两步直至i>j为止。

       快速排序的时间的复杂性是O(nlog2n),速度快,但它是不稳定的排序方法。就平均时间而言,快速排序是目前被认为是最好的一种内部排序方法

       由以上讨论可知,从时间上看,快速排序的平均性能优于前面讨论过的各种排序方法,但快速排序需一个栈空间来实现递归。若每一趟排序都将记录序列均匀地分割成长度相接近的两个子序列,则栈的最大深度为log(n+1)。

 1 #include<iostream>
 2 #include<algorithm> 
 3 using namespace std;
 4 int a[10001];
 5 
 6 int n;
 7 void qsort(int l,int r)
 8 {
 9     int i=l;
10     int j=r;
11     int mid=a[(l+r)/2];
12     do
13     {
14         while(a[i]<mid&&i<=j)
15         {
16             i++;
17         }
18         while(a[j]>mid&&i<=j)
19         j--;
20         if(i<=j)
21         {
22             swap(a[i],a[j]);
23             i++;
24             j--;
25         }
26     }while(i<=j);
27     if(l<j)
28     qsort(l,j);
29     if(i<r)
30     qsort(i,r);
31 }
32 int main()
33 {
34     
35     cin>>n;
36     for(int i=0;i<n;i++)
37     {
38         cin>>a[i];
39     }
40     qsort(0,n-1);
41     for(int i=0;i<n;i++)
42     cout<<a[i]<<" ";
43     return 0;
44 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏AI派

TensorFlow 修炼之道(1)——张量(Tensor)

TensorFlow名字可以拆解为两部分:Tensor、Flow。其中,Tensor 就表示张量。

53640
来自专栏书山有路勤为径

包含min函数的栈

LeetCode 155. Min Stack 设计一个栈,支持如下操作,这些操作的算法复杂度需要是常数级,O(1) 1.push(x) : 将元素x压入...

10910
来自专栏C语言及其他语言

数组

1、 一维数组的定义和使用 通过对前面知识的学习,我们已经知道如何定义和使用一个一个的各种变量,但总有不够用的时候。举个例子,我要记录一个班32个同学C语...

42780
来自专栏我是攻城师

理解桶排序算法原理

计数排序,基数排序,桶排序是所有排序算法里面时间复杂度能达到O(N)级别的算法,这主要原因是因为他们不采用基于比较的算法,前面的文章已经介绍了计数排序的原理,本...

72140
来自专栏ACM算法日常

HDU1106:排序 (重新修正)

之前发过一篇HDU 1106的题目,但是因为有童鞋说那篇的源码提交后超时,我们的AlphaWA童鞋重新做了一遍,这次是0ms!算是修正之前的问题,非常感谢~

9510
来自专栏小樱的经验随笔

UVA 11636-Hello World!(水题,猜结论) UVA11636-Hello World!

UVA11636-Hello World! Time limit: 1.000 seconds When you first made the computer ...

38140
来自专栏云霄雨霁

字符串排序----三向字符串快速排序

25200
来自专栏静默虚空的博客

排序五 简单选择排序

要点 简单选择排序是一种选择排序。 选择排序:每趟从待排序的记录中选出关键字最小的记录,顺序放在已排序的记录序列末尾,直到全部排序结束为止。 简单排序处理流程 ...

21490
来自专栏Jed的技术阶梯

图解冒泡排序

在上面实现的代码中,即使n个数本来就是有序的,也会进行(n-1)次排序(只比较,不交换) 优化:当数组已经有序后,就中断循环

22030
来自专栏人工智能LeadAI

查找排序数组的最小值(js)

在由小到大已排序的未知数组中,以某个元素为支点旋转(好比将序列沿着前后顺序围成环移动)得到了一个数组,请找出该数组的最小值。比如倘若原数组(对我们而言,并不知道...

20840

扫码关注云+社区

领取腾讯云代金券