- import java.io.BufferedReader;
- import java.io.File;
- import java.io.FileReader;
- import java.io.IOException;
- import java.util.ArrayList;
- public class IntegerArray {
- private ArrayList<Integer> assignList(ArrayList<Integer> list, int start,
- int end) {
- ArrayList<Integer> des = new ArrayList<Integer>();
- for (int i = start; i < end; i++) {
- des.add(list.get(i));
- }
- return des;
- }
- public long mergerTwoList(ArrayList<Integer> list, int start, int half,
- int end) {
- long count = 0;
- ArrayList<Integer> tempLeft = assignList(list, start, half);
- ArrayList<Integer> tempRight = assignList(list, half, end);
- int leftIndex = 0;
- int rightIndex = 0;
- int index = start;
- while (leftIndex < tempLeft.size() && rightIndex < tempRight.size()) {
- int temp1 = tempLeft.get(leftIndex);
- int temp2 = tempRight.get(rightIndex);
- if (temp1 > temp2) {
- count += tempLeft.size() - leftIndex;
- list.set(index, temp2);
- index++;
- rightIndex++;
- } else {
- list.set(index, temp1);
- index++;
- leftIndex++;
- }
- }
- for (; leftIndex < tempLeft.size(); leftIndex++) {
- list.set(index, tempLeft.get(leftIndex));
- index++;
- }
- for (; rightIndex < tempRight.size(); rightIndex++) {
- list.set(index, tempRight.get(rightIndex));
- index++;
- }
- return count;
- }
- public long getInversions(ArrayList<Integer> list, int start, int end) {
- long count = 0;
- if ((end - start) <= 1)
- return 0;
- int half = start + (end - start) / 2;
- count += getInversions(list, start, half);
- count += getInversions(list, half, end);
- count += mergerTwoList(list, start, half, end);
- return count;
- }
- /**
- * @param args
- */
- public static void main(String[] args) {
- // TODO Auto-generated method stub
- try {
- BufferedReader br = new BufferedReader(new FileReader(new File(
- "IntegerArray.txt")));
- String line;
- ArrayList<Integer> list = new ArrayList<Integer>();
- Integer temp;
- while ((line = br.readLine()) != null) {
- temp = Integer.parseInt(line);
- list.add(temp);
- }
- System.out.println("list size" + list.size());
- int i, j;
- int size = list.size();
- long sum = 0;
- int tempFirst;
- int tempSecond;
- long startTime = System.currentTimeMillis();
- for (i = 0; i < size - 1; i++) {
- tempFirst = list.get(i);
- for (j = i + 1; j < size; j++) {
- tempSecond = list.get(j);
- if (tempFirst > tempSecond)
- sum++;
- }
- }
- long endTime = System.currentTimeMillis();
- // Inversions Force:2407905288 time:143172
- // Inversions Second:2407905288 time:277
- System.out.println("Inversions Force:" + sum + " time:"
- + (endTime - startTime));
- startTime = System.currentTimeMillis();
- IntegerArray ia = new IntegerArray();
- sum = ia.getInversions(list, 0, list.size());
- endTime = System.currentTimeMillis();
- System.out.println("Inversions Second:" + sum + " time:"
- + (endTime - startTime));
- } catch (IOException e) {
- // TODO Auto-generated catch block
- e.printStackTrace();
- }
- }
- }
- //该片段来自于http://www.codesnippet.cn/detail/040620133780.html
来源: http://www.codesnippet.cn/detail/040620133780.html