int count = 0
for (int i = 0 i < array.length i++) {
for (int j = i + 1 j < array.length j++) {
if (array[i] > array[j]) {
count++
}
}
}
return count
} private static int count = 0
private void count(int[] array) {
int length = array.length
int left = (int) (length / 2 + 0.5)
int right = length / 2
int[] leftArray = new int[left]
int[] rightArray = new int[right]
System.arraycopy(array, 0, leftArray, 0, left)
System.arraycopy(array, left, rightArray, 0, right)
if (left > 1 && right > 1) {
count(leftArray)
count(rightArray)
}
Arrays.sort(leftArray)
Arrays.sort(rightArray)
mergeCount(leftArray, rightArray)
}
private void mergeCount(int[] leftArray, int[] rightArray) {
int leftLength = leftArray.length
int rightLength = rightArray.length
while (leftLength > 0 && rightLength > 0) {
if (leftArray[0] > rightArray[0]) {
count = count + leftLength
System.arraycopy(rightArray, 1, rightArray, 0, rightLength - 1)
rightLength--
} else {
System.arraycopy(leftArray, 1, leftArray, 0, leftLength - 1)
leftLength--
}
}
} private static Node[] nodes
private static int[] tree
private static int[] reflect
private static int length
private static int countArray(int[] array) {
init(array)
return doCount()
}
private static int doCount() {
for (int i = 0 i < length i++) {
reflect[nodes[i].pos] = i + 1
}
int count = 0
for (int i = 1 i <= length i++) {
update(reflect[i])
count = count + i - sum(reflect[i])
}
System.out.println(count)
return count
}
private static void init(int[] array) {
length = array.length
nodes = new Node[length]
reflect = new int[length + 1]
tree = new int[length + 1]
for (int i = 0 i < length i++) {
nodes[i] = new Node()
nodes[i].value = array[i]
nodes[i].pos = i + 1
}
Arrays.sort(nodes, Comparator.comparingInt(o -> o.value))
}
private static int lowbit(int x) {
return x & (-x)
}
private static void update(int pos) {
while (pos <= length) {
tree[pos] += 1
pos += lowbit(pos)
}
}
private static int sum(int pos) {
int sum = 0
while (pos > 0) {
sum += tree[pos]
pos -= lowbit(pos)
}
return sum
}
public static void main(String args[]) {
int[] array = {40000000, 20000000, 3000000, 534435454, 732123434, 167675688, 46565656, 8}
System.out.println(countArray(array))
}
//---------------//
class Node {
int value
int pos
}
用求余数的方法,求一个四位正整数的逆序数的Java程序如下:
import java.util.Scannerpublic class AA {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in)
System.out.print("请输入一个四位正整数:")
int n=sc.nextInt()
if(n<1000 || n>9999){
System.out.println("您输入的不是一个四位正整数!")
}else{
int a,b,c,d,result
a=n/1000//取四位正整数的千位数
b=n/100%10//取四位正整数的百位数
c=n/10%10//取四位正整数的十位数
d=n%10////取四位正整数的个位数
result=d*1000+c*100+b*10+a
System.out.println("四位正整数"+n+"的逆序数为:"+result)
}
}
}
运行结果:
请输入一个四位正整数:1234
四位正整数1234的逆序数为:4321
