选择、插入、归并、快排、对数器
1、异或
异或运算，相同为0，不同为1
同或运算，相同为1，不同为0
异或可以记忆为无进位相加
::交换两个值::
a=ab
b=ab
// b=a b b b=a
a=ab
// a= a b ^ a a=b
怎么把一个int类型的数，提取出最右侧的1来?
N&( ~N+1)
一个数组中有两种数出现了奇数次，其他数都出现了偶数次，怎么找到并打印这两种数?
eor = a^b != 0
假设其中有 eor 的二进制第8位的数为1
按照这个标准将数组分为两类
第八位有1的，和第二位没有1的
然后分别 异或
得出 a、b
可以找最右侧的那位1
int c=16; //1000
System.out.println(c&(~c+1)); // 16
时间复杂度分析
a 为调用次数，b为调用规模， N/b
2、归并排序
时间复杂度O(N logN), 额外空间复杂度 O（N） ,稳定的排序
递归版本：
准备一个辅助数组，然后把原数组的数据放入辅助数组中，最后赋值回去
左半边归并，右半边归并，整体再归并
1 1 4 | 2 4 5
两个指针分别指向第一个元素
1 1 2 4 4 5
遇到相同元素，左边先进去，右边后进去
public class MergeSort {
public static void mergeSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
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 left, int mid, int right) {
int[] res = new int[right - left + 1];
int i = 0;
//双指针
int p1 = left, p2 = mid + 1;
while (p1 <= mid && p2 <= right) {
res[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
}
while (p1 <= mid) {
res[i++] = arr[p1++];
}
while (p2 <= right) {
res[i++] = arr[p2++];
}
for (int j = 0; j < res.length; j++) {
arr[left + j] = res[j];
}
}
public static void main(String[] args) {
…………
mergeSort(arr1);
…………
}
}
非递归：
先两个数排好，然后再4个数排好，进而8个数排好。。 。。
public static void mergeSort2(int [] arr){
if(arr == nulll || arr.length<2){
return ;
}
int N= arr.length;
while(mergeSize <N){
int L=0;
while(L<M){
int M =L+mergeSize -1;
if(M>=N){
break;
}
int R= Math.min(M+mergeSize, N-1);
merge(arr,L,M,R);
L=R+1;
}
//防止溢出
if(mergeSize > N/2){
break;
}
mergeSize << = 1;
}
}
2.1小和数
在一个数组中，每一个元素左边比当前元素值小的元素值累加起来，叫做这个数组的小和
[1,3,4,2,5]
1左边比1小的数，没有；
3左边比3小的数，1；
4左边比4小的数，1、3；
2左边比2小的数，1；
5左边比5小的数，1、3、4、2；
所以小和为1+1+3+1+1+3+4+2=16
求问左边元素有几个比自己小，即求右边元素有几个比自己大
利用归并过程中会将数字变得有序的特点来计算
1 3 4 2 5 划分为两组
1 3 为一组 4 2 5 为一组
1 3 进行merge操作
1和3 对比，1小，且右边数组中只有一个比1大，res+=1*1
前面这组比较完成
4 2 5 拆为 4 ， 2 5 这两组
左边从4只有一个元素，也就没有小和
右边2 5 进行merger 操作， res +=2*1
merger操作后，将 4 2 5 这三个数放回辅助数组，2 4 5
现在数组为 1 3 2 4 5
左边从1 开始遍历，发现右边第一个数 3 比 1大，则从下标得出有3个数比1大，即使 res+=3*1
然后1进入辅助数组，左边指针往后，指向3，3>2，不产生小和，2进入辅助数组，右边指针往后
3 和4 对比 ，有2个数比3大，则res+=2*3
4和5对比，有1个数比4大，则res+=1*4
最后res=16
public static int smallSum(int[] arr){
if (arr == null || arr.length < 2){
return 0;
}
return mergeSort(arr,0, arr.length-1);
}
public static int mergeSort(int[] arr, int left, int right){
if(left == right){
return 0;
}
int mid = left + ((right - left) >> 1);
return mergeSort(arr, left, mid) + mergeSort(arr, mid+1, right) + merge(arr,left,mid,right);
}
public static int merge(int[] arr, int left, int middle, int right){
int[] help = new int[right - left + 1];
int i = 0;
int p1 = left, p2 = middle + 1;
int res = 0;
while (p1 <= middle && p2 <= right){
res += arr[p1] < arr[p2] ? (right-p2+1) * arr[p1] : 0;
help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
}
while (p1 <= middle){
help[i++] = arr[p1++];
}
while (p2 <= right){
help[i++] = arr[p2++];
}
for (i = 0; i < help.length; i++) {
arr[left+i] = help[i];
}
return res;
}
3、快排
时间复杂度O(Nlog N), 额外空间复杂度 O(Nlog N） 不稳定的排序
问题1
给定一个数组arr，和一个数num，请把小于等于num的数放在数组的左边，大于num的数放在数组的右边。要求额外空间复杂度O(1)，时间复杂度O(N)。
方法：
-
用x标记小于区域的最后一个数的位置，然后用for循环依次遍历数组中的数，如果大于指定数字则跳过，不进行交换；如果小于或等于num，则与x的下一个位置进行交换。
-
如果第一个位置的数小于等于num，其实就是和自己交换，i一定永远大于等于x。
public static void main(String[] args) {
int[] arr = new int[]{3,1,2,5,5,2,6,7,4};
int num = 4;
int x = -1;
for (int i = 0; i < arr.length; i++){
if(arr[i]<=num){
swap(arr,i,++x);
}
}
System.out.println( Arrays.toString(arr));
}
荷兰国旗问题
https://leetcode-cn.com/problems/sort-colors/
class Solution {
public void sortColors(int[] nums) {
int less=-1;
int more=nums.length;
int i=0;
// 指针遇到大于区指针前一个位置，停止循环
while(i<more){
// 当前数字大于给定数字， 数字与大于区的下一个进行交换
if(nums[i]>1){
swap(nums,i,--more);
//当前数字小于给定数字， 数字与小于区的下一个进行交换
}else if(nums[i]<1){
swap(nums,i,++less);
i++;
}else{
// 当前数等于给定数字，指针后移
i++;
}
}
}
void swap(int [] nums,int a,int b){
if(a==b){
return;
}
nums[a]=nums[a]^nums[b];
nums[b]=nums[a]^nums[b];
nums[a]=nums[a]^nums[b];
}
}
经典快排
- 经典快排
经典快排一次只搞定一个数，每次将初始的右侧数作为基准放在中间，<=的放左边，>的放右边；这样会导致左边会包含等于基准值的若干个数。接着返回基准值的左边部分和右边部分，再对左右部分进行上述操作，最终对数组完成排序。经典快排可能导致子区域划分极不平均。
当数据为{1,2，3, 4，5}时，每次将最后一个数作为基准，所需时间复杂度：O（N*N） - 改进后的经典快排(重要)
改进后的快排一次搞定一部分数（=x的那部分），总体来说，经典快排每次递归调用只有一个数不动，其他的需要进行二次甚至多次递归；而改进后的则是=x的一部分数全都不动，只需递归<或者>x的数即可。
为了避免经典快排可能导致子区域划分极不平均，改进后的快排则是随机抽取数组中的一个数作为基准值对数组进行排序。
时间复杂度O(N*logN)，空间复杂度O(logN);
tips: 如何绕开本身的数据状况?
用随机打乱数据
使用哈希函数
public class QuickSort {
public static void quickSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
quickSort(arr, 0, arr.length - 1);
}
public static void quickSort(int[] arr, int L, int R) {
if (L < R) {
//先随机取出一个数放到最后
swap(arr, L + (int) (Math.random() * (R - L + 1)), R);
int[] p = partition(arr, L, R);
quickSort(arr, L, p[0] - 1);
quickSort(arr, p[1] + 1, R);
}
}
public static int[] partition(int[] arr, int l, int r) {
int less = l - 1;
int more = r;
while (l < more) {
if (arr[l] < arr[r]) {
swap(arr, ++less, l++);
} else if (arr[l] > arr[r]) {
swap(arr, --more, l);
} else {
l++;
}
}
swap(arr, more, r);
return new int[] { less + 1, more };
}
public static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
public static void main(String[] args) {
int[] arr = {3,4,5,6,1,2,3,4,5,4,3};
int num = 4;
printArray(arr);
quickSort(arr);
printArray(arr);
}
}
平均时间复杂度 N*log N
4.选择排序
时间复杂度O(N^2), 不稳定的排序
在0~N-1范围内找一个最小的值，放到0位置；
在1~N-1范围内找一个最小的值，放到1位置；
一直重复到结束；
（每次过一遍范围都找到最小的，然后放到范围内的首位置）
public static void selectionSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
for (int i = 0; i < arr.length - 1; i++) {//范围每次缩小1，从前往后缩。
int minIndex = i;//找范围内最小值，最开始默认是第一个
for (int j = i + 1; j < arr.length; j++) {
minIndex = arr[j] < arr[minIndex] ? j : minIndex;//是否比目前最小值还小，如果是，则交换，否则不交换；
}
swap(arr, i, minIndex);//将最小值放到范围的第一个数
}
}
public static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
5. 插入排序：
时间复杂度O(N^2),稳定的排序
（扑克牌插牌原理）
先将手里的牌排好序，然后拿新的牌跟排好序最后面的开始比较，比 排好序的牌 小就交换到前面去，一直到比 比较的牌 大，就不用动了。
每次排好一张牌，最后都有序。
插入排序代码：
public static void insertionSort(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);
}
}
}
public static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
6. 对数器
使用对数器，具体步骤：
1）有一个你想要测的方法a
2）实现一个绝对正确但是复杂度不好的方法b
3） 实现一个随机样本产生器
4）实现比对的方法
5）把方法a和方法b比对很多次来验证方法a是否正确。
6）如果有一个样本使得比对出错，打印样本分析是哪个方法出 错
7）当样本数量很多时比对测试依然正确，可以确定方法a已经 正确。
好处：
验证方法对不对
可以很快找到错误case（几千几万case中）
判断贪心对不对
具体实现（例如测试冒泡排序方法是否正确）：
想要测试冒泡排序方法a（判断该方法是否正确）：
public static void bubbleSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
for (int e = arr.length - 1; e > 0; e--) {//范围每次缩减1，因为每次都排好了一个数
for (int i = 0; i < e; i++) {//从头到e进行两两比较
if (arr[i] > arr[i + 1]) {
swap(arr, i, i + 1);//（前面比后面大就进行交换）
}
}
}
}
public static void swap(int[] arr, int i, int j) {//两两交换
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
1）产生一个长度随机的数组（可能为正，也可能为负，0）
随机样本产生器：
public static int[] generateRandomArray(int maxSize, int maxValue) {
int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
for (int i = 0; i < arr.length; i++) {
arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
}
return arr;
}
2）绝对正确的方法
调用函数自带的排序方法（实现一个绝对正确但是复杂度不好的方法b，用于和冒泡排序测试方法比较，判断测试方法是否正确）
public static void comparator(int[] arr) {
Arrays.sort(arr);
}
3）大样本测试
public static void main(String[] args) {
int testTime = 500000;//测试次数
int maxSize = 100;
int maxValue = 100;
boolean succeed = true;
for (int i = 0; i < testTime; i++) {
int[] arr1 = generateRandomArray(maxSize, maxValue);//产生随机数组
int[] arr2 = copyArray(arr1);
bubbleSort(arr1);//测试的方法
comparator(arr2);//绝对正确的方法
if (!isEqual(arr1, arr2)) {
succeed = false;
break;
}
}
System.out.println(succeed ? "Nice!" : "Fucking fucked!");
}
public static boolean isEqual(int[] arr1, int[] arr2) {//实现比对的方法 ，比较两个数组的每个数是否相等
if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
return false;
}
if (arr1 == null && arr2 == null) {
return true;
}
if (arr1.length != arr2.length) {
return false;
}
for (int i = 0; i < arr1.length; i++) {
if (arr1[i] != arr2[i]) {
return false;
}
}
return true;
}
修订记录
2022-04-23 14:04:24 荷兰国旗问题