歡迎來到Linux教程網
Linux教程網
Linux教程網
Linux教程網
您现在的位置: Linux教程網 >> UnixLinux >  >> Linux編程 >> Linux編程

Linux下歸並排序(Merge Sort)下歸並排序算法的C語言實現

在Linux下實現了一個歸並排序的算法,分成多個文件,這裡記錄三點:歸並排序的算法、makefile的使用、gdb調試心得

一、歸並排序算法

算法的遞推關系:一個大的數列需要排序,把它從中間分成兩部分,每一部分歸並排序,然後把排好序的這兩個部分再合並起來(合並的時候要按順序合並)。

算法的Base Case:如果分成的這部分只有一個數,那麼這個部分就不用再排序(看做已經排好序的)。

實現這個算法用了三個函數,每個函數在一個文件中,分別為:merge.c  sort.c 和 main.c,其中merge.c實現的是合並的方法,sort.c實現的是排序的方法,main.c是一個測試實例。還有三個頭文件,分別指出了函數原型。

merge.c:

/*This is a merge program.
*  Given an integer ARRAY and three numbers which indicate the begain
*and the end of two subarrays, merge the two subarrays to a bigger
*one. The two subarrays are alrealy sorted from small to big.
* For example, given an array a[10] and three numbers 0, 3 and 5. The
*first array is from a[0] to a[2], the seconde array is from a[3] to
*a[4]. The number 3 and 5 are the upper side. This program merge the
*two arrays together.
*
*/
#include <stdio.h>
#include <stdlib.h>

#include "main.h"

void merge(int *a, int idxa, int idxb, int idxc)
{
    int i = idxa, j = idxb, k = 0;
    int total = idxc-idxa;
    //int temp[total] = {0};
    int *temp = (int *)malloc(sizeof(int) * total);
    if(temp == NULL)
    {
        fprintf(stderr, "malloc error in merge function\n");
        return;
    }
    while(i < idxb && j < idxc)
    {
        if(a[i] < a[j])
            temp[k++] = a[i++];
        else
            temp[k++] = a[j++];
    }

    if(i == idxb)
    {
        while(j < idxc)
            temp[k++] = a[j++];
    }
    else if(j == idxc)
    {
        while(i < idxb)
            temp[k++] = a[i++];
    }

    /*Copy the temp to the sorce array*/
    for(i = 0, k = idxa; i < total; k++, i++)
        a[k] = temp[i];

    free(temp);
}

#ifndef MAIN
/*For test*/
int main()
{
    int a[10];
    int i = 0;
    int idxa=1, idxb=5, idxc=8;

    printf("Please input 10 numbers to the array:");
    for(i = 0; i < 10; i++)
        scanf("%d", &a[i]);
    printf("Three indexes are %d, %d and %d.\nThe first subarray is:", idxa, idxb, idxc);
    for(i = idxa; i < idxb; i++)
        printf(" %d", a[i]);
    printf("\nThe second subarray is:");
    for(i = idxb; i < idxc; i++)
        printf(" %d", a[i]);
    printf("\n");

    merge(a, idxa, idxb, idxc);
    printf("The merged array is:");
    for(i = idxa; i < idxc; i++)
        printf(" %d", a[i]);
    printf("\n");

    return 0;
}
#endif

Copyright © Linux教程網 All Rights Reserved