1 /**************** 2 思路：假设待排序有n个记录，将这n个记录看成n个有序的子序列，每个子序列长度为1， 3 然后两两归并。 4 如何将将二个有序数列合并：这个非常简单，只要从比较二个数列的第一个数， 5 谁小就先取谁，取了后就在对应数列中删除这个数。然后再进行比较，如果有数列为空， 6 那直接将另一个数列的数据依次取出即可。 7 ****************/ 8 #include <iostream> 9 10 using namespace std; 11 12 //将有二个有序数列arr[first...mid]和arr[mid...last]合并。主要是merge这个函数 13 void Merge(int* arr, int first, int mid, int last, int* temp) 14 { 15 int f1 = first; 16 int m = mid; 17 int f2 = mid+1; 18 int l = last; 19 int i = 0; 20 while((f1 <= m)&&(f2 <= l)) 21 { 22 if(arr[f1] < arr[f2]) 23 temp[i++] = arr[f1++]; 24 else 25 temp[i++] = arr[f2++]; 26 } 27 while(f1 <= m) 28 temp[i++] = arr[f1++]; 29 while(f2 <= l) 30 temp[i++] = arr[f2++]; 31 for(int j=0; j<i; j++) 32 arr[first + j] = temp[j]; 33 } 34 35 36 void MergeSort(int* arr, int first, int last, int* temp) 37 { 38 int mid; 39 if(first < last) //if first >= last, return 40 { 41 mid = (first + last) /2; 42 MergeSort(arr, first, mid, temp); 43 MergeSort(arr, mid+1, last, temp); 44 Merge(arr,first, mid, last, temp); 45 } 46 } 47 48 49 int main() 50 { 51 int * arr; 52 int * temp; 53 int n; 54 cout<<"Input the arr length:"<<endl; 55 cin>>n; 56 arr = new int[n]; 57 temp = new int[n]; 58 cout<<"Input the arr elements:"<<endl; 59 for(int i=0;i<n;i++) 60 { 61 cin>>arr[i]; 62 } 63 MergeSort(arr,0,n-1,temp); 64 cout<<"The outcome:"<<endl; 65 for(int i=0;i<n;i++) 66 cout<<arr[i]<<endl; 67 return 0; 68 } 69 /************************ 70 稳定的。 71 时间复杂度：归并排序不依赖与原始数组的输入情况，每次划分时两个子序列长度都是基本一样的， 72 因此最大、最小和平均时间均为O(nlogn)。 73 空间复杂度：用到一个临时数组，因此空间代价为O(n)。 74 总结： 75 1.排序时间不依赖于原始数组； 76 2.时间为O(nlogn)，因此适用于数组n较大的情况； 77 3.空间代价为O(n)。 78 *************************/