快速排序算法的比较。
在排序一个所有元素均相同的数组的时候:
qsort1每一次递归调用排序区间只能缩减1，只能排序好一个数字，可以从代码qsort1(m+1,u)中体现。因为所有元素相同时，qsort中m值执行的时候不会发生变化。qsort1排序区间的缩小只能体现在
qsort1(m+1,u)中。即要执行n-1次qsort1递归调用。每次qsort1递归调用,需进行<=n-1次比较，即上限为o(n)的次比较。
改进后快速排序在遇到相等元素的时候停止扫描，并且交换这些元素。
总结:swap执行总次数为n-1次,比较次数上限为o(n^2)。
qsort3:采用两个索引同时执行的方法。每一次递归调用，大约能使排序区间缩减一半，每一次i>j的时候停止当前的递归调用。总计o(lgn)次的递归调用。
每一次递归调用，需进行o(n)次比较，o(n)次交换，时间复杂度大约为O(nlogn)。注:这个时间复杂度只是针对所有元素相同的特殊情形
开始想着把do while的循环改成while循环。实际上是不是很方便。因为while(true)循环中i要先自増而不管循环条件是否成立
用了类似的代码
int i=l+1;
int j=u;
//i stop on element>=t
//j stop on element<=t
while(true){
while(i<=u&&x[i]<t)
i++
while(x[j]>t)
j--;
if(i>j)
break;
swap(x[i],x[j]);
}
结果导致某些情况下i==j,直接死循环了。而do while循环不会出现这种情况
#include<iostream>
#include<cstdlib>
using namespace std;
void swap(int &i,int &j){
int temp=i;
i=j;
j=temp;
}
void qsort3(int *x,int l,int u){
if(l>=u)return;
swap(x[l],x[l+rand()%(u-l)]);
int t=x[l];
int i=l;
int j=u+1;
//i stop on element>=t
//j stop on element<=t
while(true){
do{
i++;
}while(i<=u&&x[i]<t);
do{
j--;
}while(x[j]>t);
if(i>j)
break;
swap(x[i],x[j]);
}
swap(x[l],x[j]);
qsort3(x,l,j-1);
qsort3(x,j+1,u);
}
int main(){
int x[]={3,6,7,10,3,2,1};
qsort3(x,0,6);
for(int i=0;i<=6;i++)
cout<<x[i]<<endl;
return 0;
}
快速排序是一种分治的算法，快排的关键在于partition算法
下面这种快排算法来自Algorithms(By Robert Sedgewick,Kevin Wayne)
void qsort(int *x,int l,int u){
if(l>=u)return;
//swap(x[l],x[l+rand()%(u-l)]);
int t=x[l];
//i and j initialize to value beyond
//numbers to be sorted
int i=l;
int j=u+1;
//i stop on element>=t
//j stop on element<=t
while(true){
//i<u to ensure access
//within the valid range
while(x[++i]<t){
if(i>=u)
break;
}
while(x[--j]>t){}
if(i>=j)
break;
swap(x[i],x[j]);
}
swap(x[l],x[j]);
qsort(x,l,j-1);
qsort(x,j+1,u);
}
接下来的快排版本不保证正确性，暂时没有发现错误
void qsort3(int *x,int l,int u){
if(l>=u)
return;
//swap(x[l],x[l+rand()%(u-l)]);
int t=x[l];
int i=l+1;
int j=u;
//i stop on element>=t
//j stop on element<=t
while(true){
while(x[i]<=t){
if(i>=u)break;
i++;
}
while(x[j]>t){
j--;
}
if(i>=j)
break;
swap(x[i],x[j]);
}
swap(x[l],x[j]);
qsort3(x,l,j-1);
qsort3(x,j+1,u);
}