头像

ulanbator

安徽大学




离线:9天前



ulanbator
12天前

/
1.逆序的定义巧妙的结合了归并排序,可利用归并排序的模板去做
2.对于一个已经排好顺序的左右部分数组,如果右边的某个数小于
坐标的某个数,那么左边这个数到数组的结尾的数的总个数就是右边
这个数的逆序对
3.注意数据范围,N=100010,最差的情况全是逆序数组,那么逆序对
个数是N(N-1)/2,超过JAVA中int范围,所以返回类型要用long
/
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] + " ");
    }

}

}