内容简介:归并排序是分治法(分而治之)的一种典型应用,应用递归的思想,自顶向下思考:先假定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 }
显然暴力求解代码量少,但是归并排序的效率更高。
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网
猜你喜欢:本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。