学步园

#include "stdafx.h"<br /> #include <iostream><br /> #include <algorithm><br /> #include <iterator><br /> using namespace std;<br /> void MergeSort(int arr[], int low, int high);<br /> void Merge(int arr[], int low, int midle, int high);<br /> int main()<br /> {<br /> const int N = 10;<br /> int arr[N];<br /> for(int i=0; i<N; i++)<br /> arr[i] = rand()%30;<br /> cout<<"原数组:"<<endl;<br /> copy(arr, arr+N, ostream_iterator<int>(cout, " "));<br /> cout<<endl;<br /> MergeSort(arr, 0, N);<br /> cout<<"排序后:"<<endl;<br /> copy(arr, arr+N, ostream_iterator<int>(cout, " "));<br /> cout<<endl;<br /> }<br /> void MergeSort(int arr[], int low, int high)<br /> {<br /> int mid = 0;<br /> if(low < high)//不是while是if，为这个错误找了好几天<br /> {<br /> mid = (low + high) / 2;<br /> MergeSort(arr, low, mid);<br /> MergeSort(arr, mid+1, high);<br /> Merge(arr, low, mid, high);<br /> }<br /> }<br /> void Merge(int arr[], int low, int mid, int high)<br /> {<br /> int n = high - low;<br /> int *temp = new int[n];//存放合并元素的临时数组<br /> int i = low;<br /> int j = mid;<br /> int k = 0;<br /> while((i<mid) && (j<high))<br /> {<br /> if( arr[i] < arr[j])<br /> {<br /> temp[k] = arr[i];<br /> ++i;<br /> }<br /> else<br /> {<br /> temp[k] = arr[j];<br /> ++j;<br /> }<br /> ++k;<br /> }<br /> while(i < mid)<br /> temp[k++] = arr[i++];<br /> while(j < high)<br /> temp[k++] = arr[j++];<br /> for(k=low; k<high; k++) //重新拷贝回去<br /> {<br /> arr[k] = temp[k - low];<br /> }<br /> delete []temp;<br /> }<br />