ulanbator

84

ulanbator
12天前

/
1.逆序的定义巧妙的结合了归并排序，可利用归并排序的模板去做
2.对于一个已经排好顺序的左右部分数组，如果右边的某个数小于

3.注意数据范围，N=100010,最差的情况全是逆序数组，那么逆序对

/
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main{

static int N = 100010;
static int[] array = new int[N];
static int[] tmp = new int[N];

public static long mergeSort(int l, int r){

if(l >= r) return 0;
int mid = l + r >> 1;
long count = mergeSort(l, mid) + mergeSort(mid + 1, r);//无需初始化
int i = l, j = mid + 1, k = 0;
while(i <= mid && j <= r){
if(array[i] <= array[j]) tmp[k++] = array[i++];//前半部分小于后面
else{//大于，构成逆序对
tmp[k++] = array[j++];
count += mid - i + 1;
}
}
while(i <= mid) tmp[k++] = array[i++];
while(j <= r)   tmp[k++] = array[j++];
for(i = l, j = 0; i <=r ; i++, j++) array[i] = tmp[j];
return count;

}

public static void main(String[] args) throws IOException{

BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(in.readLine());
String[] arry = in.readLine().split(" ");
for(int i = 0; i < n; i++){
array[i] = Integer.parseInt(arry[i]);
}
long result = mergeSort(0, n-1);
System.out.print(result);

}


}

ulanbator
12天前

/*
1.归并排序也是一种分治的思想，首先是确定整个数组的中间位置；
2.再递归执行整个函数
3.合并

*/
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main{

static int N = 100010;
static int[] array = new int[N];
static int[] tmp = new int[N];

public static void mergeSort(int l, int r){

if(l >= r) return;
int mid = l + r >> 1;
mergeSort(l, mid);
mergeSort(mid+1, r);
int i = l, j = mid + 1, k = 0;
while(i <= mid && j <= r){
if(array[i] <= array[j]) tmp[k++] = array[i++];
else tmp[k++] = array[j++];
}
while(i <= mid) tmp[k++] = array[i++];
while(j <= r)   tmp[k++] = array[j++];
for(i = l, j = 0; i <= r; i++, j++ ) array[i] = tmp[j];

}

public static void main(String[] args) throws IOException{

BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(in.readLine());
String[] arry = in.readLine().split(" ");
for(int i = 0; i < n; i++){
array[i] = Integer.parseInt(arry[i]);
}
mergeSort(0, n-1);
for(int i = 0; i < n; i++){
System.out.print(array[i] + " ");
}

}


}

ulanbator
12天前

/
1.选择哨兵，可以是数组中的任意位置
2.通过比较来使得位于哨兵左侧的数组元素是小于哨兵的，而位于哨兵右侧的数组元素是大于哨兵的
3.双递归执行左右两部分
4.注意do while执行要区间外移一个单位
/

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main{

static int N = 100010;
static int[] array = new int[N];

public static void quickSort(int l, int r){

if(l >= r) return;

// int key = l + r >> 1, i = l-1, j = r + 1; key是关键字的值 不是下标
int key = array[l + r >> 1], i = l - 1, j = r + 1;
while(i < j){
do i++;while(array[i] < key);
do j--;while(array[j] > key);
if(i < j){
int tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
}
quickSort(l, j);
quickSort(j+1, r);
}

public static void main(String[] args) throws IOException{
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(in.readLine());
String[] arry = in.readLine().split(" ");
for(int i = 0; i < n; i++){
array[i] = Integer.parseInt(arry[i]);
}
quickSort(0, n-1);
for(int i = 0; i< n; i++){
System.out.print(array[i] + " ");
}

}


}