排序算法:归并排序

归并排序的思路是 采用分治法,将一个大的问题拆分成若干个小问题,将一个大数组 拆为多个小数组进行排序 后再进去重组。 入下图锁示

拼合2个数组的思路:因为2个数组其实都是排过序的,只要给2个数组都设置个游标可以跟简单的进行组合。如下图所示



 

实现代码:

void _real_merge(int arr[], int start, int mid, int end)
{
    int* temp = malloc(sizeof(int) * (end - start));
    int start1 = start;
    int start2 = mid;
    int length = 0;
    
    while(1)
    {
        //两侧都用完
        if(start1>=mid && start2 >= end)
        {
            break;
        }
        
        //有一侧的元素已经用完
        else if(start1>=mid)
        {
            temp[length++] = arr[start2];
            start2++;
        }
        else if(start2 >= end)
        {
            temp[length++] = arr[start1];
            start1++;
        }
        
        //后大
        else if(arr[start1] <= arr[start2])
        {
            temp[length++] = arr[start1];
            start1++;
        }
        
        //前大
        else if(arr[start1] > arr[start2])
        {
            temp[length++] = arr[start2];
            start2++;
        }
    }
    
    //赋值回原来数组
    for (int j = start; j<end; j++)
    {
        arr[j] = temp[j-start];
    }
    
    free(temp);
}



void sort_merge(int arr[],int start, int end)
{
    if(start == end - 1 )
    {
        return;
    }
    
    int partCount  = (end - start)/2;

    sort_merge(arr, start, start + partCount);
    sort_merge(arr, start + partCount, end);
    _real_merge(arr, start, start + partCount, end);
}

int arr[] = {8,4,5,7,1,3,6,2};        
int len= (sizeof(arr) / sizeof(int));
sort_merge(arr, 0, len);

 

 

参考文章和图片引用链接:
http://www.cnblogs.com/chengxiao/p/6194356.html

发表评论?

1 条评论。

  1. 没事就来转一转,每天多吃两碗饭!

发表评论


注意 - 你可以用以下 HTML tags and attributes:
<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>