归并排序采用递归和分治的思想。分治主要是将两个无序数组合并成一个有序数组。
# include <iostream> using namespace std; void MergeTwo(int sourceArr[],int tempArr[],int startIndex,int midIndex,int endIndex){//0,4,9 int i = startIndex; int j = midIndex+1; int k = startIndex; while(i <= midIndex && j <= endIndex){ if(sourceArr[i] > sourceArr[j]) tempArr[k++] = sourceArr[j++]; else tempArr[k++] = sourceArr[i++]; } while(i <= midIndex) tempArr[k++] = sourceArr[i++]; while(j <= endIndex + 1) tempArr[k++] = sourceArr[j++]; for(i = startIndex ; i <= endIndex ; i++) sourceArr[i] = tempArr[i]; } //内部使用递归 void MergeSort(int sourceArr[],int tempArr[],int startIndex,int endIndex){ int midIndex; if(startIndex < endIndex){ midIndex = (startIndex + endIndex)/2; MergeSort(sourceArr,tempArr,startIndex,midIndex); MergeSort(sourceArr,tempArr,midIndex+1,endIndex); MergeTwo(sourceArr,tempArr,startIndex,midIndex,endIndex); } } void Print(int arr[],int n){ for(int i = 0 ; i < n ; i++) cout << arr[i] << endl; } int main(){ int arr[10] = {123,4,23,3,4,67,78,4543,234,9768}; int b[10]; MergeSort(arr,b,0,9); Print(arr,10); return 0; }