快速排序在最坏情况下的时间复杂度为（快速排序）

你们好，最近小时发现有诸多的小伙伴们对于快速排序在最坏情况下的时间复杂度为，快速排序这个问题都颇为感兴趣的，今天小活为大家梳理了下，一起往下看看吧。

1、 快速排序作为与冒泡排序相同的排序(与交换排序相同的排序)而广为人知，因为它解决了冒泡排序只用于比较两个相邻元素，所以在交换两个相邻元素时只能消除一个逆序的问题。

2、 And快速排序通过交换两个不相邻的元素，消除了待排序记录中的多个逆序。即快速排序中的一次交换可以消除多个反向序列。具体思路：从要排序的记录中选择一条记录(通常选择第一条记录，

3、 当然也可以随机划分，这样可以大大提高执行效率快速排序，我们知道的，在O(n))的时间复杂度内找到前k个元素的算法，将其关键字记录为K1，然后将其他关键字小于K1的记录移到前面。

4、 而那些大于关键字K1的被移到后面。经过一趟快速排序，将待排序的序列分成两个子表，最后在两个子表的边界处插入关键字K1。具体实现是使用三层while循环。

5、 最外层的while循环控制行程是否快速，内层的两个while循环用于从左到右扫描大于基准记录关键字的元素和从右到左扫描小于基准记录关键字的元素。

6、 可以用low和high两个指针分别指向当前记录当前从左到右和从右到左扫描的关键词，找到一个就交换。以上是行程的思路快速排序，对以上划分的子表重复以上过程。

7、 直到被划分的子表的长度不超过1。即快速排序的思想，从定义上看快速排序是递归排序。具体代码如下：

8、 #includeiostream

9、 using namespace std;

10、 const int len=7;

11、 Int qk(int a[]，int low，int high)//注意快速排序函数的参数，因为每次传递的函数快速排序是把数组分成两部分，第一部分不大于k，

12、 后一部分不小于k，然后对前一部分和后一部分进行//快速排序，所以qk的第二个参数和第三个参数应该是低高。

13、 {

14、 int x=a[低]；//选择第一个元素作为基准记录。

15、 while(lowhigh)

16、 {

17、 while(lowhigha[high]=x)

18、 high--;

19、 if(lowhigh)

20、 {

21、 a[low]=a[high];

22、 low++;

23、 }

24、 while(lowhigha[low]=x)

25、 low++;

26、 if(lowhigh)

27、 {

28、 a[high]=a[low];

29、 high--;

30、 }

31、 }

32、 a[low]=x;

33、 return low;

34、 }

35、 void qsort(int a[],int low,int high)

36、 {

37、 if(lowhigh)

38、 {

39、 int pos=qk(a,low,high);

40、 qsort(a,low,pos-1);

41、 qsort(a,pos+1,high);

42、 }

43、 }

44、 void main()

45、 {

46、 int a[len]={7,4,5,1,2,3,6};

47、 cout'快速排序之后的结果是：' endl

48、 qsort(a,0,len-1);

49、 for(int i=0;ilen;i++)

50、 {

51、 couta[i]' ';

52、 }

53、 coutendl;

54、 }

55、 复杂度分析快速排序最好的情况是序列在每一遍排序中分成两部分，表在表中间分成两个大小相同的子表，类似于半搜索，复杂度为O(nlog2n)。

56、 最坏的情况是序列已经排列好了，那么第一遍比较n-1次，第一条记录设置在原来的位置，左边子表为空，右边子表为n-1条记录，第二遍比较n-2次。

57、 第二条记录被设置在原始位置.即此时快速排序，内层的两个while循环没有执行，此时快速排序退化为冒泡排序，比较总数为n*(n-1)/2，复杂度为O(n*n)。

以上就是快速排序这篇文章的一些介绍，希望对大家有所帮助。

　　免责声明：本文由用户上传，与本网站立场无关。财经信息仅供读者参考，并不构成投资建议。投资者据此操作，风险自担。 如有侵权请联系删除！