快速排序
2021-02-02 07:17
标签：时间 return log col quic quicksort bsp index 快速排序 最坏时间复杂度O(n2)，最好和平均是O(n*log2n) 伪代码： 如果要改变选取枢纽值，比如随机选取而不是选最后一个数，则现将枢纽值和最后一个值交换，然后开始partition（即在行8前面先交换） 最坏情况：选取的值是最小或最大值 partition的时间与当前partition元素个数有关系 T(n)=T(n-1)+0+O(n)=T(n-1)+O(n) T(n-1) = T(n-2) + O(n-1) .... 所以T(n)=O(n)+O(n-1)+...+O(1)=O(n2) 最好情况：选取的值刚好是最中间的值 T(n)=2T(n/2) + n T(n/2)=2T(n/4) + n/2 .... 上面共log2n项，所以 T(n)=2(2T(n/4)+n/2)+n = 4T(n/4)+2n =4(2T(T/8)+n/4)+2n = 8T(n/8)+3n =....=2x T(n/2x) +xn 当x为log2n =nT(1)+nlog2n 所以最好情况复杂度为O(n*log2n) 快速排序 标签：时间 return log col quic quicksort bsp index 快速排序 原文地址：https://www.cnblogs.com/taoXiang/p/12810611.html 1 QuickSort(A,low,high)
2 if(lowhigh)
3 index = Partition(A,low,high)
4 QuickSort(A,low,index-1)
5 QuickSort(A,index+1,high)
6
7 Partition(A,low,high)
8 x = A[high]
9 i = low-1
10 for j=low to high-1
11 if (A[j]x)
12 i++
13 if(i!=j) swap(A,i,j)
14 swap(A,i+1,high)
15 return i+1