归并排序求逆序数

栏目: IT技术 · 发布时间: 4年前

内容简介:归并排序是分治法(分而治之)的一种典型应用,应用递归的思想,自顶向下思考:先假定mergesort()可以将一个乱序的数组排好序,因此就可以开始"分"(将一个数组平均分成两部分),再"治"(分别对前后部  分调用mergesort()使它们有序),最后再写一个合并子函数Combine(),它可以将两个有序的数组合并,Combine()实现起来比较容易.只需要管理两个指针,分别指向两个子数组的开头,开辟新内存保存中间结 果,遍历完两个数组就可以完成,时间是Θ(n).假定n个元素的数组调用mergesort()
  • 问题:求逆序数。
  • 算法:归并排序。

归并 排序 是分治法(分而治之)的一种典型应用,应用递归的思想,自顶向下思考:先假定mergesort()可以将一个乱序的数组排好序,因此就可以开始"分"(将一个数组平均分成两部分),再"治"(分别对前后部  分调用mergesort()使它们有序),最后再写一个合并子函数Combine(),它可以将两个有序的数组合并,Combine()实现起来比较容易.只需要管理两个指针,分别指向两个子数组的开头,开辟新内存保存中间结 果,遍历完两个数组就可以完成,时间是Θ(n).

假定n个元素的数组调用mergesort()需要时间T(n).因此,T(n)=2T(n/2)+Θ(n).由主定理可知:T(n)=Θ(nlogn).归并 排序算法 的时间复杂度是Θ(nlogn),空间复杂度是Θ(n).

代码如下:

 1 # include <cstdio>
 2 # include <iostream>
 3 # include <algorithm>
 4 
 5 using namespace std;
 6 
 7 int arr[100];
 8 int temp[100];
 9 int number = 0;
10 //合并函数。
11 void Combine(int left,int middle,int right){
12     int i = left;
13     int j = middle+1;
14     int k = left;
15     while (i <= middle && j <= right){
16         if(arr[i] <= arr[j]){
17             temp[k++] = arr[i++];
18         }else{
19             number+=middle-i+1;//1.归并排序求逆序数核心,记录逆序数对数。
20             temp[k++] = arr[j++];
21         }
22     }
23     while(i <= middle){
24         temp[k++] = arr[i++];
25     }
26     while(j <= right){
27         temp[k++] = arr[j++];
28     }
29     for(int m=left; m<=right; m++){
30         arr[m] = temp[m];
31     }
32     return;
33 }
34 
35 void mergersort(int left,int right){
36     if(left < right){
37         int middle = left + (right-left)/2;
38         mergersort(left,middle);
39         mergersort(middle+1,right);
40         Combine(left,middle,right);
41     }
42     return;
43 } 
44 int main(){
45     int n;
46     while( scanf("%d",&n)!= EOF){
47     for(int i=0; i<n; i++){
48         scanf("%d",&arr[i]);
49     }
50     mergersort(0,n-1);
51     for(int j=0; j<n; j++){
52         printf("%d ",arr[j]); //排序后的数组。
53     }
54     
55     printf("\n");
56     printf("%d\n",number);    
57 }
58 }

当然求逆序数也可以暴力求解,直接双重循环,此时算法复杂度为O(n 2 ),废话不多说代码如下:

 1 # include <cstdio>
 2 # include <iostream>
 3 
 4 using namespace std;
 5 int number;
 6 int arr[100];
 7  int main (){
 8      int n;
 9      while( scanf("%d",&n) != EOF){
10           number=0; 
11          for(int k=0; k<n; k++){
12              scanf("%d",&arr[k]);
13          }
14         for(int i=0; i<n; i++)
15          for(int j=i; j<n; j++){
16              if(arr[i]>arr[j]){
17                  number++;//记录逆序数对数
18              }
19          }
20          printf("%d\n",number);
21         
22      }
23  }

显然暴力求解代码量少,但是归并排序的效率更高。


以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

C语言名题精选百则技巧篇

C语言名题精选百则技巧篇

冼镜光 / 机械工业出版社 / 2005-7 / 44.00元

《C语言名题精选百则》(技巧篇)收集了100则C语言程序设计题,共分9类。第一类比较简单,主要希望读者了解到《C语言名题精选百则》(技巧篇)的题目、解法与其他书籍之间的差异;第二至六类分别是关于数字、组合数学或离散数学、查找、排序、字符串等方面的题目;第七类列出了一些不太容易归类的题目,如Buffon丢针问题、Dijkstra的三色旗问题等;第八类则收录了一些有趣的、娱乐性的题目,如魔方阵等;第九......一起来看看 《C语言名题精选百则技巧篇》 这本书的介绍吧!

HTML 压缩/解压工具
HTML 压缩/解压工具

在线压缩/解压 HTML 代码

JS 压缩/解压工具
JS 压缩/解压工具

在线压缩/解压 JS 代码

XML、JSON 在线转换
XML、JSON 在线转换

在线XML、JSON转换工具