文档章节

归并排序

汪纬
 汪纬
发布于 2015/12/15 16:57
字数 336
阅读 0
收藏 0

采用分治的思想  以O(NlogN)最坏的情形运行时间运行

 

如果对merge的每个递归调用都采用局部声明一个临时数组,那么在任一时刻就可能有logN个临时数组处在活动期

代码如下:

 1 #include <iostream>
 2 #include <vector>
 3 using namespace std;
 4 template <typename Comparable>
 5 void mergeSort(vector<Comparable> & a)
 6 {
 7     vector<Comparable> tmpArray(a.size());
 8     mergeSort(a,tmpArray,0,a.size()-1);
 9 }
10 template <typename Comparable>
11 void mergeSort(vector<Comparable> & a,vector<Comparable> & tmpArray,int left,int right)
12 {
13     if(left<right)
14     {
15         int center = (left+right)/2;
16         mergeSort(a,tmpArray,left,center);
17         mergeSort(a,tmpArray,center+1,right);
18         merge(a,tmpArray,left,center+1,right);
19     }
20 }
21 template <typename Comparable>
22 void merge(vector<Comparable> & a,vector<Comparable> & tmpArray,int leftPos,int rightPos,int rightEnd)
23 {
24     int leftEnd = rightPos-1;
25     int tmpPos = leftPos;
26     int numElements = rightEnd - leftPos + 1;
27 
28     while(leftPos <= leftEnd && rightPos <= rightEnd)
29         if(a[leftPos] <= a[rightPos])
30             tmpArray[tmpPos++] = a[leftPos++];
31         else
32             tmpArray[tmpPos++] = a[rightPos++];
33 
34     while(leftPos <= leftEnd)
35         tmpArray[tmpPos++] = a[leftPos++];
36     while(rightPos <= rightEnd)
37         tmpArray[tmpPos++] = a[rightPos++];
38 
39     for(int i=0;i<numElements;i++,rightEnd--)
40         a[rightEnd] = tmpArray[rightEnd];
41 }
42 int main()
43 {
44     vector<int> ivec;
45     ivec.push_back(1);
46     ivec.push_back(9);
47     ivec.push_back(2);
48     ivec.push_back(10);
49     ivec.push_back(3);
50     ivec.push_back(11);
51     ivec.push_back(4);
52     ivec.push_back(12);
53     ivec.push_back(5);
54     ivec.push_back(13);
55     ivec.push_back(6);
56     ivec.push_back(14);
57     ivec.push_back(7);
58     ivec.push_back(15);
59     ivec.push_back(8);
60     ivec.push_back(16);
61     mergeSort(ivec);
62     for(int j = 0;j<ivec.size();j++)
63         cout<<ivec[j]<<endl;
64     return 0;
65 }

运行结果:

本文转载自:http://www.cnblogs.com/xing901022/archive/2012/09/27/2706196.html

汪纬

汪纬

粉丝 11
博文 649
码字总数 39577
作品 0
崇明
后端工程师
私信 提问

暂无文章

Spring使用ThreadPoolTaskExecutor自定义线程池及实现异步调用

多线程一直是工作或面试过程中的高频知识点,今天给大家分享一下使用 ThreadPoolTaskExecutor 来自定义线程池和实现异步调用多线程。 一、ThreadPoolTaskExecutor 本文采用 Executors 的工厂...

CREATE_17
今天
5
0
CSS盒子模型

CSS盒子模型 组成: content --> padding --> border --> margin 像现实生活中的快递: 物品 --> 填充物 --> 包装盒 --> 盒子与盒子之间的间距 content :width、height组成的 内容区域 padd......

studywin
今天
7
0
修复Win10下开始菜单、设置等系统软件无法打开的问题

因为各种各样的原因导致系统文件丢失、损坏、被修改,而造成win10的开始菜单、设置等系统软件无法打开的情况,可以尝试如下方法解决 此方法只在部分情况下有效,但值得一试 用Windows键+R打开...

locbytes
昨天
8
0
jquery 添加和删除节点

本文转载于:专业的前端网站➺jquery 添加和删除节点 // 增加一个三和一节点function addPanel() { // var newPanel = $('.my-panel').clone(true) var newPanel = $(".triple-panel-con......

前端老手
昨天
8
0
一、Django基础

一、web框架分类和wsgiref模块使用介绍 web框架的本质 socket服务端 与 浏览器的通信 socket服务端功能划分: 负责与浏览器收发消息(socket通信) --> wsgiref/uWsgi/gunicorn... 根据用户访问...

ZeroBit
昨天
10
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部