Tag Archive: Divide and Conquer

分治算法简介——归并排序

  归并排序应用分治算法,具有O(nlogn)的时间复杂度,其工作流程可以概述为: 将长度为n的无序序列分割成n个子序列,每个序列包含1个元素; 重复将子序列相互合并称为有序序列,直到只剩下1个序列,即为排序后的序列。   一个例程如下所示: void merge(int array[], int tmpArray[], int lPos, int rPos, int rEnd) { int i,…
Read more