排序算法实现(二)
);
swap(v,left,last);//move the depart element to the right place
qsort(v,left,last-1);//the left half
qsort(v,last+1,right);//the right half
}
void swap(int v[],int i,int j)
{
int temp;
temp=v[i];
v[i]=v[j];
v[j]=temp;
}
从左右向中间判断，取中间值为分划枢纽：
[cpp]
template
void insertionSort(vector& a,int left,int right)
{
int j;
for(int p=left+1;p<=right;p++)
{
Comparable tmp=a[p];
for(j=p;j>0&&tmp
a[j]=a[j-1];
a[j]=tmp;
}
}
/**
*Return median of left,center,right.
*Order these and hide the pivot.
*/
template
const Comparable& median3(vector& a,int left,int right)
{
int center=(left+right)/2;
if(a[center]
swap(a[left],a[center]);
if(a[right]
swap(a[right],a[left]);
if(a[right]
swap(a[right],a[center]);
swap(a[center],a[right-1]);//place pivot at position right-1
return a[right-1];
}
template
void quicksort(vector& a,int left,int right)
{
if(left+10<=right)//qsort
{
Comparable pivot=median3(a,left,right);
//Begin partitioning
int i=left,j=right-1;
for(;;)
{
while(a[++i]
while(pivot
if(i
swap(a[i],a[j]);
else
break;
}
swap(a[i],a[right-1]);//Restore pivot
quicksort(a,left,i-1);
quicksort(a,i+1,right);
}
else//insertion sort on the subarray
insertionSort(a,left,right);
}
template
void quicksort(vector& a)
{
quicksort(a,0,a.size()-1);
}
快速选择：
[cpp]
//to find the kth smallest
//place it in a[k-1]
template
void quickSelect(vector& a,int left,int right,int k)
{
if(left+10<=right)//qsort
{
Comparable pivot=median3(a,left,right);
//Begin partitioning
int i=left,j=right-1;
for(;;)
{
while(a[++i]
while(pivot
if(i
swap(a[i],a[j]);
else
break;
}
swap(a[i],a[right-1]);//Restore pivot
if(k<=i)
quickSelect(a,left,i-1,k);
else if(k>i+1)
quickSelect(a,i+1,right,k);
//succeed !!
}
else//insertion sort on the subarray
insertionSort(a,left,right);
}
最坏是O(N^2)，平均为O(N)
6.间接排序（对象占用空间大，复制开销大）
[cpp]
template
class Pointer
{
public:
Pointer(Comparable *rhs=NULL):pointee(rhs){};
bool operator<(const Pointer& rhs)const//for compare in quicksort
{
return *pointee<*rhs.pointee;
}
operator Comparable*()const//类型转换
{
return pointee;
}
private:
Comparable* pointee;
};
template
void largeObjectSort(vector& a)
{
vector > p(a.size());
int i,j,nextj;