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
- 相關推薦