排序算法笔记详解（上）

算法笔记详解（上）"/>

排序算法笔记详解（上）

1、冒泡排序

package com.Mr.ZuoChengYun.sort;/*** @author pshdhx* @date 2022-02-11 11:21* @Des 冒泡排序-左程云算法学习笔记*/
public class BubbleSort {public static void bubbleSort(int[] arr){if(arr == null || arr.length < 2){return ;}for(int e=arr.length-1;e>0;e--){ // 0 ~ e范围上for(int i=0;i<e;i++){if(arr[i] > arr[i+1]){ //因为上边是e-1，所有此处i+1不用担心溢出的问题。swap(arr,i,i+1);}}}}/*** 异或运算还可以理解为无进位相加* 性质：*  0^N = N; N^N=0;*  满足交换律和结合律 a^b = b^a  (a^b)^c = a^(b^c)*  推出性质3*  a=甲 b=乙：*  a = a ^ b*  b = a ^ b*  a = a ^ b*  好处：少了一个空间的占用*  从第二行，用第一行结论： b= (a^b)^b ==> a^0=a  所以b就变为了a；*  从第三行，用第一行，第二行结论： a= (a^b) ^ a ==> b^0=b  所以a就变成了b；*  前提：a和b在内存中是一块独立的区域，他俩的值可以一样，但必须内存不一样。*///异或运算：相同为0，不同为1；public static void swap(int[] arr,int i,int j){arr[i] = arr[i] ^ arr[j];arr[j] = arr[i] ^ arr[j];arr[i] = arr[i] ^ arr[j];}/*** 面试题整理2*/public static void printOddTime2(int[] arr){int eor = 0;for(int i=0;i<arr.length;i++){eor^=arr[i];}int rightOne = eor & (~eor +1); //提出最右边的1int onlyOne = 0;for(int cur: arr){if((cur & rightOne) == 0){  //if((cur & rightOne) == 1){ //也行onlyOne ^= cur;}}System.out.println(onlyOne+" "+(eor^onlyOne));}}
//面试题【在一个整型数组中，1个数字出现了奇数次，其他所有数字出现了偶数次，怎么找到出现了奇数次的数】从左到右异或即可。o(n) o(1)
//面试题【在一个整型数组中，2个数字出现了奇数次，其他所有数字出现了偶数次，怎么找到出现了奇数次的数】
//  eor=a^b 肯定!=0（假设第八位是1，a和b的第八位肯定不同，一个为1，一个为0）
//  (数字1是第八位为1异或的最终结果)eor'=a or b
//  （数字2）eor^eor' ====> a^b ^(a or b)/*** 冒泡排序算法是稳定的算法：每次比较，每次交换，大数后移，每一轮都能找到一个最大的数字放到最后；*/
/*** 冒泡排序与选择排序最大的不同：冒泡排序是每次比较后交换；选择排序是一轮找到最小值下标后交换。*/

2、选择排序

package com.Mr.ZuoChengYun.sort;/*** @author pshdhx* @date 2022-02-11 11:20* @Des 选择排序-左程云算法学习笔记*/
public class SelectSort {public static void selectSort(int[] arr){if(arr == null || arr.length < 2){return;}for(int i=0;i<arr.length;i++){  // i~N-1int minIndex = i;for(int j=i+1;j<arr.length;j++){    //i ~ N-1上找到最小值的下标minIndex = arr[minIndex] < arr[j] ? minIndex : j;}swap(arr,i,minIndex); //找到了最小的数字之后，就根据下标交换数值}}public static void swap(int[] arr,int i,int j){int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}
}/*** 疑问：该排序稳定吗？怎么判断的* minIndex = arr[minIndex] < arr[j] ? minIndex : j; 该种判断不稳定，如果相等了，minIndex就与j交换了位置；* minIndex = arr[minIndex] < = arr[j] ? minIndex : j; 那么此种方式呢？稳定吗？也不稳定；* 6、7、6、2、8，在对其进行第一遍循环的时候，会将第一个位置的6与后面的2进行交换。此时，就已经将两个6的相对前后位置改变了。因此选择排序不是稳定性排序算法。* 6、7、6、2、8，在对其进行第一遍循环的时候，会将第一个位置的6与第二个位置的6交换的话，这是不可能的；* 选择排序算法的核心是：每次排序都找出最小的数，让第一个数【最前边的数字】与其做交换，让最小的数字放到前边；*/

3、插入排序

package com.Mr.ZuoChengYun.sort;/*** @author pshdhx* @date 2022-02-11 14:15* @Des 左程云-插入排序的实现*/
public class InsertSort {public static void insertSort(int arr[]){if(arr == null || arr.length < 2){return;}for(int i=1;i<arr.length;i++){ //想要0~i范围内做到有序，直接从1开始就行，因为0位置上已经做到了有序System.out.println("i================="+i);for(int j=i-1;j>=0;j--){ //从后往前比较，然后交换。 j--无所谓了，毕竟不是--jSystem.out.println("j======="+j);if(arr[j]>arr[j+1]){  //不用担心j+1,因为j+1也不过=i而已，j到0就结束了。System.out.println(""+j+"和"+(j+1)+"交换");swap(arr,j,j+1);}}}}public static void swap(int[] arr,int i,int j){arr[i] = arr[i] ^ arr[j];arr[j] = arr[i] ^ arr[j];arr[i] = arr[i] ^ arr[j];}public static void testFor(){for(int j=5;j>=0;j--){  // 5 4 3 2 1 0System.out.println(j);}for(int j=5;j>=0;--j){  // 5 4 3 2 1 0====> j=0 j>=0 --j  输出0，此时j=-1，不继续走了!System.out.println(j);}for(int j=5;j>0;--j){  // 5 4 3 2 1 System.out.println(j);}}public static void main(String[] args) {
//        int arr[] =  new int[]{4,1,7,3,4,9,5};
//        insertSort(arr);
//        for(int i=0;i<arr.length;i++){
//            System.out.println(arr[i]);
//        }testFor();}
}
/*** 插入排序稳定；*/

4、二路归并排序

package com.Mr.ZuoChengYun.sort;/*** @author pshdhx* @date 2022-02-12 11:11* @Des 归并排序：准备一个辅助空间，谁小拷贝谁*/
public class MergeSort {public static void mergeSort(int[] arr){if(arr == null || arr.length < 2){return;}process(arr,0,arr.length-1);}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);  //左右两侧都有序了，需要一个merge的过程，再merge过程中就排好序了}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++];}//左侧剩下的拷贝到help中while(p1 <= M){help[i++] = arr[p1++];}//右侧剩下的拷贝到help中while(p2 <= R){help[i++] = arr[p2++];}for(i = 0;i<help.length;i++){arr[L + i] = help[i];}}
}

5、快速排序

package com.Mr.ZuoChengYun.sort;/*** @author pshdhx* @date 2022-02-15 8:53* @Des 快速排序* <p>* 给定一个数组arr，和一个数num，请把小于等于num的数字放到左边，大于num的数字放到右边，要求额外空间复杂度为o(1),时间复杂度为o(n)* 3 5 6 7 4 3 5 8 假设num为5* （1）<=num时，[i]和 <=区域的下一个数字做交换，<=区域往右扩大一位，i++* (2) >num时，i++即可* 1th:<=区域为3* 2th:<=区域为3 5* 3th:不变i++* 4th:不变i++* 5th:<=区域为3 5 4* 6th:<=区域为3 5 4 3* 7th:<=区域为3 5 4 3 5* 8th:不变 i++* <p>* 给定一个数组arr，和一个数num，请把小于num的数字放到左边，等于num的数字放到中间，大于num的数字放到右边，要求额外空间复杂度为o(1),时间复杂度为o(n)* 1):[i]<num时，[i]和 <区域的下一个数字做交换， <区域 右扩， i++* 2):[i]==num时，i++* 2):[i]>num时，[i]和 >区域的上一个数字做交换，>区域左扩 i不变【为啥原地不动来，因为这个数字是从>区域上新过来的，还没有比较过。】* <p>* 整体有序的时候，使用快速排序 o(n^2) 因为每次只搞定了一个数字放在了最右边。划分值打的很偏，产生了最坏的情况!*//*** 给定一个数组arr，和一个数num，请把小于等于num的数字放到左边，大于num的数字放到右边，要求额外空间复杂度为o(1),时间复杂度为o(n)*          3 5 6 7 4 3 5 8 假设num为5*          （1）<=num时，[i]和 <=区域的下一个数字做交换，<=区域往右扩大一位，i++*           (2) >num时，i++即可*         1th:<=区域为3*         2th:<=区域为3 5*         3th:不变i++*         4th:不变i++*         5th:<=区域为3 5 4*         6th:<=区域为3 5 4 3*         7th:<=区域为3 5 4 3 5*         8th:不变 i++** 给定一个数组arr，和一个数num，请把小于num的数字放到左边，等于num的数字放到中间，大于num的数字放到右边，要求额外空间复杂度为o(1),时间复杂度为o(n)*         1):[i]<num时，[i]和 <区域的下一个数字做交换， <区域 右扩， i++*         2):[i]==num时，i++*         2):[i]>num时，[i]和 >区域的上一个数字做交换，>区域左扩 i不变【为啥原地不动来，因为这个数字是从>区域上新过来的，还没有比较过。】*//*** 整体有序的时候，使用快速排序 o(n^2) 因为每次只搞定了一个数字放在了最右边。划分值打的很偏，产生了最坏的情况!*//*** 快排1.0: question1* 快排2.0: question2* 快排3.0: 随机选 o(N*logN) :因为随机这件事情，变成了概率事件。 空间复杂度是o(logN)级别的*/
public class QuickSort {public static void quickSort(int[] arr) {if (arr == null || arr.length < 2) {return;}quickSort(arr, 0, arr.length - 1);}//arr[l..r]排好序public static void quickSort(int[] arr, int L, int R) {if (L < R) {swap(arr, L + (int) (Math.random() * (R - L + 1)), R); //等概率随机选择一个位置，让它与最后一个位置做交换。System.out.println("(int) (Math.random() * (R - L + 1))======"+(int) (Math.random() * (R - L + 1)));int[] p = partition(arr, L, R); //划分值==区域的左边界和右边界quickSort(arr, L, p[0] - 1); // 小于区域上递归quickSort(arr, p[1] + 1, R); // 大于区域上递归}}//这是处理一个arr[1..r]的函数//默认以arr[r]做划分，arr[r]====p     <p      ==p         >p//返回等于区域（左边界，右边界），所以返回一个长度为2的数组res res[0] res[1]public static int[] partition(int[] arr, int L, int R) {int less = L - 1; //小于区域右边界，一开始就在最左边。数组位置左边的前一个位置。int more = R; //大于区域左边界，一开始就在最右边。数组位置右边的后一个位置。while (L < more) {  //L表示当前数字的位置 arr[R] -> 划分值if (arr[L] < arr[R]) { //当前数小于划分值swap(arr, ++less, L++);} else if (arr[L] > arr[R]) {swap(arr, --more, L);} else { //这是遍历的时候，等于标值的时候，L++L++;}}swap(arr, more, R);return new int[]{less + 1, more};}public static void swap(int arr[], int l, int r) {int temp = arr[l];arr[l] = arr[r];arr[r] = temp;}public static void main(String[] args) {int arr[] = new int[]{2,5,3,8,4,32,45,21,13,45};quickSort(arr,0,arr.length - 1);for(int i=0;i<arr.length;i++){System.out.print(arr[i]+"\t");}}
}

6、递归行为解析

package com.Mr.ZuoChengYun.sort;/*** @author pshdhx* @date 2022-02-12 9:56* @Des 左程云-递归排序*//*** 利用递归行为求arr上的最大值*/
public class RecuisionSort {public static int getMax(int[] arr){return process(arr,0,arr.length-1);}//arr[L...R]范围上求最大值public static int process(int[] arr,int L,int R){if(L ==R){System.out.println("直接返回了"+arr[L]);return arr[L];}int mid = L + ((R - L) >> 1);int leftMax = process(arr,L,mid);System.out.println("leftMax=="+leftMax);int rightMax = process(arr,mid+1,R);System.out.println("rightMax=="+rightMax);System.out.println("最大值为:"+Math.max(leftMax,rightMax));return Math.max(leftMax,rightMax);}public static void main(String[] args) {int arr[] = new int[]{2,65,7,3,56,43};int maxValue = getMax(arr);System.out.println("最大值为=====》:"+maxValue);}
}
/*** 递归分析* [3,2,,5,6,7,4]       *                      process(0,5)*          p(0,2)                          p(3,5)*      p(0,1)    p(2,2)              p(3,4)        p(5,5)*  p(0,0)  p(1,1)                  p(3,3) p(4,4)*  *  结果拆分成了：p(0,0) p(1,1) p(2,2) p(3,3) p(4,4) p(5,5)  然后从底下往上汇总，才知道了process(0,5)的最大值是什么*  递归过程就是：用系统栈把整个过程给压栈了。【悬而未决的东西就压栈，算完了就出栈，相当于利用栈玩了个后续遍历。】*/
/*** master公式：*  T(N)             =             a             *                   T(N/b)                      +   o(N^d)*  母问题的规模量是N           子问题调用次数                     子问题的都是N/b的规模的问题              除去子问题的调用之外，剩下的过程*                               2次                           子问题调用的时候规模等量，都是N/2          比大小 o(1)* master公式的时间复杂度计算： log2 2 > 0 所以process时间复杂度是 o(n^1) = o(n) ===>等于从左到右遍历求最大值，看上边注释的倒数第二行即可理解。* logbA < d  o(N^d)           * logbA > d  o(N^logbA)* logbA == d  o(N^d*logN)*/                                                             

7、求逆序对问题

package com.Mr.ZuoChengYun.sort;/*** @author pshdhx* @date 2022-02-14 16:00* @Des 逆序对问题*//***   逆序对问题：在一个数字中，左边的数字如果比右边的数字大，则两个数字构成一个逆序对，请打印所有的逆序对*   例如：3,2,4,5,0,6,1  【逆序对数量 （3,2） （3,0） （3,1）| （2,0） （2,1）| (4,0) (4,1) |(5,0) (5,1) (6,1)】  ---10个*  */
public class ReverseOrderPair {public static int ReverseOrderPair(int[] arr) {if (arr == null || arr.length < 2) {return 0;}return process(arr, 0, arr.length - 1);}//arr[l...r]既要排好序，也要求小和public static 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 static int 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; int count = 0;while (p1 <= m && p2 <= r) {
//            count += arr[p1] > arr[p2] ? 1 : 0; //右边是排好序的啊
//            help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
//            if(arr[p1] > arr[p2]){
//                System.out.println("arr[p1]="+arr[p1]+"-----------------"+"arr[p2=]"+arr[p2]);
//                count += m - i + 1;
//            }if(arr[p1] <= arr[p2]){help[i++]=arr[p1++];}else{help[i++]=arr[p2++];count += m - p1 + 1;	//a[p1]>a[p2]时，p1到m所有数都和a[p2]形成逆序对  p1~m的的所有的数字大于p1 当然也大于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 count;}public static void main(String[] args) {int arr[] = new int[]{3,2,4,5,0,6,1};int res = ReverseOrderPair(arr);System.out.println("res=="+res);}
}

8、求小和问题

package com.Mr.ZuoChengYun.sort;/*** @author pshdhx* @date 2022-02-14 15:36* @Des 小和问题*/
/*** 归并排序扩展：* 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；* 逆序对问题：在一个数字中，左边的数字如果比右边的数字大，则两个数字构成一个逆序对，请打印所有的逆序对* 例如：3,2,4,5,0  【逆序对数量 （3,2） （3,0） （2,0） （4,0） （5,0）】*/
/*** 以小和问题为例子：右边有多少个数字比1大，有四个，那就是4个1相加；*                  1,3,4               2,5*             1,3        4           2    5*           1    3  */
public class SmallSum {public static int smallSum(int[] arr){if(arr == null || arr.length < 2){return 0;}return process(arr,0,arr.length-1);}//arr[l...r]既要排好序，也要求小和public static 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 static int  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;int res = 0;while(p1<=m && p2<=r){res += arr[p1] < arr[p2] ? (r-p2+1) * arr[p1]: 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];}return res;}public static void main(String[] args) {int arr[] = new int[]{1,3,4,2,5};int res = smallSum(arr);System.out.println("res=="+res);}
}

9、对数器验证算法准确性

package com.Mr.ZuoChengYun.sort;import java.util.Arrays;/*** @Author pshdhx* @Description 左程云-对数器* @Date 2022/2/11 0011 22:45*/
public class DuiShuQi {public static void comparator(int[] arr){Arrays.sort(arr);}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;}public static int[] copyArray(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){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;}public static void printArray(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 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;j++){if(arr[j]>arr[j+1]){swap(arr,j,j+1);}}}}public static void swap(int[]arr,int i,int j){arr[i] = arr[i] ^ arr[j];arr[j] = arr[i] ^ arr[j];arr[i] = arr[i] ^ arr[j];}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);insertionSort(arr1);comparator(arr2);if(!isEqual(arr1,arr2)){//打印arr1//打印arr2succeed = false;break;}}System.out.println(succeed ? "Nice !" : "Fucking fucked!");int[] arr = generateRandomArray(maxSize,maxValue);printArray(arr);insertionSort(arr);printArray(arr);}
}

10、二分法解释

package com.Mr.ZuoChengYun.sort;/*** @Author pshdhx* @Description 二分法解决问题* @Date 2022/2/11 0011 20:28*/
/***问题一： 在一个有序数组中，查找某个数字是否存在*/
/*** 问题二：在一个有序数组中，找>=某个数字最左侧的数字*/
/***问题三：在arr中，无序，任何相邻的数字一定不相等，局部最小：比左右两边的数字小就可以了。 *//*** 无序也可以二分，谁说二分必须有序的啊？满足某种条件即可。* 如果0位置是局部最小，直接返回* 如果0位置不是局部最小，那么右边的数字一定比他大。↘* 再看最后边的位置：如果n-1位置是局部最小，就直接反悔了；如果不是，那么左边的数字一定比他小 ↙；* 根据最后边两个箭头的指向，这样的话，0位置到n-1位置上一定有个局部最小值；中间一定有个波谷是拐点的，他就是局部最小。* 取中间M位置，如果他是局部最小，直接返回。如果不是，那么他左侧或者右侧一定存在局部最小。从这里开始二分。*/
//对数器的概念和使用/*** 理解：如果一个想要测试的方法a，但是同一个问题可以由很多策略来实现。*/
public class BinarySearch {}