归并排序求逆序数

栏目: 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  }

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


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

查看所有标签

猜你喜欢:

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

数据科学入门

数据科学入门

[美] Joel Grus / 高蓉、韩波 / 人民邮电出版社 / 2016-3 / 69.00元

数据科学是一个蓬勃发展、前途无限的行业,有人将数据科学家称为“21世纪头号性感职业”。本书从零开始讲解数据科学工作,教授数据科学工作所必需的黑客技能,并带领读者熟悉数据科学的核心知识——数学和统计学。 作者选择了功能强大、简单易学的Python语言环境,亲手搭建工具和实现算法,并精心挑选了注释良好、简洁易读的实现范例。书中涵盖的所有代码和数据都可以在GitHub上下载。 通过阅读本书,......一起来看看 《数据科学入门》 这本书的介绍吧!

随机密码生成器
随机密码生成器

多种字符组合密码

HTML 编码/解码
HTML 编码/解码

HTML 编码/解码

HSV CMYK 转换工具
HSV CMYK 转换工具

HSV CMYK互换工具