C++实现自顶向下的归并排序算法

C++实现自顶向下的归并排序算法

　　自顶向下的归并排序算法是采用分治法进行自顶向下的程序设计方式，下面小编为大家整理了C++实现自顶向下的归并排序算法，希望能帮到大家！

　　一. 算法描述

　　自顶向下的归并排序：采用分治法进行自顶向下的程序设计方式，分治法的核心思想就是分解、求解、合并。

　　1. 先将长度为N的无序序列分割平均分割为两段

　　2. 然后分别对前半段进行归并排序、后半段进行归并排序

　　3. 最后再将排序好的前半段和后半段归并

　　过程(2)中进行递归求解，最终下图详细的分解了自顶向下的合并算法的实现过程：

　　二. 算法实现

　　/*=============================================================================## FileName: mergeSort.c# Algorithm: 归并排序(自顶向下)# Author: Knife# Created: 2014-06-14 16:40:02#=============================================================================*/#include#includevoid merge_sort(int* intArr, int intArr_len);void merge_array(int* intArr1, int len1, int* intArr2, int len2);void main(){ int intArr[] = {8,3,6,4,2,9,5,4,1,7}; int n = sizeof (intArr) / sizeof (intArr[0]); int i = 0; merge_sort(intArr, n); for(;i1){ int* intArr1 = intArr; int intArr1_len = intArr_len/2; int* intArr2 = intArr + intArr_len/2; int intArr2_len = intArr_len - intArr1_len; /pic/pic/pic/pic/pic/pic/pic/pic/pic/p>

　　三. 算法分析

　　平均时间复杂度：O(nlog2n)

　　空间复杂度：O(n) (用于存储有序子序列合并后有序序列)

　　稳定性：稳定

【C++实现自顶向下的归并排序算法】相关文章：

C++实现自底向上的归并排序算法03-14

C++归并排序算法实例02-09

C语言实现归并排序算法02-04

C语言实现归并排序算法实例03-19

C语言实现归并排序算法实例分析01-25

如何实现归并排序03-14

堆排序算法及用C++实现基于最大堆的堆02-12

C++选择排序算法实例02-25

C++冒泡排序算法实例详解10-13