C语言归并排序代码

时间:2014-12-05 17:57    点击:


    #include <stdio.h>
    #include <stdlib.h>
    #define N 7
    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+l)*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;
    }
    void merge_sort(int arr[], unsigned int first, unsigned int last){
    int mid = 0;
    if(first<last){
    mid = (first+last)/2; /* 注意防止溢出 */
    /*mid = first/2 + 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;
    }
    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");
    system("pause");
    return 0;
    }

来源:未知//所属分类:C语言/更新时间:2014-12-05 17:57
顶一下
(1)
100%
踩一下
(0)
0%
上一篇:C语言快速排序代码
下一篇:C语言顺序查找算法代码
相关内容