一般情况下,快速排序的时间复杂度是\(O(n logn)\)
在最坏的情况下,快速排序的时间复杂度是\(O(n^2)\)
void quick_sort(int q[],int l,int r){ if(l>=r)return; int i = l-1,j = r+1,mid = q[(l+r)/2]; while(i<j){ do i++;while(q[i]<mid); do j--;while(q[j]>mid); if(i<j)swap(q[i],q[j]); } quick_sort(q,l,j),quick(q,j+1,r); }
在这里,q是待排序的数组,l是左边界,r是右边界
int quick_choose(int q[],int l,int r,int k){ if(l>=r)return q[l]; int i = l-1,j = r+1,mid = q[(l+r)/2]; while(i<j){ do i++;while(q[i]<mid); do j--;while(q[j]>mid); if(i<j)swap(q[i],q[j]); } int sl = j-l+1; if(sl>=k)return quick_choose(q,l,j,k); else return quick_choose(q,j+1,r,k-sl); }
与快排的思路类似,可以快速找出数组q中l~r中第k大得数字。
c++中可以用库函数
sort(q,q+n)
nth_element(q,q+k-1,q+n);
注意这里的k是从1开始计的