「Acwing算法合集」
Acwing算法系列文章
一、快速排序
题目如下：
输入格式
输入共两行，第一行包含整数 n。
第二行包含 n 个整数（所有整数均在 1∼10^9 范围内），表示整个数列。
输出格式
输出共一行，包含 n 个整数，表示排好序的数列。
数据范围
1≤n≤100000
输入样例：
5
3 1 2 4 5
输出样例：
1 2 3 4 5
代码如下：
import java.util.*;public class Main{ public static void swap(int[] arr, int i, int j){ int help = arr[i]; arr[i] = arr[j]; arr[j] = help; } public static int[] partition(int[] arr, int l, int r){ if(l > r){ return new int[]{-1, -1}; } if(l == r){ return new int[]{l, r}; } int less = l - 1; int more = r; int index = l; while(index < more){ if(arr[index] == arr[r]){ ++index; }else if(arr[index] < arr[r]){ swap(arr, index++, ++less); }else{ swap(arr, index, --more); } } swap(arr, more, r); return new int[]{less+1, more}; } public static void process3(int[] arr, int l, int r){ if(l >= r){ return ; } swap(arr, l + (int)(Math.random() * (r - l + 1)), r); int[] p = partition(arr, l, r); process3(arr, l, p[0] - 1); process3(arr, p[1] + 1, r); } public static void main(String[] args){ Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] arr = new int[n]; for(int i = 0; i < n;++i){ arr[i] = sc.nextInt(); } process3(arr, 0, n - 1); for(int i = 0; i < n; ++i){ System.out.print(arr[i] + " "); } }} 运行结果：
二、第k个数
题目如下：
给定一个长度为 n 的整数数列，以及一个整数 k，请用快速选择算法求出数列从小到大排序后的第 k 个数。
输入格式
第一行包含两个整数 n 和 k。
第二行包含 n 个整数（所有整数均在 1∼10^9 范围内），表示整数数列。
输出格式
输出一个整数，表示数列的第 k 小数。
数据范围
1≤n≤100000,
1≤k≤n
输入样例：
5 3
2 4 1 5 3
输出样例：
3
代码如下：
import java.util.*;public class Main{ public static void swap(int[] arr, int i, int j){ int help = arr[i]; arr[i] = arr[j]; arr[j] = help; } public static int[] partition(int[] arr, int l, int r){ if(l > r){ return new int[]{-1,-1}; } if(l == r){ return new int[]{l, r}; } int less = l - 1; int more = r; int index = l; while(index < more){ if(arr[index] == arr[r]){ ++index; } else if(arr[index] < arr[r]){ swap(arr, index++, ++less); }else{ swap(arr, index, --more); } } swap(arr, more, r); return new int[]{less + 1, more}; } public static void process(int[] arr, int l, int r){ if(l >= r){ return; } swap(arr, l + (int)(Math.random() * (r - l + 1)), r); int[] p = partition(arr, l, r); process(arr, l, p[0] - 1); process(arr, p[1] + 1, r); } public static void main(String[] args){ Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int k = sc.nextInt(); int[] arr = new int[n]; for(int i = 0; i < n; i++){ arr[i] = sc.nextInt(); } process(arr, 0, n - 1); System.out.println(arr[k - 1]); }}运行结果：
三、 归并排序
题目如下：
给定你一个长度为 n 的整数数列。
请你使用归并排序对这个数列按照从小到大进行排序。
并将排好序的数列按顺序输出。
输入格式
输入共两行，第一行包含整数 n。
第二行包含 n 个整数（所有整数均在 1∼10^9 范围内），表示整个数列。
输出格式
输出共一行，包含 n 个整数，表示排好序的数列。
数据范围
1≤n≤100000
输入样例：
5
3 1 2 4 5
输出样例：
1 2 3 4 5
代码如下：
import java.util.*;public class Main{ public static void mergeSort(int[] arr){ mergeSort(arr, 0, arr.length - 1); } public static void mergeSort(int[] arr, int l, int r){ if(l >= r){ return; } int mid = l + ((r - l) >> 1); mergeSort(arr, l, mid); mergeSort(arr, mid + 1, r); merge(arr, l, mid, r); } public static void merge(int[] arr, int l, int m, int r){ int[] help = new int[r - l + 1]; int i = 0; int p1 = l; int p2 = m + 1; while(p1 <= m && p2 <= r){ help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++]; } while(p1 <= m){ help[i++] = arr[p1++]; } while(p2 <= r){ help[i++] = arr[p2++]; } for(i = 0; i < help.length; ++i){ arr[l + i] = help[i]; } } public static void main(String[] args){ Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] arr = new int[n]; for(int i = 0; i < n; ++i){ arr[i] = sc.nextInt(); } mergeSort(arr); for(int i = 0; i < n; ++i){ System.out.print(arr[i] + " "); } }}运行结果：
四、逆序对的数量
题目如下：
给定一个长度为 n 的整数数列，请你计算数列中的逆序对的数量。
逆序对的定义如下：对于数列的第 i 个和第 j 个元素，如果满足 ia[j]，则其为一个逆序对；否则不是。
输入格式
第一行包含整数 n，表示数列的长度。
第二行包含 n 个整数，表示整个数列。
输出格式
输出一个整数，表示逆序对的个数。
数据范围
1≤n≤100000，
数列中的元素的取值范围 [1,10^9]。
输入样例：
6
2 3 4 5 6 1
输出样例：
5
代码如下：
import java.util.*;public class Main{ public static long res = 0; public static void mergeSort(int[] arr){ mergeSort(arr, 0, arr.length - 1); } public static void mergeSort(int[] arr, int l, int r){ if(l >= r){ return; } int mid = l + ((r - l) >> 1); mergeSort(arr, l, mid); mergeSort(arr, mid + 1, r); merge(arr, l, mid, r); } public static void merge(int[] arr, int l, int m, int r){ int[] help = new int[r - l + 1]; int i = 0; int p1 = l; int p2 = m + 1; while(p1 <= m && p2 <= r){ res += arr[p1] > arr[p2] ? (m - p1 + 1) : 0; help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++]; } while(p1 <= m){ help[i++] = arr[p1++]; } while(p2 <= r){ help[i++] = arr[p2++]; } for(i = 0; i < help.length; ++i){ arr[l + i] = help[i]; } } public static void main(String[] args){ Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] arr = new int[n]; for(int i = 0; i < n; ++i){ arr[i] = sc.nextInt(); } mergeSort(arr); System.out.println(res); }}运行结果：
