类似归并排序，只是不需要辅助空间。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47 |
#include<iostream>using
namespace std;int swap(int
ds[],int
begin,int
mid,int
end){ int
lb=begin; for(int
rb=mid;rb<end;rb++){ int
temp=ds[rb]; int
i=rb; for(;i>lb;i--) ds[i]=ds[i-1]; ds[i]=temp; lb++; } return
0;}int
spotMerge(int
ds[],int
begin,int
mid,int
end){ int
i=begin,j=mid+1,index=mid+1; while(i<j && i<=end && j<=end){ while(ds[i]<ds[j] &&i<j) i++; while(ds[j]<ds[i] &&j<=end) j++; swap(ds,i,index,j); } return
0;}int
mySpotMergeSort(int
unSorted[],int
begin,int
end){ if(begin<end){ int
mid=(begin+end)/2; mySpotMergeSort(unSorted,begin,mid); mySpotMergeSort(unSorted,mid+1,end); spotMerge(unSorted,begin,mid,end); } return
0;}int
main(){ int
data[7]={1,2,3,4,5,6,7}; mySpotMergeSort(data,0,6); return
0;} |
原地归并排序（Spot Merge Sort）,布布扣,bubuko.com
原文：http://www.cnblogs.com/seair/p/3630109.html