站点图标

C 归并排序

2018-11-20折腾记录算法 / Develop / C
本文最后更新于 607 天前,文中所描述的信息可能已发生改变

懒得写开头,过几天应该会添加( ̄ ▽  ̄)”

终于将排序算法修复完成啦!!!,目前已经不需要判断是否是奇数个了ヾ(≧▽≦*)o


_79
#include <stdio.h>
_79
#include <limits.h>
_79
#define N 15 //定义要排序的数组个数
_79
//归并排序控制Demo
_79
//归并排序函数
_79
int* Merge_Sort(int n, int nums[])
_79
{
_79
//创建临时存储结果的数组,若不创建在交换部分会复杂许多
_79
int nums_temp[N+1];
_79
int u, i, m, x, y, j;
_79
//外层循环,控制排序的总轮数
_79
for(u = 1; u < n; u*=2)
_79
{
_79
//将临时数组的索引下标归零,即回到第一个元素
_79
m=0;
_79
//内层循环,控制各组进行比较
_79
for(i = 0; i < n; i = i + u*2)
_79
{
_79
x = 0;
_79
y = 0;
_79
//两组进行归并,当有一组元素为空时结束归并
_79
while(x<u&&y<u&&i+x<n&&i+u+y<n)
_79
{
_79
//判断元素大小,小的元素排前,同时移动临时数组下标
_79
if(nums[i+x] > nums[i+u+y])
_79
{
_79
nums_temp[m] = nums[i+u+y];
_79
y++;
_79
m++;
_79
}
_79
else
_79
{
_79
nums_temp[m] = nums[i+x];
_79
x++;
_79
m++;
_79
}
_79
}
_79
//判断最后残留的元素,将残留元素归并(残留元素即两组之中最后一个不需要比较的元素)
_79
if(x == u)
_79
{
_79
for(j=y;j<u;j++)
_79
{
_79
nums_temp[m] = nums[i+u+j];
_79
m++;
_79
}
_79
}
_79
else
_79
{
_79
for(j=x;j<u;j++)
_79
{
_79
nums_temp[m] = nums[i+j];
_79
m++;
_79
}
_79
}
_79
}
_79
//将临时数组的元素复制回原数组,注意这里不能直接等于
_79
for(i = 0; i < n; i++)
_79
{
_79
nums[i] = nums_temp[i];
_79
}
_79
}
_79
//返回排序好的数组
_79
return nums;
_79
}
_79
_79
int main(int argc, char const *argv[])
_79
{
_79
//要进行排序的数组
_79
int nums[N] = {3,4,-9,0,4,5,4,2,9,23,22,20,45,-10};
_79
int i;
_79
//调用归并排序函数
_79
int *p = Merge_Sort(N, nums);
_79
//循环输出,输出实际个数,奇数数组添加的元素就被屏蔽了
_79
for(i = 0; i < N; i++)
_79
{
_79
printf("%d ", p[i]);
_79
}
_79
return 0;
_79
}

C 归并排序

https://blog.ixk.me/post/c-merge-sort
  • 许可协议

    BY-NC-SA

  • 发布于

    2018-11-20

  • 本文作者

    Otstar Lin

转载或引用本文时请遵守许可协议,注明出处、不得用于商业用途!

C 插入排序C语言链表实现