【数据结构】：排序--归并排序

归并排序

1、思想： 归并排序是类似于快排的一种排序，采用分治的思想，将原来的序列进行划分，划分到各自的区间大小为1（注意：如果是一个奇数大小的序列，那么要将其中一个多划分一次），然后将划分的子区间进行有序合并，最终达到完全有序的序列。2、具体如何实现： 3、代码实现： #include<iostream> #include<assert.h> using namespace std; void _MergeSort(int* a,int* temp,int left,int right) { if(left >= right) return; int mid = left+((right-left)>>1); int begin1 = left; int end1 = mid; int begin2 = mid+1; int end2 = right; _MergeSort(a,temp,left,mid); _MergeSort(a,temp,mid+1,right); int index = left; while(begin1 <= end1 && begin2<=end2) { if(a[begin1] < a[begin2]) { temp[index++] = a[begin1++]; } else { temp[index++] = a[begin2++]; } } while(begin1 <= end1) { temp[index++] = a[begin1++]; } while(begin2 <= end2) { temp[index++] = a[begin2++]; } //最后将临时数组中的数拷到原数组中 for(int i = 0; i<=right; i++) //注意等号 { a[i] = temp[i]; } } void MergeSort(int* a,size_t n) { assert(a); int* temp = new int[n]; for(int i = 0; i<n; i++) { temp[i] = a[i]; } _MergeSort(a,temp,0,n-1); } void TestMergeSort() { int i = 0; int a[10] = {2,0,4,9,3,6,8,7,1,5}; int sz = sizeof(a)/sizeof(a[0]); MergeSort(a,sz); for(int i = 0; i<10; i++) { cout<<a[i]<<" "; } cout<<endl; } 4、时间复杂度和空间复杂度： 时间复杂度：O(NlgN) 空间复杂度：O(N)5、作用： 它是不考虑原序列的顺序性的，一般应用于外部排序