C 归并排序

1#include <stdio.h>
2#include <limits.h>
3#define N 15 //定义要排序的数组个数
4//归并排序控制Demo
5//归并排序函数
6int* Merge_Sort(int n, int nums[])
7{
8    //创建临时存储结果的数组，若不创建在交换部分会复杂许多
9    int nums_temp[N+1];
10    int u, i, m, x, y, j;
11    //外层循环，控制排序的总轮数
12    for(u = 1; u < n; u*=2)
13    {
14        //将临时数组的索引下标归零，即回到第一个元素
15        m=0;
16        //内层循环，控制各组进行比较
17        for(i = 0; i < n; i = i + u*2)
18        {
19            x = 0;
20            y = 0;
21            //两组进行归并，当有一组元素为空时结束归并
22            while(x<u&&y<u&&i+x<n&&i+u+y<n)
23            {
24                //判断元素大小，小的元素排前，同时移动临时数组下标
25                if(nums[i+x] > nums[i+u+y])
26                {
27                    nums_temp[m] = nums[i+u+y];
28                    y++;
29                    m++;
30                }
31                else
32                {
33                    nums_temp[m] = nums[i+x];
34                    x++;
35                    m++;
36                }
37            }
38            //判断最后残留的元素，将残留元素归并（残留元素即两组之中最后一个不需要比较的元素）
39            if(x == u)
40            {
41                for(j=y;j<u;j++)
42                {
43                    nums_temp[m] = nums[i+u+j];
44                    m++;
45                }
46            }
47            else
48            {
49                for(j=x;j<u;j++)
50                {
51                    nums_temp[m] = nums[i+j];
52                    m++;
53                }
54            }
55        }
56        //将临时数组的元素复制回原数组，注意这里不能直接等于
57        for(i = 0; i < n; i++)
58        {
59            nums[i] = nums_temp[i];
60        }
61    }
62    //返回排序好的数组
63    return nums;
64}
65
66int main(int argc, char const *argv[])
67{
68    //要进行排序的数组
69    int nums[N] = {3,4,-9,0,4,5,4,2,9,23,22,20,45,-10};
70    int i;
71    //调用归并排序函数
72    int *p = Merge_Sort(N, nums);
73    //循环输出，输出实际个数，奇数数组添加的元素就被屏蔽了
74    for(i = 0; i < N; i++)
75    {
76        printf("%d ", p[i]);
77    }
78    return 0;
79}