首页 > 其他 > 详细

归并排序

时间:2014-03-14 18:38:46      阅读:411      评论:0      收藏:0      [点我收藏+]
bubuko.com,布布扣
 1 #include<stdio.h>
 2 #include<stdlib.h>
 3 #include<limits.h>
 4 void merge(int a[], int p, int q, int r);
 5 void merge_sort(int a[], int p, int r);
 6 int main() {
 7     int a[10] = { 6,5, 4, 3, 1, 2, 0, 7,8,9};
 8     int i = 0;
 9     /*用来测试merge函数的一个实例*
10 
11     int idxa = 0, idxb = 4, idxc = 9;
12 
13     printf("Please input 10 numbers to the array:");
14 
15     printf("Three indexes are %d, %d and %d.\nThe first subarray is:", idxa, idxb, idxc);
16     for (i = idxa; i <= idxb; i++)
17         printf(" %d", a[i]);
18     printf("\nThe second subarray is:");
19     for (i = idxb + 1; i <= idxc; i++)
20         printf(" %d", a[i]);
21     printf("\n");
22 
23     merge(a, idxa, idxb, idxc);
24     printf("The merged array is:");
25     for (i = idxa; i <= idxc; i++)
26         printf(" %d", a[i]);
27     printf("\n");
28     getchar();
29     *测试用例到此处结束*/
30 
31     merge_sort(a, 0, 9);
32     printf("The sorted array is:");
33     for (i = 0; i < 10; i++)
34         printf(" %d", a[i]);
35     printf("\n");
36     getchar();
37     return 0;
38 }
39 void merge_sort(int a[], int p, int r){
40     int q = 0;
41     if (p < r) {
42         q = (p + r) / 2;    //由于整数精度限制,自动对q进行了下取整
43         merge_sort(a, p, q);
44         merge_sort(a, q + 1, r);
45         merge(a, p, q, r);
46     }
47 }
48 void merge(int a[], int p, int q, int r) {
49     /*无聊的声明,用于循环等操作*/
50     int i = 0, j = 0, k = 0;
51     /*声明需要的存储空间来存放数据*/
52     int n1 = q - p + 1;               //设置子数组A[p...q],    此时需要q-p+1的大小的数组
53     int n2 = r - q;                   //设置子数组A[q+1...r],    此时需要r - (q+1) + 1的大小的数组
54     /*令L[n1 + 1]和R[n2 + 1]成为新的数组,其中 +1 是为了放置哨兵牌(一个代表极值的数)*/
55     int *left  = (int *)malloc(sizeof(int) * (n1 + 1));    //申请一段存放左侧数组数据的空间
56     int *right = (int *)malloc(sizeof(int) * (n2 + 1));    //申请一段存放左侧数组数据的空间
57     /*初始化Left 和 Right*/
58     for (i = 0; i < n1; i++) {
59         *(left + i) = a[p + i];
60     }
61     for (j = 0; j < n2; j++) {
62         *(right + j) = a[q + j + 1];
63     }
64     *(left    + n1) = INT_MAX;        //将最后一个设置为哨兵牌,因为是从小到大排序,所以将哨兵牌设为整数最大值
65     *(right + n2) = INT_MAX;
66 
67     i = 0;            //无聊的初始化无聊变量,用于循环
68     j = 0;
69     /*从Left和Right中选小的一个合并到一起*/
70     for (k = p; k <= r; k++) {
71         if (*(left + i) <= *(right + j)) {
72             a[k] = *(left + i);
73             i++;
74         }
75         else {
76             a[k] = *(right + j);
77             j++;
78         }
79     }
80     free(left);
81     free(right);
82 }
bubuko.com,布布扣

归并排序,布布扣,bubuko.com

归并排序

原文:http://www.cnblogs.com/RainFool/p/3599051.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!