前言
什么是数据结构与算法
- 数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。
- 算法：解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作。
正文
几种简单的排序算法
-
根据左神的入门新手班视频，开头先介绍了几种时间复杂度稳定的排序算法
-
首先定义了基本的数组元素交换方法
/** 声明一个临时变量tmp存储数组j 然后把数组i赋值给数组j 把tmp赋值给arr[i] */ public static void swap(int[] arr,int i ,int j){ int tmp = arr[j]; int arr[j] = arr[i]; int arr[i] = tmp; } //根据异或运算特性 N = 0 ^ N,0 = N ^ N public static void swap1(int[] arr,int i ,int j){ if (i == j){ return; //防止指针指到相同区域 } int arr[i] = arr[i] ^ arr[j]; int arr[j] = arr[i] ^ arr[j]; int arr[i] = arr[i] ^ arr[j]; }以下几种排序算法默认都是单挑递增，且时间复杂度均是O($n^2$)
冒泡排序
- 首先对输入的arr做一个判断，确定一开始的边界条件，如果是null或者长度是1，则不用排序，直接返回。
- 首先做第一个for循环
- 对数组中每个元素遍历，这里默认从最后一个元素开始，
- 因为最后一个元素肯定是最大值，因此在做一个for循环，从第二个元素开始，开始和前一个元素做对比，如果arr[j-1] > arr[j],则说明前一个元素比后一个元素，不满足单调递增，因此，进行互换。
public static void bubbleSort(int[] arr){
if( arr == null || arr.lenth < 2){
return;
}
int len = arr.length;
for(int end = len - 1; end >=0 ;end--){
for(int j = 1 ; j <= end;j++){
if(arr[j-1] > arr[j]){
swap(arr,j-1,j);
}
}
}
}
选择排序
- 因为这个排序是单调递增，因此做一个for循环，求每次这个for循环上该最小值的索引位置，将他和当前的循环i做交换，就能返回这个数组的单调递增排序
public static void selectSort(int[] arr){
if( arr ==null || arr.length < 2){
return;
}
int len = arr.lenth;
for(int i = 0 ;i< len - 1;i++){
minIndex = i;
for(int j = i + 1 ; J < len -1 ;j++){
if(arr[minIndex] < arr[j]){
minIndex = j;
}
}
swap(arr,i,minIndex);
}
}
插入排序
-
当前这个排序是单调递增的，因此，先做第一层for循环，下标是i，从下标1开始，并开启第二层for循环
-
对下标 0 ~ i之间的元素进行for循环，依次判断arr[ j ] 和 arr[ j + 1 ]的大小，如果 arr[ j ] > arr[ j + 1 ] ，则交换位置，并判断j-1个位置，直到不满足该条件，或者j>0，这时能保证下标 i 的元素是单调定增的
-
该算法因为遇到大体递增的数列，能减少循环次数，比冒泡和选择效率高一点，但是时间复杂度依旧是O($n^2$)
public static void insertSort(int[] arr){ if(arr == null || arr.length < 2){ return; } for(int i = 1;i < arr.length ;i++){ for(int j = i - 1;j> 0 && arr[j] > arr[j+1]; j--){ swap(arr,j,j+1) } } }
归并排序
递归版本
- 思路：
- 归并排序就是利用归并的思想实现的排序方法。它的原理是假设初始序列含有n个记录，则可以看成是n个有序的子序列，每个子序列的长度为1，然后两两合并，得到$⌈n/2⌉$($⌈x⌉$表示不小于x的最小整数)个长度为2或1的有序子序列；再两两归并。。。。。如此重复，直至得到一个长度为n的有序序列为止
- 具体步骤
- 1.声明一个函数，把数组给拆分成左一半，右一半
- 2.声明一个归并函数，把左半边数组和右半边数组做一个排序，分别声明左指针和右指针，对左右指针比大小，然后依次排序
public static void mergeSort1(int[] arr){
if(arr == null || arr.length < 2){
return;
}
}
public static void process(int[] arr,int L,int R){
if(L == R){
return;
}
int mid = L +(R-L)>>1;
process(arr,L,mid);
process(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];//数组长度就是L~R之间的元素个数，包含L，因此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];
}
}
非递归版本
思路：
-
声明一个步长step，step初始值是1，
-
把数组划分成n个数组，划分之后的n个数组每个数组之间的长度是2step，最后一个数组长度如果满足大于step，则将他划分为左区间：$[L,L+step-1]$,右区间：$[L+step,length-1]$
-
对步长进行循环，step=step*2,直到step>length>>1,表明当前的步长正好能将该数组分为左右两区间
//这个函数是用来归并数组某个范围上的排序
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 mergerSort(int[] arr){
if(arr == null || arr.length < 2){
return;
}
int step = 1;
int N = arr.length;
while(step < N){
int L = 0;
while(L < N){ //左区间只要小于当前数组的长度，就对左区间做归并排序的操作
int M = 0; //中间
if(N - L >= step){
// N-1 -L+1 = N - L,表示的是数组的总长度到左数组的左区间之间的距离
//数组的总长度-数组子集左区间的长度大于当前步长，说明子集可以做归并操作
M = L + step -1;
} else {
M = N -1;
}
if(M == N -1){
break;
}
int R = 0;
if( N - 1 - M >= step){ //数组子集的右半区间的长度是否满足一个步长
R = M + step;
} else {
R = N -1;
}
merge(arr,L,M,R);
if( R == N -1){
break;
}else{
L = R + 1;
}
}
/*
步长大于数组的一半，说明该数组必然能整体被切分为左半数组和右半数组，那就能整体完成一次归并排序
*/
if( step > N/2 ){
break;
}
step *= 2;
}
}
简化版本：
- 设整体数组的长度为N，step是步长
- 最后一个分区数组的L和整体数组的N-1之间的长度是否满足大于一个步长，可以做合并排序
- 根据$N-1-L+1=N-L<=step$,判断不能满足归并条件
- 满足$N-L > step$，则$M=L + step -1$,R判断是否越界，取$step, N - M - 1$,这两个数的最小值+M
- 对步长进行循环，step=step*2,直到step>length>>1,表明当前的步长正好能将该数组分为左右两区间
//这个函数是用来归并数组某个范围上的排序
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 mergeSort3(int[] arr){
if(arr == null || arr.length < 2){
return;
}
int N =arr.length;
int step = 1;
while(step < N){
int L = 0;
while(L < N){
if(step >= N - L){
break;
}
int M = L + step -1;
int R = Math.min(step,N-M-1) + M;
merge(arr,L,M,R);
L = R +1;
}
if( step > N/2){
break;
}
step <<= 1;
}
}
归并排序相关算法题
数组小和
定义：在一个数组中，一个数左边比它小的数的总和，叫数的小和，所有数的小和累加起来，叫数组小和，求数组小和
思路：
- 两层for循环，求数组中每个数的最小和，然后累加
- 归并排序，这个数组的最小和必然是左边一半数组的最小和+右边一半数组的最小和+左边每个数子满足小于右边每个数子的条件的最小和。
- 可以参考归并排序，让左右两边数组都有序，然后设左边数组下标为p1，右边数组下标为p2，对$arr[p1]$和$arr[p2]$进行判断，满足$arr[p1] < arr[p2]$条件的，取$res = arr[p1] * {右边元素的个数}$，然后比较完，得出归并情况下的res
- 然后不断递归，得到最终解
public int smallSum(int[] arr){
if(arr == null || arr.length < 2){
return 0;
}
}
public int process(int[] arr,int l,int r){
if( l == r ){
return 0;
}
int mid = l + ((r - l)>>2); //防止溢出
return process(arr,l,mid) + process(arr,mid+1,r) + merge(arr,l,mid,r);
}
public int merge(int[] arr,int l,int m,int r){
int help[] = new int[r - l + 1];//辅助数组，长度是l~r之间的元素，包含l，因此加1
int p1 = l;
int p2 = m+1;
int i = 0;
int ans = 0;
while( p1 <= m && p2 <= r){
ans += arr[p1] < arr[p2]? arr[p1] * (r-p2+1):0;
help[i++] = arr[p1] < arr[p2] ? arr[p1++]:arr[p2++];//arr[p1] == arr[p2]时，需要移动p2的游标，因为arr[p1]可能满足arr[p1] < arr[j](j > 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];
}
return ans;
}
逆序对的个数
定义：设有一个序列{a_1, a_2, a_3,...a_{n-1}, a_n},对于序列中任意两个元素$ai,aj$，若$i<j$,$ai>aj$，则说明$ai$和$aj$是一对逆序对。
思路：
1. 两层for循环统计个数
1. 用归并排序的思想，统计左半数组的逆序对的个数和右半数组的逆序对个数，同时统计左半数组和右半数组对应的逆序对个数
public int reversePairNumber(int[] arr){
if(arr == null || arr.length < 2){
return 0;
}
return process(arr,0,arrlength-1);
}
public int process(int[] arr,int l,int r){
if(l == r){
return 0;
}
int mid = l + ((r - l) >> 1);
return process(arr,l,mid) + process(arr,mid + 1,r) + merge(arr,l,mid,r);
}
public int merge(int[] arr,int l,int m,int r){
int[] help = new int[r - l + 1];
//因为求的是ai > aj的关系，所以直接从数组最后开始遍历
int p1 = m;
int p2 = r;
int i = help.length - 1;
int res = 0;
while(p1 >= l && p2 >= m + 1){
res += arr[p1] > arr[p2] ? (p2 - m):0;//求的是p2到m+1之间的个数，m+1也算，所以是p2-m
help[i--] = arr[p1] > arr[p2] ? arr[p1--] : arr[p2--];
}
while(p1 >= 1){
help[i--] = arr[p1--];
}
while(p2 >= m + 1){
help[i--] = arr[p2--];
}
for(i = 0;i < help.length;i++){
arr[l + i] = help[i];
}
return res;
}
翻转对
题目：给定一个数组 nums ，如果 i < j 且 nums[i] > 2*nums[j] 我们就将 (i, j) 称作一个重要翻转对。你需要返回给定数组中的重要翻转对的数量。
思路：通过$i<j,nums[i]>2*nums[j]$,可以推测使用归并的思路，比较数组左右两侧有序情况下的$a[i]$和$a[j]$的大小，
- 设定一个参数$windowR=m+1,p_1=l,p_2=m+1$,$windowR$是开区间的边界表明$[m+1,windowR)$上的元素满足$arr[p1] > 2*arr[p2]$
- 对$p_1$进行$l-m$的遍历，满足$arr[p1] > 2*arr[p2] => windowR++$
- 可以求得每个p1的翻转队，$ans = windowR - m - 1$
- 最后归并排序
public int reversePairs(int[] arrs){
if(arrs == null && arrs.length < 2){
return 0;
}
return process(arrs,0,arrs.length-1);
}
public int process(int[] arrs,int l,int r){
if(l == r){
return 0;
}
int mid = l + ((r-l) >> 1);
return process(arrs,l,mid) + process(arrs,mid + 1,r) + merge(arrs,l,mid,r);
}
public int merge(int[] arrs,int l,int m,int r){
int p1 = l;
int p2 = m+1;
int windowR = m+1;
int ans = 0;
while(p1 <= m){
while(windowR <= r && (long)arrs[p1] > (long)2 * arrs[windowR]){
windowR++;
}
ans += windowR - m - 1;
p1++;
}
int[] helpArr = new int[r-l+1];
int i = 0;
p1 = l;
p2 = m+1;
while(p1 <= m && p2 <= r){
helpArr[i++] = arrs[p1] <= arrs[p2] ? arrs[p1++] : arrs[p2++];
}
while(p1 <= m){
helpArr[i++] = arrs[p1++];
}
while(p2 <= r){
helpArr[i++] = arrs[p2++];
}
for(i = 0;i < helpArr.length;i++){
arrs[l + i] = helpArr[i];
}
return ans;
}
区间和的个数
题目：给你一个整数数组 nums 以及两个整数 lower 和 upper 。求数组中，值位于范围 [lower, upper] （包含 lower 和 upper）之内的 区间和的个数 。区间和 S(i, j) 表示在 nums 中，位置从 i 到 j 的元素之和，包含 i 和 j (i ≤ j)
输入：nums = [-2,5,-1], lower = -2, upper = 2 输出：3 解释：存在三个区间：[0,0]、[2,2] 和 [0,2] ，对应的区间和分别是：-2 、-1 、2 。
来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/count-of-range-sum 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路：
- 前缀和preSum表示的是数组对应位置的和,$nums = [-2,5,-1] => preSum = [-2,3,2]$
- 根据前缀和$a[j] - a[i] in [lower,upper]$,可以知道 位置从 i 到 j 的元素之和 在 [lower, upper]。
- 把满足$a[j] - a[i] in [lower,upper]$的个数统计出来
- 用归并的思路，对preSum左右分组，左边有序和右边有序的情况下，计算右边元素减去左边元素满足[lower, upper]的情况个数
- 对右边元素循环，$a[j] - a[i] <= upper、a[j] - a[i] >= lower =》 a[i] <= a[j] - lower,a[i] >= a[j] - upper$，根据这个关系可以知道右边元素满足$min = a[j] - upper$和$max = a[j] - lower$，这两个值之间的元素
- 因为$a[i]和a[j]$都满足单调递增，所以可以假设参数windowL,windowR分别满足$windowL<min和windowR>= max$,$res = windowR-windowL$即是满足$j$作为边界的满足$i-j$之间的元素之和
public int countRangeSun(int[] nums,int lower,int upper){
if(nums == null && nums.length == 0){
return 0;
}
long[] preSum = new long[nums.length];
preSum[0] = nums[0];
for(int i = 1;i < preSum.length;i++){
preSum[i] = preSum[i - 1] + nums[i];
}
}
public int process(long[] preSum,int l ,int r,int lower,int upper){
if(l == r){
return preSum[l] >= lower && preSum[l] <= upper ? 1 : 0;
}
int mid = l + ((r-l) >> 1);
return process(preSum,l,mid,lower,upper) + process(preSum,mid+1,r,lower,upper) + merge(preSum,l,mid,r,lower,upper);
}
public int merge(long[] preSum,int l,int m,int r,int lower,int upper){
int windowL = l;
int windowR = l;
int ans = 0;
for(int i = m+1;i<= r;i++){
long min = preSum[i] - upper;
long max = preSum[i] - lower;
while(windowR <= m && preSum[windowR] <= max){
windowR++;
}
while(windowL <= m && preSum[windowL] < min){
windowL++;
}
ans += windowR - windowL;
}
long[] helpArr = new long[r-l+1];
int i = 0;
p1 = l;
p2 = m+1;
while(p1 <= m && p2 <= r){
helpArr[i++] = arrs[p1] <= arrs[p2] ? arrs[p1++] : arrs[p2++];
}
while(p1 <= m){
helpArr[i++] = arrs[p1++];
}
while(p2 <= r){
helpArr[i++] = arrs[p2++];
}
for(i = 0;i < helpArr.length;i++){
arrs[l + i] = helpArr[i];
}
return ans;
}
快速排序
递归版本
-
思路：
- 快速排序(Quick Sort)的基本思想是：通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录做排序，以达到整个序列有序的目的。
- 挑选一个数作为分区数，以arr[r]为例,假设小于$arr[r]$的区域为lessR，初始下标是$l-1$
- $arr[i] <= arr[r]$,则将i和lessR+1的数组交换，然后lessR++
- arr[i] >arr[r],则略过,i++
- i碰到r前一个下标，停止循环，把r和lessR+1的下标元素交换，必然能做到$ <=arr[r] arr[r] >=arr[r]$
/**
交换数组的两个游标位置上的数
*/
public static void swap(int[] arr,int i,int j){
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
public static int partition(int[] arr,int L,int R){
if(L > R){
return -1;
}
if(L == R){
return L;
}
int lessEqual = L -1;
int index = L;
while(index < R){
if(arr[index] <= arr[R]){
swap(arr,index,++lessEqual);
}
index++;
}
swap(arr,++lessEqual,R);
return lessEqual;
}
public static void quickSort1(int[] arr){
if(arr == null || arr.length < 2){
return;
}
process1(arr,0,arr.length - 1);
}
public static void process1(int[] arr,int L,int R){
if(L >= R){
return;
}
int m= partition(arr,L,R);
process1(arr,L,m - 1);
process(arr,m + 1,R);
}
/**
partition:选取右游标为关键字，然后想办法把它放到一个位置，使得它左边的值都比他小，右边的值都比他大，我们将这样的关键字称为枢纽(pivot)
思路：
1.设立一个游标，index，从L开始
2.设立一个左区域，游标是lessR,初始值是L-1,凡是arr[index] < arr[R],则将lessR+1和index上的元素互换，之后，index++,lessR++
3.设立一个右区域，游标是moreR,初始值是R，凡是arr[index] > arr[R],则将moreR--,然后将moreR和index上的元素互换
4.index撞到了右区域，将lessR++和R互换位置
*/
public static int[] netherlandsFlag(int[] arr, int L, int R) {
if (L > R) { // L...R 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, less + 1, index);
// less++;
// index++;
swap(arr, index++, ++less);
} else { // >
swap(arr, index, --more);
}
}
swap(arr, more, R); // <[R] =[R] >[R]
return new int[] { less + 1, more };
}
public static void quickSort3(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
process3(arr, 0, arr.length - 1);
}
public static void process3(int[] arr, int L, int R) {
if (L >= R) {
return;
}
swap(arr, L + (int) (Math.random() * (R - L + 1)), R);//随机变换r上的数,Math.random是[0,1)，左闭右开，因此要+1
int[] equalArea = netherlandsFlag(arr, L, R);
process3(arr, L, equalArea[0] - 1);
process3(arr, equalArea[1] + 1, R);
}
非递归版本
思路：借助Stack结构，模仿递归的运行过程，每次运行结束后，将返回的pivio范围t继续压倒下个栈中，直到pivot撞到数组左边界，或者右边界，队列同理
public class Job{
public int L;
public int R;
public Job(int left,int right){
this.L = left;
this.R = right;
}
}
public static void quickSortByStack(int[] arr){
if(arr == null || arr.length < 2 ){
return;
}
int N = arr.length;
swap(arr, (int) (Math.random() * N), N - 1);
int[] equalArea = netherlandsFlag(arr, 0, N - 1);
int el = equalArea[0];
int er = equalArea[1];
Stack<Op> stack = new Stack<>();
stack.push(new Op(0, el - 1));
stack.push(new Op(er + 1, N - 1));
while (!stack.isEmpty()) {
Op op = stack.pop(); // op.l ... op.r
if (op.l < op.r) {
swap(arr, op.l + (int) (Math.random() * (op.r - op.l + 1)), op.r);
equalArea = netherlandsFlag(arr, op.l, op.r);
el = equalArea[0];
er = equalArea[1];
stack.push(new Op(op.l, el - 1));
stack.push(new Op(er + 1, op.r));
}
}
}
// 快排3.0 非递归版本 用队列来执行
public static void quickSortByQueue(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
int N = arr.length;
swap(arr, (int) (Math.random() * N), N - 1);
int[] equalArea = netherlandsFlag(arr, 0, N - 1);
int el = equalArea[0];
int er = equalArea[1];
Queue<Op> queue = new LinkedList<>();
queue.offer(new Op(0, el - 1));
queue.offer(new Op(er + 1, N - 1));
while (!queue.isEmpty()) {
Op op = queue.poll();
if (op.l < op.r) {
swap(arr, op.l + (int) (Math.random() * (op.r - op.l + 1)), op.r);
equalArea = netherlandsFlag(arr, op.l, op.r);
el = equalArea[0];
er = equalArea[1];
queue.offer(new Op(op.l, el - 1));
queue.offer(new Op(er + 1, op.r));
}
}
}
堆排序
定义：将待排序的数组构造成一个大顶堆。此时，整个数组的最大值就是堆顶的根结点。将根节点和末尾元素互换，然后将$n-1$个元素重新构造成一个堆，这样就会得到$n$个元素中的次大值。反复执行，便能得到一个有序数组了。
public void heapSort(int[] arr){
if(arr == null || arr.length < 2){
return;
}
/*
for(int i = 0;i < arr.length;i++){
heapInsert(arr,i);
}
*/
for(int i = arr.length-1;i>=0;i++){
heapify(arr,i,arr.length);
}
int heapSize = arr.length;
swap(arr,0,--heapSize);
while(heapSize > 0){
heapify(arr,0,heapSize);
swap(arr,0,--heapSize);
}
}
private void heapify(int[] arr,int index , int heapSize){
int left = index * 2 +1;
while(left < heapSize){
int largest = left+1 < heapSize && arr[left+1] > arr[left] ? left + 1 : left;
largest = arr[largest] > arr[index] ? largest : index;
if(largest == index){
break;
}
swap(arr,largest,index);
index = largest;
left = index * 2+1;
}
}
private void heapInsert(int[] arr,int index){
while(arr[index] > arr[(index-1)/2]){
swap(arr,index,(index-1)/2);
index = (index-1)/2;
}
}
private void swap(int[] arr,int i,int j){
int tmp = arr[i];
int arr[i] = arr[j];
int arr[j] = tmp;
}
计数排序
定义：计数排序是一个非基于比较的[排序算法]。计数排序的基本思想是对于给定的输入序列中的每一个元素x，确定该序列中值小于x的元素的个数（此处并非比较各元素的大小，而是通过对元素值的计数和计数值的累加来确定）。一旦有了这个信息，就可以将x直接存放到最终的输出序列的正确位置上。
思路：
1.设定一个变量max，存储数组中的最大值，然后创建数组长度为max+1的数组arr
2.对数组遍历，对应的数值再数组arr中+1=>$arr[i]++$
3.根据数组$arr$遍历，根据$arr[i]$的值，填充原始数组，然后返回
public class Code03_CountSort {
public static void countSort(int[] arr){
if(arr == null || arr.length<2){
return;
}
int max = Integer.MIN_VALUE;
for(int i = 0;i < arr.length;i++){
max = Math.max(arr[i],max);
}
int[] help = new int[max+1];
for(int i = 0;i<help.length;i++){
help[arr[i]]++;
}
int i = 0;
for(int j = 0;j < help.length;j++){
while(help[j]-- > 0){
arr[i++] = j;
}
}
}
public static void comparator(int[] arr){
Arrays.sort(arr);
}
public static int[] generateRandomArr(int maxSize,int maxVal){
int[] arr = new int[(int)(Math.random()*maxSize+1)];
for(int i = 0;i < arr.length;i++){
arr[i] =(int)(Math.random()*maxVal+1);
}
return arr
}
public static int[] dpCopyArr(int[] arr){
if(arr == null){
return null;
}
int[] res = new int[arr.length];
for(int i = 0;i<arr.length;i++){
res[i] = arr[i];
}
return res;
}
public static boolean isEqual(int[] arr1,int[] arr2){
if((arr1 ==null && arr2!=null)||(arr1 != null && arr2 == null)){
return false;
}
if((arr1 == null && arr2 == null)||( arr1 == arr2)){
return true;
}
if(arr1.length != arr2.length){
return false;
}
for(int i = 0 ; i < arr.length;i++){
if(arr1[i] != arr2[i]){
return false;
}
}
return true;
}
public static void printArr(int[] arr) {
if (arr == null) {
return;
}
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
public static void main(String[] args) {
int testTime = 500000;
int maxSize = 100;
int maxValue = 300;
boolean success = true;
for (int i = 0; i < testTime; i++) {
int[] arr1 = generateRandomArray(maxSize, maxValue);
int[] arr2 = copyArr(arr1);
countSort(arr1);
comparator(arr2);
if (!isEqual(arr1, arr2)) {
success = false;
printArr(arr1);
printArr(arr2);
break;
}
}
System.out.println(success ? "没有问题" : "有问题");
}
}
基数排序
定义：基数排序（radix sort）属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或bin sort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序，
思路：
- 从左至右扫描数组，对数组的个位数做从1到9的归类，然后先进先出这些数组中的数字（做到相对有序）
- 重复上述操作，直到当前数组中最大数字的最大位数
- 可以不用队列或栈完成上述排序
- 首先设定一个参数$help[]$，用来记录当前数组归类后，从1到9每个桶的前缀和
- 根据前缀和，从右到左扫描，满足哪个桶就再当前数组的help[i]位置加上，然后help[i]--
- 例子：76，34，72，35，65，36，22，21
- 第一步，分类，$[1,2,0,1,2,2,0,0,0]$
- 第二步，前缀和:$[1,3,3,4,6,8,8,8,8]$
- 第三步：根据前缀和从右到左排列（因为当前数组$arr[i]$局部有序，需要从右到左，保证最大的再正确的位置）
- 数组变成：21，22，72，34，35，65，76，36
public class Code04_RadixSort {
public static void radixSort(int[] arr){
if(arr == null || arr.length < 2){
return;
}
radixSort(arr,0,arr.length-1,maxbits(arr));
}
//求当前数组中的最大值
//1.循环，得到当前数组中的max
//2.对max求出它的最高位
public static int maxbits(int[] arr){
int max = Integer.MIN_VALUE;
for(int i = 0;i<arr.length;i++){
max = Math.max(max,arr[i]);
}
int res = 0;
while(max != 0){
res++;
max / = 10;
}
return res;
}
//求出当前x位上的值
public static int getDigit(int x, int d){
return ((x/(int) Math.pow(10,d-1)))%10;
}
public static void radixSort(int[] arr, int L, int R, int digits){
final int radix = 0;
int i = 0,j = 0;
int[] help = new int[R - L + 1];
for( int d = 1;d < digits; d++){
int[] count = new int[radix];
for (i = L; i <= R; i++) {
j = getDigit(arr[i], d);
count[j]++;
}
for (i = 1; i < radix; i++) {
count[i] = count[i] + count[i - 1];
}
for (i = R; i >= L; i--) {
j = getDigit(arr[i], d);
help[count[j] - 1] = arr[i];
count[j]--;
}
for (i = L, j = 0; i <= R; i++, j++) {
arr[i] = help[j];
}
}
}
public static void comparator(int[] arr){
Arrays.sort(arr);
}
public static int[] generateRandomArr(int maxSize,int maxVal){
int[] arr = new int[(int)(Math.random()*maxSize+1)];
for(int i = 0;i < arr.length;i++){
arr[i] =(int)(Math.random()*maxVal+1);
}
return arr
}
public static int[] dpCopyArr(int[] arr){
if(arr == null){
return null;
}
int[] res = new int[arr.length];
for(int i = 0;i<arr.length;i++){
res[i] = arr[i];
}
return res;
}
public static boolean isEqual(int[] arr1,int[] arr2){
if((arr1 ==null && arr2!=null)||(arr1 != null && arr2 == null)){
return false;
}
if((arr1 == null && arr2 == null)||( arr1 == arr2)){
return true;
}
if(arr1.length != arr2.length){
return false;
}
for(int i = 0 ; i < arr.length;i++){
if(arr1[i] != arr2[i]){
return false;
}
}
return true;
}
public static void printArr(int[] arr) {
if (arr == null) {
return;
}
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
public static void main(String[] args) {
int testTimes = 5000;
int len = 10;
int maxValue = 100;
boolean succeed = true;
for (int i = 0; i < testTimes; i++) {
int[] arr1 = generateRandomArr(len, maxValue);
int[] arr2 = copyArr(arr1);
radixSort(arr1);
comparator(arr2);
if (!isEqual(arr1, arr2)) {
succeed = false;
printArray(arr1);
printArray(arr2);
break;
}
}
System.out.println(succeed ? "没有问题" : "有问题");
}
}