【python2C】排序算法

题：逆序对（NXD）

对于给定的一段正整数序列a，逆序对就是序列中 a[i]​>a[j]​ 且 i<j 的有序对。

输入格式

第一行，一个正整数 n，表示序列中有 n个数，n<=5e5

第二行， n 个正整数以空格间隔，表示给定的序列。序列中每个数字不超过 1e9。

输出格式

输出序列中逆序对的数目。

样例输入
6
5 6 2 6 2 1

样例输出
10

解题思路

直娃统计版

从左到右逐个遍历a[i]，计算 a[i+1:]的部分大于a[i]的NXD数，累加。

排序计算版

先降序排序a得到b，并记录排序前的原始序号ind

依次遍历b，b[j]对应的原始序号可计算其后的数，累加。
pop b[j] 然后再次sort，或 遍历比较剩余的数修改较前数的序号

冒泡排序版

最接近的排序算法。依次比较相邻数对，每遇到一对NXD就交换，总交换次数=NXD总数

归并排序版

 参考常用十大排序算法，可以看到
1. 冒泡排序最坏情况太慢了。
2. 计数排序可能最快，奈何不存在交换NXD。
3. 退而求其次，使用时间复杂度最稳定又快的 归并排序，
每次合并两个组时，若后组的当前数较小，则累加前组剩余数的数量（它们都是NXD）

python

def ZW(): # 直娃版cnt=0for i in range(n):b=m[i];	cnt+=sum([1 for j in range(i+1,n) if m[j]<b])return cnt

def SortPop(): # 排序计算cnt=0; m2=m.copy(); v=-1;a=sorted(m,reverse=True); nmax=len(a)-1for j in range(nmax):	# 最后一个数不成对if(v==a[j]): continue;	# 同值的已经处理过了v=a[j]; inds=[i for i in range(len(m2)) if m2[i]==v]nmax-=len(inds);while(len(inds)>0):ind=inds.pop();_=m2.pop(ind);cnt+=len(m2)-indif(nmax<=0): breakreturn cnt

def SortBubble(): # 冒泡法global m2cnt=0for i in range(n):for j in range(n-1-i):if(m2[j]>m2[j+1]):m2[j],m2[j+1]=m2[j+1],m2[j]; cnt+=1;return cnt

def SortMerge(iS=0,iE=None): # 归并法,iS,iE分别为首尾在m中的序号，顾头也顾尾global m2if(iE==None): iE=len(m2)-1if(iS>=iE): return 0iM=(iS+iE)//2; cnt=SortMerge(iS,iM)+SortMerge(iM+1,iE)temp=[]; i_S=iS;j_S=iM+1for j in range(j_S,iE+1):for i in range(i_S,iM+1):if(m2[i]<=m2[j]):temp.append(m2[i]);i_S+=1else:temp.append(m2[j]);cnt+=iM+1-i;i_S=i;j_S+=1;breakelse:breaktemp+=m2[i_S:iM+1]+m2[j_S:iE+1]m2=m2[:iS]+temp+m2[iE+1:]return cnt

C

//直娃版  for (int i=0,b,a;i<n;i++){b=m[i]; a=0;for (int j=i+1;j<n;j++){        	if (m[j]<b) a++;}cnt+=a;} 

//排序计算版 sort(m,m+n,cmp); // 降序排列 mint nmax=n-1; // 最大的对数 （尾-头的序号） for (int i=0;i<n-1;i++){int s2=nmax-m[i].ii; // m[i]的逆序对数为s2= nmax-m[i].ii for (int j=0;j<i;j++){ // 检查已处理过的m，即mi较大或相等的， if (m[j].ii>=m[i].ii){ // 同mi且ii较大的排在前，借机一起减掉 s2--;}}s+=s2;}

//冒泡排序，每遇到一对NXD就交换，记录交换次数 ，~1.3s for (int i=0,t;i<n;i++){for (int j=0;j<n-1-i;j++){if(m[j]>m[j+1]){t=m[j+1];m[j+1]=m[j];m[j]=t;cnt++;}}}

// 归并排序
long long MergeSort(int start, int end) // start和end分别是左边界和右边界
{if (start >= end) return 0;int mid = (start + end) / 2;long long cnt=MergeSort(start, mid)+MergeSort(mid + 1, end);// 合并两个有序序列int length = 0; // 表示辅助空间有多少个元素int i_start = start,	i_end = mid;int j_start = mid + 1,	j_end = end;while (i_start <= i_end && j_start <= j_end){if (m[i_start] <= m[j_start]){temp[length++] = m[i_start++]; }else{temp[length++] = m[j_start++]; cnt+=mid+1-i_start; // cnt}}// 把剩下数的合并while (i_start <= i_end)temp[length++] = m[i_start++]; while (j_start <= j_end)temp[length++] = m[j_start++];// 把辅助空间的数据放到原空间for (int i = 0; i < length; i++) m[start + i] = temp[i];return cnt;
}

小结

python运行时间对比， 冒泡法>>直娃版>排序版>归并版

C++运行时间对比，排序版,冒泡法>直娃版>>归并版