科威网络做网站怎么样,建设部质量监督官方网站,有没有可以做游戏的网站,网站站长是什么theme: channing-cyan
归并排序
归并排序是一种分治算法#xff0c;将待排序的数组递归地分成两半#xff0c;分别排序#xff0c;然后将两个有序的子数组归并成一个有序数组。将数组不断地二分#xff0c;直到子数组的长度为1时#xff0c;认为其有序。然后将相邻的两个…
theme: channing-cyan
归并排序
归并排序是一种分治算法将待排序的数组递归地分成两半分别排序然后将两个有序的子数组归并成一个有序数组。将数组不断地二分直到子数组的长度为1时认为其有序。然后将相邻的两个有序子数组进行归并直到整个数组有序
时间复杂度 归并排序的时间复杂度为O(nlogn)其中n为数组的长度
题目与代码
题目
给定你一个长度为 n的整数数列。
请你使用归并排序对这个数列按照从小到大进行排序。
并将排好序的数列按顺序输出。
输入格式
输入共两行第一行包含整数 n。
第二行包含 n 个整数所有整数均在 1∼109 范围内表示整个数列。
输出格式
输出共一行包含 n 个整数表示排好序的数列。
数据范围
1≤n≤100000
输入样例
5
3 1 2 4 5输出样例
1 2 3 4 5代码
import java.util.Scanner;public class Main {static int n, N (int) 1e5 10;static int[] a new int[N], tmp new int[N];public static void main(String[] args) {Scanner in new Scanner(System.in);n in.nextInt();for (int i 0; i n; i) {a[i] in.nextInt();}mergeSort(a, 0, n - 1);for (int i 0; i n; i) {System.out.print(a[i] );}}/*** 归并排序** param q 待排序数组* param l 左边界* param r 右边界*/public static void mergeSort(int[] q, int l, int r) {if (l r) {return;}int mid l r 1;mergeSort(q, l, mid);mergeSort(q, mid 1, r);merge(q, l, mid, r);}/*** 归并操作** param q 待排序数组* param l 左边界* param mid 中间位置* param r 右边界*/public static void merge(int[] q, int l, int mid, int r) {int k 0, i l, j mid 1;while (i mid j r) {if (q[i] q[j]) {tmp[k] q[i];} else {tmp[k] q[j];}}while (i mid) {tmp[k] q[i];}while (j r) {tmp[k] q[j];}for (i l, j 0; i r; i, j) {q[i] tmp[j];}}
}
788. 逆序对数量
题目
给定一个长度为 n 的整数数列请你计算数列中的逆序对的数量。
逆序对的定义如下对于数列的第 i个和第 j 个元素如果满足 ij 且 a[i]a[j]则其为一个逆序对否则不是。
输入格式
第一行包含整数 n表示数列的长度。
第二行包含 n 个整数表示整个数列。
输出格式
输出一个整数表示逆序对的个数。
数据范围
1≤n≤100000 数列中的元素的取值范围 [1,109]
输入样例
6
2 3 4 5 6 1输出样例
5代码
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;public class Main {static int n,N (int)1e5 10;static int[] a new int[N], tmp new int[N];public static void main(String[] args) {Scanner in new Scanner(System.in);n in.nextInt();for (int i 0;i n;i ) {a[i] in.nextInt();}System.out.println(merge_sort(a, 0 , n - 1));}public static long merge_sort(int[] q, int l, int r) {if (l r) {return 0;}int mid l r 1;long res merge_sort(q, l, mid) merge_sort(q, mid 1, r);int k 0, i l, j mid 1;while (i mid j r) {if (q[i] q[j]) {tmp[k ] q[i ];} else{res mid - i 1;tmp[k ] q[j ];}}while (i mid) {tmp[k ] q[i ];}while (j r) {tmp[k ] q[j ];}for (i l, j 0; i r; i , j ) {q[i] tmp[j];}return res;}}
