- #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;
- }
- //该片段来自于http://www.codesnippet.cn/detail/0203201511826.html
来源: http://www.codesnippet.cn/detail/0203201511826.html