求一個(gè)數(shù)組的逆序數(shù)對(duì)的個(gè)數(shù)(歸并排序)
// merge函數(shù)求出在arr[l...mid]和arr[mid+1...r]有序的基礎(chǔ)上, arr[l...r]的逆序數(shù)對(duì)個(gè)數(shù)
private static long merge(Comparable[] arr, int l, int mid, int r) {
Comparable[] aux = Arrays.copyOfRange(arr, l, r+1);
// 初始化逆序數(shù)對(duì)個(gè)數(shù) res = 0
long res = 0L;
// 初始化，i指向左半部分的起始索引位置l志衍；j指向右半部分起始索引位置mid+1
int i = l, j = mid+1;
for( int k = l ; k <= r; k ++ ){
if( i > mid ){ // 如果左半部分元素已經(jīng)全部處理完畢
arr[k] = aux[j-l];
j ++;
}
else if( j > r ){ // 如果右半部分元素已經(jīng)全部處理完畢
arr[k] = aux[i-l];
i ++;
}
else if( aux[i-l].compareTo(aux[j-l]) <= 0 ){ // 左半部分所指元素 <= 右半部分所指元素
arr[k] = aux[i-l];
i ++;
}
else{ // 右半部分所指元素 < 左半部分所指元素
arr[k] = aux[j-l];
j ++;
// 此時(shí), 因?yàn)橛野氩糠謐所指的元素小
// 這個(gè)元素和左半部分的所有未處理的元素都構(gòu)成了逆序數(shù)對(duì)
// 左半部分此時(shí)未處理的元素個(gè)數(shù)為 mid - j + 1
res += (long)(mid - i + 1);
}
}
return res;
}
// 求arr[l..r]范圍的逆序數(shù)對(duì)個(gè)數(shù)
// 思考: 歸并排序的優(yōu)化可否用于求逆序數(shù)對(duì)的算法? :)
private static long solve(Comparable[] arr, int l, int r) {
if (l >= r)
return 0L;
int mid = l + (r-l)/2;
// 求出 arr[l...mid] 范圍的逆序數(shù)
long res1 = solve(arr, l, mid);
// 求出 arr[mid+1...r] 范圍的逆序數(shù)
long res2 = solve(arr, mid + 1, r);
return res1 + res2 + merge(arr, l, mid, r);
}
public static long solve(Comparable[] arr){
int n = arr.length;
return solve(arr, 0, n-1);
}
求出nums里第k小的數(shù)(快速排序)
// 對(duì)arr[l...r]部分進(jìn)行partition操作
// 返回p, 使得arr[l...p-1] < arr[p] ; arr[p+1...r] > arr[p]
// partition 過(guò)程, 和快排的partition一樣
// 思考: 雙路快排和三路快排的思想能不能用在selection算法中? :)
private static int partition(Comparable[] arr, int l, int r){
// 隨機(jī)在arr[l...r]的范圍中, 選擇一個(gè)數(shù)值作為標(biāo)定點(diǎn)pivot
swap( arr, l , (int)(Math.random()*(r-l+1))+l );
Comparable v = arr[l];
int j = l; // arr[l+1...j] < v ; arr[j+1...i) > v
for( int i = l + 1 ; i <= r ; i ++ )
if( arr[i].compareTo(v) < 0 ){
j ++;
swap(arr, j, i);
}
swap(arr, l, j);
return j;
}
// 求出nums[l...r]范圍里第k小的數(shù)
private static Comparable solve(Comparable[] nums, int l, int r, int k){
if( l == r )
return nums[l];
// partition之后, nums[p]的正確位置就在索引p上
int p = partition(nums, l, r);
if( k == p ) // 如果 k == p, 直接返回nums[p]
return nums[p];
else if( k < p ) // 如果 k < p, 只需要在nums[l...p-1]中找第k小元素即可
return solve( nums, l, p-1, k);
else // 如果 k > p, 則需要在nums[p+1...r]中找第k-p-1小元素
// 注意: 由于我們傳入__selection的依然是nums, 而不是nums[p+1...r],
// 所以傳入的最后一個(gè)參數(shù)依然是k, 而不是k-p-1
return solve( nums, p+1, r, k );
}
// 尋找nums數(shù)組中第k小的元素
// 注意: 在我們的算法中, k是從0開(kāi)始索引的, 即最小的元素是第0小元素, 以此類推
// 如果希望我們的算法中k的語(yǔ)意是從1開(kāi)始的, 只需要在整個(gè)邏輯開(kāi)始進(jìn)行k--即可, 可以參考solve2
public static Comparable solve(Comparable nums[], int k) {
assert nums != null && k >= 0 && k < nums.length;
return solve(nums, 0, nums.length - 1, k);
}
// 尋找nums數(shù)組中第k小的元素, k從1開(kāi)始索引, 即最小元素是第1小元素, 以此類推
public static Comparable solve2(Comparable nums[], int k) {
return Selection.solve(nums, k - 1);
}
private static void swap(Object[] arr, int i, int j) {
Object t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
