C++實(shí)現(xiàn)自頂向下的歸并排序算法

　　自頂向下的歸并排序算法是采用分治法進(jìn)行自頂向下的程序設(shè)計方式，下面小編為大家整理了C++實(shí)現(xiàn)自頂向下的歸并排序算法，希望能幫到大家！

　　一. 算法描述

　　自頂向下的歸并排序：采用分治法進(jìn)行自頂向下的程序設(shè)計方式，分治法的核心思想就是分解、求解、合并。

　　1. 先將長度為N的無序序列分割平均分割為兩段

　　2. 然后分別對前半段進(jìn)行歸并排序、后半段進(jìn)行歸并排序

　　3. 最后再將排序好的前半段和后半段歸并

　　過程(2)中進(jìn)行遞歸求解，最終下圖詳細(xì)的分解了自頂向下的合并算法的實(shí)現(xiàn)過程：

　　二. 算法實(shí)現(xiàn)

　　/*=============================================================================## 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>

　　三. 算法分析

　　平均時間復(fù)雜度：O(nlog2n)

　　空間復(fù)雜度：O(n) (用于存儲有序子序列合并后有序序列)

　　穩(wěn)定性：穩(wěn)定

【C++實(shí)現(xiàn)自頂向下的歸并排序算法】相關(guān)文章：

C++實(shí)現(xiàn)自底向上的歸并排序算法03-14

C++歸并排序算法實(shí)例02-09

C語言實(shí)現(xiàn)歸并排序算法02-04

C語言實(shí)現(xiàn)歸并排序算法實(shí)例03-19

C語言實(shí)現(xiàn)歸并排序算法實(shí)例分析01-25

如何實(shí)現(xiàn)歸并排序03-14

堆排序算法及用C++實(shí)現(xiàn)基于最大堆的堆02-12

C++選擇排序算法實(shí)例02-25

C++冒泡排序算法實(shí)例詳解10-13