文档章节

归并排序-非递归应用

一叶舟troy
 一叶舟troy
发布于 2015/08/15 15:54
字数 884
阅读 104
收藏 6
/** function:
    合并2个有序数组,有效到大
    input:
    数组first pData[begin..mid]
    数组second pData[mid+1..end]
    output:pData[begin...end]
    
    需要空间:o(n)
**/
void merge(int *pData,int begin,int mid,int end)
{
    int pTemp[8]={0};
    int first =begin;
    int second =mid+1;
    int iTemp=begin;//iTemp开始位置不能每次都零开始,begin
    
    while(first<=mid && second<=end)
    {
        if(pData[first]<=pData[second])
        {
            pTemp[iTemp++]=pData[first++];
        }else
        {
              pTemp[iTemp++]=pData[second++];
        }
    }
    
    //待排序数组 还没有剩余
    while(first<=mid && second>end)
    {
          pTemp[iTemp++]=pData[first++];
    }
    
    while(second<=end && first>mid)
    {
       pTemp[iTemp++]=pData[second++]; 
    }
    
    for(int i=begin;i<=end;i++)
    {
        pData[i]=pTemp[i];
    }
   // delete []pTemp; 
    
}
/***
   function:非递归形式  
   统计i后门位置,比i小的个数,加入[0--i] 统计完毕之后,我是不计较后门是有些无需的
   前提:自己没有统计完毕千万不打乱
   1 
    如何做到间隔step访问 观察规律 
    根据step查分成n组 
    step=1
    [0,1], [2,3] ,[4,5][6,7] begin 
    
    step=2;
    [40,80] [20,60]                       begin 0 mid=1 end  3 
    
     [40,80] [20,60] ,[41,81] [21,61]    begin 4 mid=5  end 7
     step=4;
     
     组后一组 可能少于一个step的数据
    2  如何将一个step 数据排序完毕
    
    
    
**/
void merge_sort(int * pData,int length)
{
    int step=0;//step 避免全部排序,为了判断是否第一我不要和每一个人打一架
    int begin=0;//下一个拆分合并数组的开始位置 
    int mid=0;//begin-mid,mid-end 拆分需要合并的2个数组
    int end =0;//待排序结束位置
    //int temp[length]={0};//无法为temp申请空间 因为length不知道
   
    //控制归并排序次数
   for(step =1;step<length;step*=2)
   {   
       cout<<"step=="<<step<<":"<<endl;
       
      //控制一次归并排序,有多少对数字需要合并
      //<=length必须等于 不如少计算一个数组
      for(begin=0;(begin+2*step)<=length;begin=end+1)
      {   
          mid=begin+step-1;
          end=mid+step;
          if(end>length-1)//第二个序列个数不足
          {
              end=length-1;
          }
           //cout<<"begin_mid__end:"<<begin<<"__"<<mid<<"__"<<end<<endl;
           merge(pData,begin,mid,end); 
          //showData(pData,length);
      }
      showData(pData,length);
      
   }
 
}
void testgetMaxSum()
{
  
   int array[8]={0,5,-2,1,-8,7,6,-3};   
   showData(array,8);
   merge_sort(array,8);
   
   //showData(array,12);
   
}
////递归方式
void merge_sort(int * pData,int begin ,int end)
{
    if(begin >end)
    {
        retunr ;//quit
    }
    
    int mid=(begin+end)/2;
    merge_sort(pData,begin,mid);
    merge_sort(pData,mid+1,end);
    merge(pData,begin,mid,end);
}

输出结果:

  • 题目描述:

  • 在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数。

  • 输入:

  • 每个测试案例包括两行:

    第一行包含一个整数n,表示数组中的元素个数。其中1 <= n <= 10^5。

    第二行包含n个整数,每个数组均为int类型。

  • 输出:

  • 对应每个测试案例,输出一个整数,表示数组中的逆序对的总数。

    样例输入:

    4
    7 5 6 4

  • 样例输出:

  • 5

【解题思路】

1  模拟人工计算方式 ,缺点 顺序执行

