import java.util.Scanner; public class Solution { /** * @param args */ static int sum = 0; public static void main(String[] args) { // TODO Auto-generated method stub Scanner in = new Scanner(System.in); while (in.hasNext()) { int n = in.nextInt(); int[] arr = new int[n]; for (int i = 0; i < n; i++) { arr[i] = in.nextInt(); } int lo = 0; int hi = n - 1; quick(arr, lo, hi); System.out.println(sum); } } public static void quick(int[] arr, int lo, int hi) { if (hi <= lo) { return; } int lt = lo; int i = lo + 1; int gt = hi; int tmp = arr[lo]; while (i <= gt) { if (arr[i] < tmp) { swap(arr, lt++, i++); } else if (arr[i] > tmp) { swap(arr, i, gt--); } else { i++; } } quick(arr, lo, lt - 1); quick(arr, gt + 1, hi); } public static void swap(int[] a, int i, int j) { if (a[i] != a[j]) sum++; int tmp = a[i]; a[i] = a[j]; a[j] = tmp; } } 三向切分快排，不知道好不好使