归并排序

  基本思想:归并算法应用到分治策略,简单说就是把一个答问题分解成易于解决的小问题后一个个解决,最后在把小问题 的一步步合并成总问题的解。这里的排序应用递归来把数组分解成一个个小数组,直到小数组的数位有序,在把有序的小数组两两合并 而成有序的大数组。

动图演示

归并排序

C代码

#include <stdio.h>
#include <limits.h>

// 合并两个已排好序的数组
void Merge(int a[], int left, int mid, int right)
{
    int len = right - left + 1;        //    数组的长度
    int *temp = new int[len];       // 分配个临时数组
    int k = 0;
    int i = left;                   // 前一数组的起始元素
    int j = mid + 1;                // 后一数组的起始元素
    while (i <= mid && j <= right)
    {
        //    选择较小的存入临时数组
        temp[k++] = a[i] <= a[j] ? a[i++] : a[j++];  
    }
    while (i <= mid)
    {
        temp[k++] = a[i++];
    }
    while (j <= right)
    {
        temp[k++] = a[j++];
    }
    for (int k = 0; k < len; k++)
    {
        a[left++] = temp[k];
    }
}

// 递归实现的归并排序
void MergeSort(int a[], int left, int right)  
{
    if (left == right)    
        return;
    int mid = (left + right) / 2;
    MergeSort(a, left, mid);
    MergeSort(a, mid + 1, right);
    Merge(a, left, mid, right);
}


int main() {
    int a[] = { 5,1,9,2,8,7,10,3,4,0,6 };
    int n = sizeof(a) / sizeof(int);
    MergeSort(a, 0, n - 1);
    printf("排序好的数组为:");
    for (int k = 0; k < n; ++k)
        printf("%d ", a[k]);
    printf("\n");
    return 0;
}

分析:

  最差、最优、平均时间复杂度都为O(nlogn),其中递归树共有lgn+1层,每层需要花费O(n)。辅助空间O(n)。稳定性:稳 定。

Copyright © liyang.com 2019 all right reserved,powered by Gitbook该文件修订时间: 2019-07-01 15:22:50

results matching ""

    No results matching ""