7  3

5 1

6 1

sum=3+1+1=5

缺点:N*N

2 如何上面联系起来。例如学生成绩比较 班级A和班级B,如果班级A 第一名(i) 大约班级B(i) 第一名

比较 ,就不需要和B中其他值比较了


参考:

http://www.cnblogs.com/xing901022/p/3671771.html

© 著作权归作者所有

一叶舟troy
粉丝 10
博文 27
码字总数 24336
作品 0
程序员
私信 提问
加载中

评论(3)

一叶舟troy
一叶舟troy 博主
特殊测试:剩余最后一个数据该怎么办
一叶舟troy
一叶舟troy 博主
;(begin+2*step)<=length 应该是 最后一个step数据
一叶舟troy
一叶舟troy 博主
step==8:
-8 -3 -2 0 1 5 6 7 -90 测试结果有问题 这个是为啥呀
数据结构-二路归并及归并排序

一、介绍: 归并排序(Merge sort)是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;...

sssssuuuuu666
2017/12/08
0
0
Leetcode:148_Sort List | O(nlogn)链表排序 | Medium

题目:Sort List Sort a linked list in O(n log n) time using constant space complexity 看题目有两个要求:1)时间复杂度为O(nlogn);2)空间复杂度为常数,即不能增设额外的空间。 满足...

chambai
2014/10/07
0
0
JavaScript算法 ,Python算法,Go算法,java算法,系列之【归并排序】篇

常见的内部排序算法有:插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括: 归并排序(英语:Merge sort,或mergesort),是创建在归并操作上...

湖南小影
2017/05/12
0
0
JavaScript算法 ,Python算法,Go算法,java算法,系列之【归并排序】篇

常见的内部排序算法有:插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括: 归并排序(英语:Merge sort,或mergesort),是创建在归并操作上...

湖南小影
2017/05/12
0
0
面试 11:玩转 Java 归并排序

面试 11:Java 玩转归并排序 前面讲了冒泡、选择、插入三种简单排序,时间复杂度都是 O(n²),今天,我们终于迎来了更高级的排序:归并排序。 虽然在这之前还有希尔排序和堆排序,但由于时间...

nanchen2251
2018/07/18
0
0

没有更多内容

加载失败,请刷新页面

加载更多

OSChina 周六乱弹 —— 早上儿子问我他是怎么来的

Osc乱弹歌单(2019)请戳(这里) 【今日歌曲】 @凉小生 :#今日歌曲推荐# 少点戾气,愿你和这个世界温柔以待。中岛美嘉的单曲《僕が死のうと思ったのは (曾经我也想过一了百了)》 《僕が死の...

小小编辑
今天
779
11
Excption与Error包结构,OOM 你遇到过哪些情况,SOF 你遇到过哪些情况

Throwable 是 Java 中所有错误与异常的超类,Throwable 包含两个子类,Error 与 Exception 。用于指示发生了异常情况。 Java 抛出的 Throwable 可以分成三种类型。 被检查异常(checked Exc...

Garphy
今天
15
0
计算机实现原理专题--二进制减法器(二)

在计算机实现原理专题--二进制减法器(一)中说明了基本原理,现准备说明如何来实现。 首先第一步255-b运算相当于对b进行按位取反,因此可将8个非门组成如下图的形式: 由于每次做减法时,我...

FAT_mt
昨天
6
0
好程序员大数据学习路线分享函数+map映射+元祖

好程序员大数据学习路线分享函数+map映射+元祖,大数据各个平台上的语言实现 hadoop 由java实现,2003年至今,三大块:数据处理,数据存储,数据计算 存储: hbase --> 数据成表 处理: hive --> 数...

好程序员官方
昨天
7
0
tabel 中含有复选框的列 数据理解

1、el-ui中实现某一列为复选框 实现多选非常简单: 手动添加一个el-table-column,设type属性为selction即可; 2、@selection-change事件:选项发生勾选状态变化时触发该事件 <el-table @sel...

everthing
昨天
6
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部