合并排序（语言C） [英] Merge sort (Language C)

问题描述

在合并排序的情况下，函数如何工作？

我无法理解下一步的条件是什么。

How does function work in case of merge sort?
I can''t understand on what condition it moves to next step.

partition(arr,low,mid);
partition(arr,mid+1,high);
mergeSort(arr,low,mid,high);


#include <stdio.h>
#define MAX 50

void mergeSort(int arr[],int low,int mid,int high);
void partition(int arr[],int low,int high);

int main(){

    int merge[MAX],i,n;

    printf("Enter the total number of elements: ");
    scanf("%d",&n);

    printf("Enter the elements which to be sort: ");
    for(i=0;i<n;i++){
         scanf("%d",&merge[i]);
    }

    partition(merge,0,n-1);

    printf("After merge sorting elements are: ");
    for(i=0;i<n;i++){
         printf("%d ",merge[i]);
    }

   return 0;
}

void partition(int arr[],int low,int high){

    int mid;

    if(low<high){
         mid=(low+high)/2;
         partition(arr,low,mid);
         partition(arr,mid+1,high);
         mergeSort(arr,low,mid,high);
    }
}

void mergeSort(int arr[],int low,int mid,int high){

    int i,m,k,l,temp[MAX];

    l=low;
    i=low;
    m=mid+1;

    while((l<=mid)&&(m<=high)){

         if(arr[l]<=arr[m]){
             temp[i]=arr[l];
             l++;
         }
         else{
             temp[i]=arr[m];
             m++;
         }
         i++;
    }

    if(l>mid){
         for(k=m;k<=high;k++){
             temp[i]=arr[k];
             i++;
         }
    }
    else{
         for(k=l;k<=mid;k++){
             temp[i]=arr[k];
             i++;
         }
    }

    for(k=low;k<=high;k++){
         arr[k]=temp[k];
    }
}

推荐答案

合并排序或合并排序是一种简单但有效的排序算法，可将列表拆分为两个子列表，对每个子列表进行排序，然后将它们组合成一个排序列表。它具有良好的最坏情况性能，只需要顺序访问，使其成为链接列表等顺序数据结构的理想选择。



请注意函数partition是< b> reqursive 的;这意味着，它调用自身并将未排序的整数数组分开，直到数组的各个部分被排序。

函数mergeSort只是将已排序的部分组合（或合并）在一起。

Merge sort or mergesort is a simple but efficient sort algorithm that splits the list into two sublists, sorts each one, then combines them into a single sorted list. It has good worst-case performance and requires only sequential access, making it ideal for sequential data structures like linked lists.

Please note that the function "partition" is reqursive; that means, it calls itself and divide the array of unsorted integers as long till parts of array are sorted.
The function mergeSort just assemble (or merge) the sorted parts together.

这篇关于合并排序（语言C）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！