归并排序，快速排序木

归并排序：归并排序是每次都把有序的区间合并起来构成一个新的有序序列。初始时区间长度是1；模拟求解时：区间段数是n。每次最后那段都合并到前一段上。递归求解：只要注意边界就好了，left>=right就递归结束返回程序上一层。总的时间复杂度为0（nlogn）,空间复杂度为0（n）;

代码一：模拟合并区间

View Code

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 using namespace std;
 6 
 7 #define maxSize 200008
 8 int Temp[maxSize];
 9 
10 // 输入要排序的数据
11 void inPutData(int myArray[], int n){
12     for ( int i=1; i<=n; ++i )
13        scanf ("%d", myArray+i);
14 }
15 // 输出排序后结果
16 void outPutData(int myArray[], int n) {
17      for ( int i=1; i<=n; ++i ) {
18           if(i-1) printf(" ");
19           printf("%d", myArray[i]);
20      }
21      puts("");
22 }
23 
24 // 合并区间[l,mid]和[mid+1,r];
25 
26 void merge( int a[], int l, int mid, int r){
27     int startA = l, endA = mid-1, i=l;
28     int startB = mid, endB = r;
29     while(startA<=endA && startB<=endB){
30          if(a[startA]<=a[startB]) Temp[i++] =  a[startA++];
31          else Temp[i++] = a[startB++];
32     }
33     while(startA<=endA) Temp[i++] = a[startA++];
34     while(startB<=endB) Temp[i++] = a[startB++];
35     for(i=l; i<=r; ++i ) a[i] = Temp[i];
36 };
37 
38 // 模拟合并的
39 void mergeSort( int myArray[], int n ) {
40     /**
41     segNum 区间段数
42     segLength 区间平均长度
43     lastSegLength 最后一段的长度
44     */
45     int segNum = n, segLength = 1, lastSegLength = 1;
46     int tmp_segNum, tmp_segLength, i, j;
47     while(segNum > 1) {
48          tmp_segNum = segNum; // 保存原来的段数用于判断区间
49          segNum >>= 1; // 合并后段数减半
50          tmp_segLength = segLength<<1; // 合并后区间长度加倍
51          if( tmp_segNum&1 ) // 如果段数是奇数
52          {
53              for( i=1, j=1; i<=segNum; j+=tmp_segLength, ++i )
54                merge(myArray, j, j+segLength, j+tmp_segLength-1);
55              //最后一段和前一段已合并的区间合并
56              j = n-lastSegLength-tmp_segLength+1;
57              merge(myArray, j, j+tmp_segLength, n);
58              // 注意每次合并后要更新最后一段长度和平均长度
59              lastSegLength += tmp_segLength;
60              segLength = tmp_segLength;
61          }else
62          {
63              for(i=1, j=1; i<=segNum; ++i, j+=tmp_segLength)
64              {
65                  if(i<segNum)
66                     merge(myArray, j, j+segLength, j+tmp_segLength-1);
67                  else // 特别注意这段的范围
68                     merge(myArray, j, j+segLength, n);
69              }
70 
71              lastSegLength += segLength;
72              segLength = tmp_segLength;
73          }
74     }
75 }
76 
77 int main(){
78     int n;
79     int myArray[maxSize];
80     while( ~scanf("%d", &n) ) {
81          inPutData(myArray, n);
82          mergeSort(myArray, n);
83          outPutData(myArray, n);
84     }
85 };

代码二：递归合并区间，代码简单。

View Code

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 using namespace std;
 6 
 7 #define maxSize 200008
 8 
 9 template <typename T>
10 void Swap( T& a, T& b){
11    T tmp = a; a = b; b  = tmp;
12 }
13 
14 // 输入要排序的数据
15 void inPutData(int myArray[], int n){
16     for ( int i=1; i<=n; ++i )
17        scanf ("%d", myArray+i);
18 }
19 // 输出排序后结果
20 void outPutData(int myArray[], int n) {
21      for ( int i=1; i<=n; ++i ) {
22           if(i-1) printf(" ");
23           printf("%d", myArray[i]);
24      }
25      puts("");
26 }
27 
28 int b[maxSize];
29 void merge( int a[], int l, int mid, int r){
30      int startA = l, endA= mid, i = l;
31      int startB = mid+1, endB = r;
32      while(startA<=endA && startB<=endB) {
33           if(a[startA] <= a[startB] ) b[i++]= a[startA++];
34           else b[i++] = a[startB++];
35      }
36      while(startA<=endA) b[i++] = a[startA++];
37      while(startB<=endB) b[i++] = a[startB++];
38      for(i=l; i<=r; ++i )  a[i] = b[i];
39 }
40 
41 void mergeSort(int a[], int l, int r){
42      if(l>=r) return ;
43      int mid = (l+r)>>1;
44      mergeSort(a, l, mid);
45      mergeSort(a, mid+1, r);
46      merge(a, l, mid, r);
47 }
48 
49 int main(){
50     int n;
51     int myArray[maxSize];
52     while( ~scanf("%d", &n) ) {
53          inPutData(myArray, n);
54          mergeSort(myArray, 1, n);
55          outPutData(myArray, n);
56     }
57 };

快速排序：从数组中选一个关键字，按关键字把数组分为两部分，之后这两部分序列在关键字的两边。接着细分，分治思想。比如a[left]为关键字划分，找左边大于a[left]的和右边小于a[left]的元素进行交换。得到序列a[1].... a[left] ....a[n], 接着划分[1，left这个位置-1]和[left这个位置+1, right]。平均时间复杂度为o(nlogn),最差情况下会达到0(n*n), 空间复杂度为0(n)的堆栈。代码如下：

View Code

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 using namespace std;
 6 
 7 #define maxSize 200008
 8 
 9 template <typename T>
10 void Swap( T& a, T& b){
11    T tmp = a; a = b; b  = tmp;
12 }
13 
14 // 输入要排序的数据
15 void inPutData(int myArray[], int n){
16     for ( int i=1; i<=n; ++i )
17        scanf ("%d", myArray+i);
18 }
19 // 输出排序后结果
20 void outPutData(int myArray[], int n) {
21      for ( int i=1; i<=n; ++i ) {
22           if(i-1) printf(" ");
23           printf("%d", myArray[i]);
24      }
25      puts("");
26 }
27 
28 // 以a[left]作为关键字；
29 
30 void quickSort(int a[], int left, int right)
31 {
32     if(left >=  right) return ;
33     int tmp = a[left], i = left, j = right+1;///
34     while(i <= j) {/// j最后是小于i的，j所在的位置是最后一个小于tmp的。
35         do ++i; while(a[i] < tmp);
36         do --j; while(a[j] > tmp);
37         if(i < j) Swap(a[i], a[j]);
38     }
39     Swap(a[left], a[j]);
40     quickSort(a, left, j-1);
41     quickSort(a, j+1, right);
42 }
43 
44 int main(){
45     int n;
46     int myArray[maxSize];
47     while( ~scanf("%d", &n) ) {
48          inPutData(myArray, n);
49          quickSort(myArray, 1, n);
50          outPutData(myArray, n);
51     }
52 };

归并排序，快速排序 木

归并排序，快速排序木