归并排序

 1#include <stdlib.h>
 2
 3//合并过程
 4void merge(int data[],int start,int mid,int end){
 5
 6
 7    int *tmpLeft,*tmpRight;
 8    int leftSize,rightSize;
 9    int l,r,j;
10
11    printArray(data,8);
12    printf("\n");
13    l = 0;
14    r = 0;
15    j = 0;
16    leftSize = mid - start + 1;
17    rightSize = end - mid;
18
19    tmpLeft = (int *)malloc(leftSize * sizeof(int));
20    tmpRight = (int *)malloc(rightSize * sizeof(int));
21
22    while(j < leftSize){
23        tmpLeft[j] = data[start + j];
24        j++;
25    }
26
27    j = 0;
28
29    while(j < rightSize){
30        tmpRight[j] = data[mid + 1 + j];
31        j++;
32    }
33
34    j = 0;
35
36    while(l < leftSize && r < rightSize){
37        if(tmpLeft[l] < tmpRight[r]){
38
39            data[start + j++] = tmpLeft[l++];
40
41        }else{
42        
43            data[start + j++] = tmpRight[r++];
44        }        
45    }
46
47    while(l < leftSize){
48        data[start + j++] = tmpLeft[l++];
49    }
50
51    while(r < rightSize){
52        data[start + j++] = tmpRight[r++];
53    }
54
55    free(tmpLeft);
56    free(tmpRight);
57}
58
59
60void merge_sort(int data[],int start,int end){
61
62    int mid;
63    if(start < end){
64        //将数组划分
65        mid = (start + end) / 2;
66        merge_sort(data,start,mid);
67        merge_sort(data,mid + 1,end);
68        //合并划分后的两个数组
69        merge(data,start,mid,end);
70    }
71
72}