C语言归并排序

2020年01月13日 317点热度 4人点赞 1条评论

在阅读本文章之前请确保你已经掌握了递归思想。

归并排序采用了一种分治的思想。时间复杂度为O(n log n)空间复杂度为O(n),是一种稳定的排序算法,它的速度仅次于快速排序。整个过程分为划分和合并两个部分

归并排序的步骤:

1.检查数组的元素数,如果元素数大于等于2就可以视为两个数组。(划分)

2.将数组划分为两部分,分别对两部分分别进行归并排序。(划分并排序,递归)

3.对排序好的两部分进行合并得到最终的有序数组。(合并)

还是举个栗子,我有一组数8 7 6 5 4 3 2 1:

这个过程也是一个自顶向下逐步划分的过程,在步骤中的第二步中其实就进行了一次递归,我们不关心这个过程具体怎么实现,我们只需要知道这里划分出来的两个新数组可以采用归并排序,将它们排序成两个有序的数组,具体过程交给另一个函数,只不过这个函数比较特别,这个函数就是归并排序本身而已.

以上就可以写出一个归并排序的框架的代码,代码中我们忽略了如何把两部分进行合并的算法
int mergeSort(int a[],int start,int end)//需要排序的“两个相邻子数组”为a,它的起点为start,终点为end
{
    if(start>=end)return;//元素小于2个,显然,两个子数组至少元素数为2,小于2一定不能分为两个数组了,直接排除.
    int mid=(start+end)/2;//两个数组间的间隔
    mergeSort(a,start,mid);//对左边的新数组进行排序
    mergeSort(a,mid+1,end);//对右边的新数组进行排序
    //----某种算法----将两个数组合并。
}

归并

下面就是某种算法的描述了.

算法需要两个指针i和j分别只向需要归并的“两个”数组的头部,还需要一个tmp数组用来临时储存归并后的结果

算法步骤(从小到大)

1.循环选取i和j指向的较小的元素放在临时数组中,直至i或j中的一个到达数组的终点。

2.将未选取完的数组剩余元素按顺序赋值给临时数组

3.因为我们所谓的两个数组并非真正的数组,只是人为看做两个数组,并且用mid做分界线,所以需要将临时数组的元素赋值给两个连续的数组.

写出代码如下:

int tmp[MAX_LENTH];
 void _mergeSort(int *array, int start, int middle, int end)  //其中middle是两个数组的分界线,数组1从start到middle 数组2从middle+1到end
 {  
    int i = start;  
    int j = middle + 1;  
    int index = start;  //临时数组写入指针
    while ((i <= middle) && (j <= end))
    {  
        if (array[i] >= array[j])  
            tmp[index++] = array[j++];  
        else  
            tmp[index++] = array[i++];  
    }     
    while(i <= middle) tmp[index++] = array[i++];  //数组1没有写入完的情况
    while(j <= end) tmp[index++] = array[j++];  //数组2没有写入完的情况,该处两个循环不可能都执行。
   
    for (i = start; i <= end; i++)  //临时数组赋值给原数组
        array[i] = tmp[i];  
 }

再合并原来的框架得到如下代码

int tmp[MAX_LENTH]; 
void merge(int *array, int start, int middle, int end) //其中middle是两个数组的分界线,数组1从start到middle 数组2从middle+1到end
{ 
    register int i = start;
    register int j = middle + 1; 
    register int index = start; //临时数组写入指针 
    while ((i <= middle) && (j <= end))
    {    
        if (array[i] >= array[j])
        tmp[index++] = array[j++]; 
        else tmp[index++] = array[i++];
    }
    while(i <= middle) tmp[index++] = array[i++]; //数组1没有写入完的情况 
    while(j <= end) tmp[index++] = array[j++]; //数组2没有写入完的情况,该处两个循环不可能都执行。 
    for (i = start; i <= end; i++) //临时数组赋值给原数组 
        array[i] = tmp[i];
}
int mergeSort(int a[],int start,int end)//需要排序的“两个相邻子数组”为a,它的起点为start,终点为end
{
    if(start>=end)return;//元素小于2个,显然,两个子数组至少元素数为2,小于2一定不能分为两个数组了,直接排除.
    int mid=(start+end)/2;//两个数组间的间隔
    mergeSort(a,start,mid);//对左边的新数组进行排序
    mergeSort(a,mid+1,end);//对右边的新数组进行排序
    merge(a,start,mid,end);//对两个数组进行合并.
}

 

Danny

我就如一粒石子,在随波逐流中,逐渐冲蚀了自己的棱角,变光滑,也变丑陋。

文章评论

  • woc

    <sakka>nen</49649>

    2020年03月14日