归并排序算法（合并排序）代码,C代码库,德仔网

代码语言

代码分类

【C】归并排序算法（合并排序）

作者:寂寞的煙客 / 发布于2014/11/7/ 599


	#include <stdio.h>
	#include <stdlib.h>
	
	#define N 7
	
	void merge(int arr[], int low, int mid, int high);
	void merge_sort(int arr[], unsigned int first, unsigned int last);
	
	int main()
	{
	 int i;
	 int a[N] = {32, 12, 56, 78, 76, 45, 36};
	
	 printf("排序前 \n");
	 for (i=0; i<N; i++)
	 {
	 printf("%d\t", a[i]);
	 }
	
	 merge_sort(a, 0, N-1);
	
	 printf("\n排序后 \n");
	 for (i=0; i<N; i++)
	 {
	 printf("%d\t", a[i]);
	 }
	 printf("\n");
	
	 return 0;
	}
	
	void merge_sort(int arr[], unsigned int first, unsigned int last)
	{
	 int mid = 0;
	 if (first < last)
	 {
	 mid = (first+last)/2; //注意防止溢出
	 // mid = (first & last)+( (first ^ last) >>1 );
	 merge_sort(arr, first, mid);
	 merge_sort(arr, mid+1, last);
	 merge(arr, first, mid, last);
	 }
	 return;
	}
	
	void merge(int arr[], int low, int mid, int high)
	{
	 int i, k;
	 int *tmp = (int *)malloc( (high-low+1)*sizeof(int) ); //申请空间，使其大小成为两个
	
	 int left_low = low;
	 int left_high = mid;
	 int right_low = mid+1;
	 int right_high = high;
	
	 for (k=0; left_low<=left_high && right_low<=right_high; k++)
	 {
	 //比较两个指针指向的元素
	 if (arr[left_low] <= arr[right_low])
	 {
	 tmp[k] = arr[left_low++];
	 }
	 else
	 {
	 tmp[k] = arr[right_low++];
	 }
	 }
	
	 if (left_low <= left_high)
	 {
	 //若第一个序列有剩余，直接复制出来，粘贴到合并序列尾
	 // memcpy(tmp+k, arr+left_low, (left_high-left_low+1)*sizeof(int) );
	 for (i=left_low; i<=left_high; i++)
	 {
	 tmp[k++] = arr[i];
	 }
	 }
	
	 if (right_low <= right_high)
	 {
	 //若第二个序列有剩余，直接复制出来粘到合并序列尾
	 // memcpy( tmp+k, arr+right_low, (right_high-right_low+1)*sizeof(int) );
	 for (i=right_low; i<=right_high; i++)
	 {
	 tmp[k++] = arr[i];
	 }
	 }
	
	 for (i=0; i<high-low+1; i++)
	 {
	 arr[low+i] = tmp[i];
	 }
	
	 free(tmp);
	
	 return;
	}

试试其它关键字

　归并排序　　合并排序　

同语言下

可能有用的

寂寞的煙客贡献的其它代码(2)