AcWing 107. 超快速排序--java解释
原题链接
简单
作者:
OneDay1
,
2021-02-07 14:45:21
,
所有人可见
,
阅读 416
//类型需要使用long,要不数据超int会wa
import java.util.Scanner;
public class Main{
static long[] a = new long[500010];
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
while(true){
int n = sc.nextInt();
if(n ==0) break;
for(int i = 0; i < n; i++){
a[i] = sc.nextLong();
}
System.out.println(ksort(a,0,n-1));
}
}
public static long ksort(long[] a,int l,int r){
// 出口
if(l >=r) return 0;
int mid = l+r>>1;
long count = 0;
// 两边进行排序
//两个区间排序的过程也有交换的地方
count = ksort(a,l,mid)+ksort(a,mid+1,r);
// 归并
int i = l,j = mid +1 ,k=0;
long[] temp = new long[r-l+1];
while(i <= mid && j <= r){
if(a[i] >a[j]){
//如果i这个位置大于j的位置元素,那么,表示i后面的元素都要大于j后面的中的元素
//那么需要把小于的一边元素保存到temp的临时数组中
//那么需要交换的次数是mid - i +1
temp[k++] = a[j++];
count += mid - i +1
}
else{
temp[k++] = a[i++];
}
}
//将j-r循环完的元素,l-mid没有循环完的元素保存到temp中
while(i<=mid) temp[k++] = a[i++];
//将l-mid循环完的元素,j-r没有循环完的元素保存到temp中
while(j<=r) temp[k++] = a[j++];
for (i = l, j = 0; i <= r; i ++, j ++ ) a[i] = temp[j];
return count;
}
}