|
http://blog.csdn.net/ltyqljhwcm/article/details/52155097?locationNum=6&fps=1这篇文章对手摇算法以及归并排序有很详细的讲解！！
手摇算法就是空间复杂度为O(1)，仅仅是依靠交换操作来对字符串进行处理。
利用手摇算法实现归并排序，主要需要三个变量：
i指向右边待排序列将要插入的左边序列的位置；
index指向右边待排序列的初始位置；
j指向右边待排序列的末尾位置的后一个位置；
也就是将右边index-----j-1之间的序列插入到左边i的前面的位置；也就是将index-------j-1和i-------index-1这两个数据块交换位置；
class MergeSort {
public:
int* mergeSort(int* A, int n) {
// write code here
mergeSort(A,0,n-1);
return A;
}
void mergeSort(int* A,int start,int end){
if(start>=end)
return;
int middle=(start+end)/2;
mergeSort(A,start,middle);
mergeSort(A,middle+1,end);
merging(A,start,middle,end);
}
void merging(int* A,int start, int middle, int end){
int i=start;
int index=middle+1;
int j=middle+1;
while(j<=end&&i<j){
while(A[i]<=A[j]&&i<j){
i=i+1;
}
if(i>=j)
break;//说明此时已经排序结束
while(A[j]<A[i]&&j<=end){
j=j+1;
}
reverse(A,index,j-1);
reverse(A,i,index-1);
reverse(A,i,j-1);
i=i+(j-index);
index=j;
}
}
void reverse(int* A,int left,int right){
if(left==right)
return;
while(left<=right){
int temp;
int* p;
int* q;
p=&A[left];
q=&A[right];
temp=*p;
*p=*q;
*q=temp;
left=left+1;
right=right-1;
}
}
};
对于上面的归并排序来说，空间复杂度为o（1）,而时间复杂度为O(n*logn)--O(n*n*logn)。 | 
转播
