分治算法-JZTXT

分治算法就是把一个大的问题递归转化为许多原理相同的小问题，通过解决这些小问题，进而以合并以达到解决大问题的目的

问题： 对于任意一个已知数组，如何利用分治的方法把数组从大到小排序？

#include <stdio.h>

int L[100],R[100];
void merge(int numbers[],int left,int mid, int right)
{
    int n1 = mid - left + 1;
    int n2 = right - mid;
    int i,j,k;
    for(i = 1;i<=n1;i++)
        L[i] = numbers[left+i-1]; // 临时数组，用于储存numbers传入数组的值
    for(j = 1;j<=n2;j++)
        R[j] = numbers[mid+j];
    L[n1+1] = 99999;  //确立边界（个人不喜欢这样）便于下一步的大小比较
    R[n2+1] = 99999;

    i = 1;
    j = 1;

    for(k = left;k<=right;k++)
        if(L[i]<=R[j])          //确立大小关系，重构numbers
        {
            numbers[k] = L[i];
            i++;
        }
        else
        {
            numbers[k] = R[j];
            j++;

        }

}

void mergeSort(int numbers[],int left,int right)

{
    if(left < right)
    {
        int mid; //int的智慧
        mid  = (right + left) / 2;
        mergeSort(numbers,left,mid);
        mergeSort(numbers,mid+1,right);
        merge(numbers,left,mid,right);
    }
}


int main()
{
    int numbers[]={5,2,4,6,1,3,2,6}; //此处的numbers可以任意替换
    mergeSort(numbers , 0, 7);
    for(int i = 0;i<8;i++)
    {
        printf("%d",numbers[i]);
    }
}

对于较为简单的排序问题，冒泡就可以很容易的解决，但冒泡的时间复杂度是O（n^2），而分治的时间复杂度是O（n*log n）,虽然编写难度较大，但是计算机运行更加容易