合并排序的原理就是使用分治法策略，将一个规模为N的问题，划分为n个规模为m（mvoid MergerSort(int* _array,int left,int right)
{
if(left
{
int middle=(left+right)/2;
MergerSort(_array,left,middle);
MergerSort(_array,middle+1,right);
MergerArray(_array,left,right);
}
}
C语言代码如下：
- #include <stdio.h>
- //数组合并
- void MergeArray(int* sorce , int left ,int right)
- {
- int k = 0 ;
- int i = left ;
- int middle = (left+right)/2;
- int j = middle+1;
- int* dest = new int[right-left+1];
- while(i<=middle&& j<=right)
- {
- if(sorce[i]<sorce[j])
- {
- dest[k++] = sorce[j++];
-
- }else
- {
- dest[k++] = sorce[i++];
-
- }
- }
- while(i<=middle)
- {
- dest[k++] = sorce[i++];
- }
- while(j<=right)
- {
- dest[k++] = sorce[j++];
- }
- //将合并好的结果和源数组进行交换，相当于拷贝
- int q = left ;
- int m = 0 ;
- while( q<=right)
- {
- sorce[q++] = dest[m++];
- }
- delete[] dest;
- }
- //合并排序
- void MergeSort(int* _array,int left,int right)
- {
- if(left<right)
- {
- int middle = (left+right)/2;
- MergeSort(_array,left,middle); //对左边排序
- MergeSort(_array,middle+1,right);//对右边排序
- //对排序结果进行合并
- MergeArray(_array,left,right);
- }
-
- }
- int main(int argc, char** argv)
- {
-
- int _wait_array[7] ={24,-2,11,9,31,0,21};
- MergeSort(_wait_array,0,6);
- return 0 ;
- }
阅读(1637) | 评论(0) | 转发(0) |
