算法导论三剑客之 分治算法 合并排序

 1 #include "iostream"
 2 #include "windows.h"
 3 #define MAX 0x7fffffff
 4 using namespace std;
 5
 6 void merge(int s,int q,int e,int A[]){
 7     int i,j,k;
 8     int B[100],C[100];
 9     for(i=s;i<=q;i++)
10         B[i-s+1]=A[i];
11     for(j=q+1;j<=e;j++)
12         C[j-q]=A[j];
13     B[q-s+2]=C[e-q+1]=MAX;
14
15     i=j=1;
16     k=s;
17     while(k<=e){
18         if(B[i]>=C[j]){
19             A[k]=C[j];
20             j++;
21         }
22         else{
23             A[k]=B[i];
24             i++;
25         }
26         k++;
27     }
28
29 }
30
31
32 void merge_sort(int s,int e,int A[]){
33     if(e>s){
34         int q=(s+e)/2;
35         merge_sort(s,q,A);
36         merge_sort(q+1,e,A);
37         merge(s,q,e,A);
38     }
39 }
40 void main(){
41     int A[]={0,1,12,3,4,3,7,1,122};
42     merge_sort(1,8,A);
43     int i;
44     for(i=1;i<=8;i++){
45         cout<<A[i]<<" ";
46     }
47     cout<<endl;
48     getchar();
49 }

算法导论三剑客之 分治算法 合并排序,布布扣,bubuko.com

时间: 06-15

算法导论三剑客之 分治算法 合并排序的相关文章

算法导论三剑客之 动态规划 0-1背包问题

1 #include "iostream" 2 using namespace std; 3 4 float MAX(float m1,float m2){ 5 if(m1>=m2) 6 return m1; 7 else 8 return m2; 9 } 10 11 float bag_Zero_One(int n,float v,float p[],float w[]){ 12 if(n==0||v==0) 13 return 0; 14 else{ 15 float m2;

算法导论——lec 13 贪心算法与图上算法

之前我们介绍了用动态规划的方法来解决一些最优化的问题.但对于有些最优化问题来说,用动态规划就是"高射炮打蚊子",采用一些更加简单有效的方法就可以解决.贪心算法就是其中之一.贪心算法是使所做的选择看起来是当前最佳的,期望通过所做的局部最优选择来产生一个全局最优解. 一. 活动选择问题 [问题]对几个互相竞争的活动进行调度:活动集合S = {a1, a2, ..., an},它们都要求以独占的方式使用某一公共资源(如教室),每个活动ai有一个开始时间si和结束时间fi ,且0 ≤ si &

算法导论学习之快排+各种排序算法时间复杂度总结

快排是一种最常用的排序算法,因为其平均的时间复杂度是nlgn,并且其中的常数因子比较小. 一.快速排序 快排和合并排序一样都是基于分治的排序算法;快排的分治如下: 分解:对区间A[p,r]进行分解,返回q,使得A[p–q-1]都不大于A[q] A[q+1,r]都大于A[q]; 求解:对上面得到的区间继续递归进行快排 合并:因为快排是原地排序,所以不需要特别的合并 从上可以看出最重要的就是分解函数,其按关键值将数组划分成3部分,其具体实现的过程见代码注释. 我们一般取数组的最后一个元素作为划分比较

算法导论第八章__实现计数排序

计数排序:不须要比較就能得出排序的顺序__比如.本章的计数排序.基数排序.桶排序 比較排序:须要进行比較才干得出排序的顺序__比如,本章的堆排序.高速排序(本质是插入排序).插入排序 代码清单:计数排序__完美演绎下标的作用 public class Count_Sort { //接收须要排序的数组 private int[] A; //排序后的数组 private int[] B; //用于计数的数组 private int[] C; // 初始化 public Count_Sort(int[

《算法导论》习题2.2-2 选择排序

伪代码: SELECTION-SORT1 for i=2 to A.length-1 2  max = A[i] 3  mark = i 4 for j=i+1 to A.length 5 if A[j]>max 6  max=A[j] 7 mark = j 8 A[mark]=A[i] 9 A[i] = max Java 实现: public class SelectionSort { public static double [] sort(double [] A) { for(int i

算法导论——最小生成树:Kruskal算法(利用了并查集)

package org.loda.graph; import org.loda.structure.MinQ; import org.loda.structure.Queue; import org.loda.util.In; /** * * @ClassName: KruskalMST * @Description:Kruskal最小生成树算法 * @author minjun * @date 2015年5月25日 下午10:50:01 * */ public class KruskalMST

算法导论——最短路径:BellmanFord算法

package org.loda.graph; import org.loda.structure.Stack; import org.loda.util.In; /** * * @ClassName: BellmanFord * @Description: 最短路径问题 * * 通用最短路径算法,能解决除了含负权重环以外的所有情况的最短路径,包括了含有负权重边的有向加权图 * * @author minjun * @date 2015年5月28日 下午11:04:45 * */ public

算法导论学习笔记(2)-归并排序

今天学习了算法导论上的归并排序算法,并且完成了在纸上写出伪代码,以前就学过归并但是理解的不够透彻,以 前还一直困惑:为什么明明归并排序比快排的时间复杂度更稳定,为什么库函数不用归并而用快排,现在知道原因了,因为归并排序必须开额外的空间,而且空间开销还比较大,下面介绍算法: 首先,归并排序用到了分治的思想,把大数据分成若干个小数据,然后再分别对小数据进行处理,最后把小数据 合并成大数据. 其次,归并排序用到了一个最重要的特点,就是把两组已经排序的数据合并成一组有序数据,并且该过程的时间复 杂度为O

算法系列之常用算法之一----分治算法

一.基本概念 在计算机科学中,分治法是一种很重要的算法.分治算法,字面上的解释是"分而治之",分治算法主要是三点: 1.将一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题----"分" 2.将最后子问题可以简单的直接求解----"治" 3.将所有子问题的解合并起来就是原问题打得解----"合" 这三点是分治算法的主要特点,只要是符合这三个特点的问题都可以使用分治算法进行解决(注意用词,是"