Merge Sort 归并排序C语言实现

#Merge Sort-归并排序

此贴由戴维营教育学员翻译,鄙人整理,特意为戴维营教育零基础学员课外学习之用.

归并排序是基于分而治之的方法,它把这个要进行排序的列表,平分成两半,变成两个未排序的列表。再对这两个无序列表进行同样的排序,合并,最终得到一个排好序的列表。这两个无序列表是通过不断地调用归并排序算法进行排序;我们最终得到一个大小为1的已经排好序的列表。这两个大小为1的列表,然后又合并。

##算法:

这是一种分而治之的算法。工作原理如下 -

  • 1,把我们输入的需要排序的列表从中间分成两半,称为左半部分和右半部分。
    例如:假设输入是-10 32 45 -78 91 1 0 -16,则左部分是-10 32 45 -78,右部分将是91 1 0 6。
  • 2,把这左右两部分分别单独排序。需要注意的是,这里的排序并不意味着使用其他一些方法来排序。而是我们递归地使用一样的函数。
  • 3,然后合并这两个排好序的列表。

输入元素的总个数:number_of_elements, 然后输入这么多个元素保存到数组array[number_of_elements]里面。接下来调用函数 MergeSort() 对这个数组进行排序。
MergeSort()函数对数组[left,right]范围内的元素排序,即从索引left到索引right之的所有元素。
Merge() 函数的作用是合并两个已排好序的部分。排好序的部分是从[left,mid][mid+1,right]。合并后输出这个排好序的数组。

MergeSort() 函数:

它把数组,以及该数组的最左边和最右边的索引作为它的参数。数组的中间元素通过公式(left + right)/2计算得出。检查是否(left<right)因为只有(left<right)时我们才需要排序,而当left=right时表示它已经排好序了。排序左半部分通过调用MergeSort(array,left,mid),排序右半部分通过调用MergeSort(array,mid + 1, right),最后调用Merge() 函数把这两个数组合并到一起。

最后复制回已排序的数组到原数组。

##特性:

  • 最好的情况 - 当数组已经排序时, 时间复杂度为O(nlogn)
  • 最坏的情况 - 当数组是按相反的顺序时, 时间复杂度为O(nlogn)
  • 一般情况下 - 时间复杂度为O(nlogn)
  • 额外的空间是必需的,所以数组归并排序空间复杂度是O(n) ,链表归并排序的空间复杂度是O(logn).

##归并排序C语言实现


#include <stdio.h>
/*This is called Forward declaration of function */
void Merge(int * , int , int , int );
/* Logic: This is divide and conquer algorithm. This works as follows.
         (1) Divide the input which we have to sort into two parts in the middle. Call it the left part and right part.
             Example: Say the input is  -10 32 45 -78 91 1 0 -16 then the left part will be -10 32 45 -78 and the right part will be  91 1 0 6.
         (2) Sort Each of them seperately. Note that here sort does not mean to sort it using some other method. We already wrote fucntion to sort it. Use the same.
         (3) Then merge the two sorted parts.
*/

/*This function Sorts the array in the range [left,right].That is from index left to index right inclusive
 */
 
void MergeSort(int *array, int left, int right)
{
        int mid = (left+right)/2;
        /* We have to sort only when left<right because when left=right it is anyhow sorted*/
        if(left<right)
        {
                /* Sort the left part */
                MergeSort(array,left,mid);
                /* Sort the right part */
                MergeSort(array,mid+1,right);
                /* Merge the two sorted parts */
                Merge(array,left,mid,right);
        }
}


/* Merge functions merges the two sorted parts. Sorted parts will be from [left, mid] and [mid+1, right].
 */
void Merge(int *array, int left, int mid, int right)
{
        /*We need a Temporary array to store the new sorted part*/
        int tempArray[right-left+1];
        int pos=0,lpos = left,rpos = mid + 1;
        while(lpos <= mid && rpos <= right)
        {
                if(array[lpos] < array[rpos])
                {
                        tempArray[pos++] = array[lpos++];
                }
                else
                {
                        tempArray[pos++] = array[rpos++];
                }
        }
        while(lpos <= mid)  tempArray[pos++] = array[lpos++];
        while(rpos <= right)tempArray[pos++] = array[rpos++];
        int iter;
        /* Copy back the sorted array to the original array */
        for(iter = 0;iter < pos; iter++)
        {
                array[iter+left] = tempArray[iter];
        }
        return;
}


int main(void)
{
        int number_of_elements;
        scanf("%d",&number_of_elements);
        int array[number_of_elements]; 
        int iter;
        for(iter = 0;iter < number_of_elements;iter++)
        {
                scanf("%d",&array[iter]);
        }
        /* Calling this functions sorts the array */
        MergeSort(array,0,number_of_elements-1); 
        for(iter = 0;iter < number_of_elements;iter++)
        {
                printf("%d ",array[iter]);
        }
        printf("\n");
        return 0;
}

标签:none

添加新评论