首页 > 代码库 > 归并排序

归并排序

参考:白话经典算法系列之五 归并排序的实现

 

 1 #include "stdafx.h" 2  3 //t[]在外部申请,以此避免在函数体内部反复申请数组的开销。 4 void merge_array(int a[], int left, int middle, int right, int t[])  5 { 6     int l = left, r = middle + 1, k = 0; 7     while(l <= middle && r <= right) 8     { 9         if(a[l] < a[r])10              t[k++] = a[l++];11         else12             t[k++] = a[r++];13     }14 15     while(l <= middle)16         t[k++] = a[l++];17 18     while(r <= right)19         t[k++] = a[r++];20 21     for(int i = 0; i < k; ++i)22         a[left + i] = t[i];       //mark!第一次忘记写left了。23 }24 25 void merge_sort(int a[], int left, int right, int t[])26 {27     if(left >= right) return;28     int middle = (left + right)/2;29     merge_sort(a, left, middle, t);30     merge_sort(a, middle + 1, right, t);31     merge_array(a, left, middle, right, t);    32 }33 34 int _tmain(int argc, _TCHAR* argv[])35 {36     int array[] = {7,10,19,25,12,17,21,30,48};37     38     int * t = new int[sizeof(array)/sizeof(int)];    39     merge_sort(array, 0, sizeof(array)/sizeof(int) - 1, t);40     delete []t;41 42     getchar();43     return 0;44 }

 

归并排序