首页 > 专题系列 > Java解POJ > POJ 2299 Ultra-QuickSort [解题报告] Java
2013
11-11

POJ 2299 Ultra-QuickSort [解题报告] Java

Ultra-QuickSort

问题描述 :

In this problem, you have to analyze a particular sorting algorithm. The algorithm processes a sequence of n distinct integers by swapping two adjacent sequence elements until the sequence is sorted in ascending order. For the input sequence

9 1 0 5 4 ,


Ultra-QuickSort produces the output

0 1 4 5 9 .


Your task is to determine how many swap operations Ultra-QuickSort needs to perform in order to sort a given input sequence.

输入:

The input contains several test cases. Every test case begins with a line that contains a single integer n < 500,000 -- the length of the input sequence. Each of the the following n lines contains a single integer 0 ≤ a[i] ≤ 999,999,999, the i-th input sequence element. Input is terminated by a sequence of length n = 0. This sequence must not be processed.

输出:

For every input sequence, your program prints a single line containing an integer number op, the minimum number of swap operations necessary to sort the given input sequence.

样例输入:

5
9
1
0
5
4
3
1
2
3
0

样例输出:

6
0

解题代码:

import java.io.BufferedInputStream;   
import java.util.Scanner;   
public class Main {   
  
    static long num = 0;  
  
    public static void main(String[] args) {   
        Scanner scan = new Scanner(new BufferedInputStream(System.in));   
        while (scan.hasNext()) {   
            int n = scan.nextInt();   
            if (n == 0) {   
                break;   
            }   
            num = 0;   
            int data[] = new int[n];   
            for (int i = 0; i < n; i++) {   
                data[i] = scan.nextInt();   
            }   
            mergeSort(data, 0, n - 1);   
            System.out.println(num);   
        }   
    }   
  
    static void mergeSort(int[] array, int left, int right) {   
  
        if (left < right) {   
            int center = (left + right) / 2;   
            mergeSort(array, left, center);   
            mergeSort(array, center + 1, right);   
            Merge(array, left, center, right);   
        }   
    }   
  
    static void Merge(int[] array, int left, int center, int right) {   
        //[1,2,3,4] left=1,ceter=2,right=4   
        int[] temp = new int[right - left + 1];  
        int i = left;   
        int j = center + 1;   
        int k = 0;   
        while (i <= center && j <= right) {   
            if (array[i] > array[j]) {   
                temp[k++] = array[j++];   
               
                num += center - i + 1;   
  
            } else {   
                temp[k++] = array[i++];   
            }   
        }   
        while (i <= center) {   
            temp[k++] = array[i++];   
        }   
        while (j <= right) {   
            temp[k++] = array[j++];   
        }   
        for (i = left, k = 0; i <= right; i++, k++) {   
            array[i] = temp[k];   
        }   
    }   
}

  1. 第二种想法,我想来好久,为啥需要一个newhead,发现是把最后一个节点一直返回到嘴上面这层函数。厉害,这道题之前没样子想过。