数组的逆序对个数
程序员文章站
2022-05-10 15:33:12
...
计算数组的逆序对个数
如果按照升序为准,如果数组已经按照升序排列,则逆序对个数为0;若数组是降序排列的,则逆序对个数最多。
可以使用归并排序解决
public void sort(int[] n,int start,int end,int[] t){
//计算数组的中间位置
int mid = start + (end - start) / 2;
if(start < end){
//前半段排序
sort(n,start,mid,t);
//后半段排序
sort(n,mid+1,end,t);
//合并
merge(n,start,mid,end,t);
}
}
static void merge(int[] n,int start,int mid,int end,int[] t){
int[] tmp = new int[end - start + 1];
int i = start;
int j = mid+1;
int k = 0;
//遍历前后数组,并进行排序,将排序结果保存在临时数组中
while(i <= mid && j <= end){
if(n[i] > n[j]){
tmp[k++] = n[j++];
t[0] += (mid + 1 - i);
} else {
tmp[k++] = n[i++];
}
}
//将左边剩余数加到临时数组
while(i <= mid){
tmp[k++] = n[i++];
}
//将右边剩余数加到临时数组
while(j <= end){
tmp[k++] = n[j++];
}
//将临时数组的内容覆盖原来数组的内容
for(int m=0; m<tmp.length; m++){
n[m+start] = tmp[m];
}
}
//测试案例
public static void main(String[] args){
int[] d = new int[]{1,5,7,9,3,2};
int[] t = new int[1];
sort(d,0,5,t);
}
下一篇: 剑指offer——数组中的逆序对