首页 > 代码库 > 归并排序
归并排序
分治法的思想:将原问题分解为几个规模较小但类似于原问题的子问题,递归求解这些子问题,然后再合并这些子问题的解来建立原问题的解。主要包括三个主要步骤:1、分解原问题 ;2、解决子问题;3、合并子问题的解
归并排序遵循分治模式,算法的时间复杂度是O(NlogN),属于稳定排序。直观操作为:
分解:分解待排序的n个元素的序列成各具有n/2个元素的两个子序列。
解决:使用归并排序递归地排序两个子序列。
合并:合并两个已排序的子序列以产生已排序的答案。
具体算法由一个辅助函数和一个递归函数组成:
函数代码:
#include<iostream> using namespace std; #define INF 65535 template<class T> void Merge(T *A, int p, int q, int r) { int n1 = q - p + 1; int n2 = r - q; T *L = new T[n1 + 1]; T *R = new T[n2 + 1]; for (int i = 0; i<n1; i++){ L[i] = A[p + i]; } for (int j = 0; j<n2; j++){ R[j] = A[q + j + 1]; } L[n1] = INF; R[n2] = INF; int i = 0,j = 0; for (int k = p; k <= r; k++) { if (L[i] <= R[j]) { A[k] = L[i]; i++; } else{ A[k] = R[j]; j++; } } delete[]L; delete[]R; } //二分归并排序 template<class T> void MergeSort1(T *A, int p, int r) // p r 均是元素下标 { if (p<r) { int q = (p + r) / 2; MergeSort1(A, p, q); MergeSort1(A, q + 1, r); Merge(A, p, q, r); } }
测试代码:
int main() { int arry[] = { 210, 12, 9, 1, 5, 8, 19, 4, 7, 10,15,17,21,41,51,61,81,71,91,100 }; MergeSort1<int>(arry, 0, 19); //调用时,是数组首元素和末尾元素下标 for (int i = 0; i < 20; i++) cout << arry[i] << " "; cout << endl; cout << "BigThink" << endl; system("pause"); return 0; }
归并排序
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。