成全高清视频免费观看动漫版-成全视频动漫免费高清-午夜不卡久久精品无码免费

你好，欢迎来到电脑编程技巧与维护杂志社！

杂志社简介│广告服务│读者反馈│编程社区

您的位置：技术专栏 / C专栏

归并排序

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

1. 首先考虑将两个有序数列合并的过程：

只要从比较二个数列的第一个数，谁小就先取谁，取了后就在对应数列中删除这个数。然后再进行比较，如果有数列为空，那直接将另一个数列的数据依次取出即可。

void MergeArray(int a[], int n, int b[], int m, int c[])     
{   
    int i=j=k=0;    
    
    if(NULL == a&&NULL ==b)   
        return;   
    else if(NULL == a&&NULL != b){   
        while(j <m)   
            c[k++] = b[j++];   
    }   
    else if(NULL != a&&NULL == b){   
        while(i < n)   
            c[k++] = a[i++];   
    }   
    else{   
        while (i < n && j < m)  {     
            if (a[i] < b[j])     
                c[k++] = a[i++];     
            else    
                c[k++] = b[j++];      
        }     
        while (i < n)     
            c[k++] = a[i++];     
        while (j < m)     
            c[k++] = b[j++];     
    }   
}<span style="font-family:Arial;color:#333333;"><span style="font-size: 15px; line-height: 26px;">   
</span></span>

2. 再来看归并排序

其的基本思路就是将数组分成二组A，B，如果这二组组内的数据都是有序的，那么就可以很方便的将这二组数据进行排序。如何让这二组组内数据有序了？

可以将A，B组各自再分成二组。依次类推，当分出来的小组只有一个数据时，可以认为这个小组组内已经达到了有序，然后再合并相邻的二个小组就可以了。

//将有二个有序数列a[first...mid]和a[mid...last]合并。   
void MergeaArray(int a[], int first, int mid, int last, int temp[])   
{   
    int i = first, j = mid + 1;   
    int m = mid,   n = last;   
    int k = 0;   
        
    while (i <= m && j <= n)   
    {   
        if (a[i] <= a[j])   
            temp[k++] = a[i++];   
        else  
            temp[k++] = a[j++];   
    }   
        
    while (i <= m)   
        temp[k++] = a[i++];   
        
    while (j <= n)   
        temp[k++] = a[j++];   
        
    for (i = 0; i < k; i++)   
        a[first + i] = temp[i];   
}   
void mergesort(int a[], int first, int last, int temp[])   
{   
    if (first < last)   
    {   
        int mid = (first + last) / 2;   
        mergesort(a, first, mid, temp);    //左边有序   
        mergesort(a, mid + 1, last, temp); //右边有序   
        MergeArray(a, first, mid, last, temp); //再将二个有序数列合并   
    }   
}   
    
bool MergeSort(int a[], int n)   
{   
    int *p = new int[n];   
    if (p == NULL)   
        return false;   
    mergesort(a, 0, n - 1, p);   
    delete[] p;   
    return true;   
}

如果数列长为N，将数列分开成小数列一共要logN步，每步都是一个合并有序数列的过程，时间复杂度可以记为O(N)，故一共为O(N*logN)，归并排序的效率是比较高的。

推荐精品文章


·2024年9月目录 ·2024年8月目录 ·2024年7月目录 ·2024年6月目录 ·2024年5月目录 ·2024年4月目录 ·2024年3月目录 ·2024年2月目录 ·2024年1月目录 ·2023年12月目录 ·2023年11月目录 ·2023年10月目录 ·2023年9月目录 ·2023年8月目录

联系方式

TEL：010-82561037
Fax: 010-82561614
QQ: 100164630
Mail：gaojian@comprg.com.cn

友情链接

中国软件网│软件开发网│