AcWing
  • 首页
  • 课程
  • 题库
  • 更多
    • 竞赛
    • 题解
    • 分享
    • 问答
    • 应用
    • 校园
  • 关闭
    历史记录
    清除记录
    猜你想搜
    AcWing热点
  • App
  • 登录/注册

AcWing 107. 超快速排序    原题链接    简单

作者: 作者的头像   小呆呆 ,  2019-10-21 09:03:20 ,  所有人可见 ,  阅读 4870


15


2

引理:逆序数

在一个排列中,如果一对数的前后位置与大小顺序相反,即前面的数大于后面的数,那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。
该排列的逆序数等于该排列转化为自然排序(从小到大)的最小次数
例如:31425 的逆序数为3

  • 3无逆序,则n1 = 0,

  • 1逆序有3,则n2 = 1,

  • 4无逆序,则n3 = 0,

  • 2逆序有3,4,则n4 = 2,

  • 5无逆序,则n5 = 0,

  • 若将该序列转化成从小到大排序,需要(n1 + n2 + n3 + n4 + n5)次交换。

直接计算

计算一个排列的逆序数的直接方法是逐个枚举逆序,同时统计个数。例如在序列 { 3, 1, 4, 2, 5 } 中,逆序依次为 (3,1),(3,2),(4,3),因此该序列的逆序数为 3。

归并排序

直接计数法虽然简单直观,但是其时间复杂度是O(n^2)。一个更快的计算方法是在归并排序的同时计算逆序数。且该方法只是交换相邻的两个元素,符合题意。

算法分析

(归并排序)
  • 给定两个有序序列,从右边序列中最小的元素开始往左边序列中插入,设右边序列中选定的元素的位置为j,左边序列选定的元素位置为i,中间位置为mid,则此时交换的位置次数是(mid - i + 1),最后把所有归并后交换的次数累加在一起即可。

  • 例如 31425 经过归并后得出两个有序序列 134 和 25 (注意:314也是需要归并交换位置得到123的)即将2 插入到3位置前,此操作相当于交换了两次位置,设3元素的位置为i,4元素的位置是中间位置mid,则此时交换的次数为(mid - i + 1) = 2次

附上主播的图
ec8d32d62b62e7be74d4fe56db175a7.png

时间复杂度$O(nlogn)$

Java 代码


import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static long count = 0;
    static long[] arr = new long[500010];
    public static void merge_sort(long q[], int l, int r)
    {
        if (l >= r) return;
        int mid = l + r >> 1;
        merge_sort(q, l, mid);
        merge_sort(q, mid + 1, r);
        long[] tmp = new long[r - l + 1];
        int k = 0, i = l, j = mid + 1;
        while (i <= mid && j <= r)

            if (q[i] > q[j]) {tmp[k ++ ] = q[j ++ ];count += mid - i + 1;}
            else tmp[k ++ ] = q[i ++ ];

        while (i <= mid) tmp[k ++ ] = q[i ++ ];
        while (j <= r) tmp[k ++ ] = q[j ++ ];

        for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
    }
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        while(scan.hasNext())
        {
            int n = scan.nextInt();
            if(n == 0) break;
            for(int i = 0;i < n;i++) arr[i] =  scan.nextLong();
            merge_sort(arr,0,n - 1);
            System.out.println(count);
            count = 0;
        }
    }

}

1 评论


用户头像
虚怀   2020-04-25 09:23         踩      回复
import java.util.*;
class Main{
    public static long merge(long[] arr, int lo, int mid, int hi){
        long[] t = Arrays.copyOf(arr, arr.length);
        int i = lo, j = mid + 1, k = lo;
        long res = 0;
        while(i <= mid && j <= hi){
            if(t[i] > t[j]){
                res += mid - i + 1;
                arr[k++] = t[j++];
            }else{
                arr[k++] = t[i++];
            }
        }
        while(i <= mid){
            arr[k++] = t[i++];
        }
        while(j <= hi){
            arr[k++] = t[j++];
        }
        return res;
    }

    public static long ms(long[] arr, int lo, int hi){
        if(lo < hi){
            int mid = (lo + hi) / 2;
            long left = ms(arr, lo, mid);
            long right = ms(arr, mid + 1, hi);
            return left + right + merge(arr, lo, mid, hi);
        }
        return 0;
    }

    public static void main(String[] argv){
        Scanner in = new Scanner(System.in);
        int n = 0;
        while((n = in.nextInt()) != 0){
            long[] arr = new long[n];
            while(n-- > 0){
                arr[arr.length - 1 - n] = in.nextLong();
            }
            long res = 0;
            System.out.println(Main.ms(arr, 0, arr.length - 1));
        }
    }
}

为什么我的代码超时了?求解


App 内打开
你确定删除吗?
1024
x

© 2018-2025 AcWing 版权所有  |  京ICP备2021015969号-2
用户协议  |  隐私政策  |  常见问题  |  联系我们
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标 qq图标
请输入绑定的邮箱地址
请输入注册信息