poj2299 Ultra-QuickSort

Ciel Yang 收录于类别练习 OJ解题报告

2017-08-13 2023-04-21 约 1104 字预计阅读 3 分钟

本题考查了排序算法的灵活运用，尤其是如何减少低效排序算法核心操作数量级。

题目描述

题目大意

有 n 个不同的整数组成的数组，对它的唯一合法操作方法就是把相邻的元素进行交换，求一共要多少次交换才能令数组元素以升序排列。

输入

本题有多组输入，每组的输入以一个非负整数开始，表示数组元素的个数 n，接下来 n 行输入代表数组的元素内容；如果 n 为 0 则表示输入结束。

示例输入为：

输出

对应每组输入数据，输出交换的次数。

对应的示例输出为：

知识点解析

归并算法比冒泡排序更高效的原因在于它可以减少非必要的比较。比如：假设归并排序左右子数组排序结果为 [1, 3, 5] 和 [2, 4]，这样在归并的时候 1 就无需和 4 进行比较，可以直接放入正确的位置，同理 2 也无需和 5 比较。所以，每次归并操作都会大量减少非必要元素之间的比较，而冒泡排序则会对所有成对元素进行比较，这就是为什么归并操作会更省时的原因。

解题思路

本题通过相邻元素交换的办法来排序，实际上就是冒泡排序的操作方法，但是只进行必要的交换操作，即按从左到右的顺序摆放正确的元素。那么，每个待冒泡的元素所要交换的次数是上一轮冒泡后元素位置和它的正确位置之间的距离，而这个距离就是包含待冒泡元素的逆序对的个数。所以，本题实际是求数组中的逆序对的个数。

但是，暴力方法统计逆序对实际是冒泡排序的类似算法，相当耗时（必定会 TLE），所以可以参考排序改进的思路减少逆序对的累加操作，本题可以考虑使用归并排序的类似方法进行优化。在归并排序的归并过程中，不仅可以减少比较操作，而且可以减少逆序对的累加计数。只要有右边的子数组元素要归入目标数组，就表示有逆序对产生，而包含这个元素的逆序对个数就是左边数组的剩余元素个数。比如：左右子数组排序结果为 [1, 3, 5] 和 [2, 4]，在将 2 进行归并时，左子数组的剩余元素为 [3, 5]，有两个元素，而归并 4 的时候左边只剩下 5 一个元素，即得到逆序对个数为 3，再递归加上左右子数组的逆序对个数，就能得到正确答案。

代码展示

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

import static java.lang.System.in;

public class Main {

    private static long count(int[] arr) {
        return mergeSort(arr, 0, arr.length - 1);
    }

    private static long mergeSort(int[] arr, int start, int end) {
        if (start == end) return 0L;
        int mid = (start + end) >> 1;
        long left = mergeSort(arr, start, mid);
        long right = mergeSort(arr, mid + 1, end);
        long re = left + right;

        int[] temp = new int[end - start + 1];

        int l = start;
        int r = mid + 1;
        int index = 0;
        while (l <= mid || r <= end) {
            if (r > end || (l <= mid && arr[l] < arr[r])) {
                temp[index++] = arr[l++];
            } else {
                if (l <= mid) re += mid - l + 1;
                temp[index++] = arr[r++];
            }
        }

        for (int i = start, j = 0; i <= end; i++, j++) {
            arr[i] = temp[j];
        }

        return re;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(in));
        while (true) {
            String line = reader.readLine();
            int n = Integer.parseInt(line);
            if (n == 0) break;

            int[] buf = new int[n];
            for (int i = 0; i < n; i++) {
                line = reader.readLine();
                buf[i] = Integer.parseInt(line);
            }

            System.out.println(count(buf));
        }
    }
}

目录