C语言归并排序算法实现

jack1007

归并排序主要分两步：
一是将序列分成两份子序列，然后每个子序列再分成两份，如此下去，直到每个序列里面只有一个元素，那么可以认为序列有序了。这个由一个递归功能的mergesort函数实现。
二是完成两个有序子序列合并，在merge函数里面实现。
将两个部分组合起来，就实现了归并排序，mergesort函数实现。
代码如下：

1. #include <stdio.h>
   
2. 
   
3. void print_arr(int *arr, int arr_len);
   
4. void merge(int *arr, int left, int midle, int right);
   
5. void mergesort(int *arr, int left, int right);
   
6. 
   
7. int
   
8. main()
   
9. {
   
10.   int arr[] = {78, 56, 13, 67, 35, 87, 92, 48, 52, 18};
    
11.   int arr_len = sizeof(arr) / sizeof(arr[0]);
    
12.   print_arr(arr, arr_len);
    
13.   mergesort(arr, 0, arr_len - 1);
    
14.   print_arr(arr, arr_len);
    
15.   return 0;
    
16. }
    
17. 
    
18. void
    
19. merge(int *arr, int left, int midle, int right)
    
20. {
    
21.   int arr_tmp[right - left + 1];
    
22.   int k = 0;
    
23.   int i = left;
    
24.   int j = midle + 1;
    
25.   while (i <= midle && j <= right) {
    
26.     if (arr[i] <= arr[j]) {
    
27.       arr_tmp[k] = arr[i];
    
28.       i++;
    
29.       k++;
    
30.     } else {
    
31.       arr_tmp[k] = arr[j];
    
32.       j++;
    
33.       k++;
    
34.     }
    
35.   }
    
36.   while (i <= midle) {
    
37.     arr_tmp[k] = arr[i];
    
38.     i++;
    
39.     k++;
    
40.   }
    
41.   while (j <= right) {
    
42.     arr_tmp[k] = arr[j];
    
43.     j++;
    
44.     k++;
    
45.   }
    
46.   
    
47.   int index = 0;
    
48.   while (index < k) {
    
49.     arr[left + index] = arr_tmp[index];
    
50.     index++;
    
51.   }
    
52. }
    
53. 
    
54. void
    
55. mergesort(int *arr, int left, int right)
    
56. {
    
57.   int midle;
    
58.   if (left  < right) {
    
59.     midle = (left + right) / 2;
    
60.     mergesort(arr, left, midle);
    
61.     mergesort(arr, midle + 1, right);
    
62.     merge(arr, left, midle, right);
    
63.   }
    
64. }
    
65. 
    
66. void
    
67. print_arr(int *arr, int arr_len)
    
68. {
    
69.   int i = 0;
    
70.   while (i < arr_len) {
    
71.     printf("%d ", arr[i]);
    
72.     i++;
    
73.   }
    
74.   printf("\n");
    
75. }

复制代码