归并排序

浏览数：21 / 时间：2015年06月08日

归并排序的数组实现

 1 //折半插入排序
 2 void insertSort_Binary(int *arr, int len)
 3 {
 4     int i, j;//工作指针
 5     int low, mid, high;//折半查找指针
 6     int current;//暂存待插入的元素
 7 
 8     //将各个元素插入到前面的有序序列
 9     for(i = 0; i< len; i++)
10     {
11         current = arr[i];
12         low = 0;
13         high = i - 1;
14         while(low <= high)
15         {
16             mid = low + (high-low)/2;
17             if(arr[mid] > current)
18                 high = mid - 1;
19             else
20                 low = mid + 1;
21         }
22         //后移元素
23         for(j = i - 1; j >= high+1; j--)
24             arr[j+1] = arr[j];
25         //插入目标元素
26         arr[high+1] = current;
27     }
28 }
29 
30 //归并排序
31 void mergeSort(int *arr, int len1, int *arr2, int len2, int *arr3)
32 {
33     int i = 0;//遍历数组1的指针
34     int j = 0;//遍历数组2的指针
35     int k = 0;//存储归并后的元素的指针
36 
37     //对数组1、2进行排序，使之成为有序数组
38     insertSort_Binary(arr1,len1);
39     insertSort_Binary(arr2,len2);
40 
41     while(i < len1 && i < len2)
42     {
43         if(arr1[i] < arr2[j])
44             arr3[k++] = arr1[i++]；
45         else
46             arr3[k++] = arr2[j++];
47     }
48     while(i < len1)
49         arr3[k++] = arr1[i++];
50     while(j < len2)
51         arr3[k++] = arr2[j++];
52 }