0


1. 认识复杂度和简单排序算法

1. 认识复杂度和简单排序算法

常数时间的操作,一个操作如果和样本的数据量没有关系,每次都是固定时间内完成的操作,叫做常数操作。
例子:

int a = arr[i];

时间复杂度为一个算法流程中,常数操作数量的一个指标。常用O(读作big O)来表示。具体来说,先要对一个算法流程非常熟悉,然后去写出这个算法流程中,发生了多少常数操作,进而总结出常数操作数量的表达式。
在表达式中,只要高阶项,不要低阶项,也不要高阶项的系数,剩下的部分如果为f(N),那么时间复杂度为O(f(N))。
评价一个算法流程的好坏,先看时间复杂度的指标,然后再分析不同数据样本下的实际运行时间,也就是“常数项时间”。

1. 选择排序

选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理是:

  1. 第一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置。
  2. 然后再从剩余的未排序元素中寻找到最小(大)元素,然后放到已排序的序列的末尾。
  3. 以此类推,直到全部待排序的数据元素的个数为零。

选择排序是不稳定的排序方法。时间复杂度O(n^2), 空间复杂度O(1)。
例如给定一组数据,[4, 2, 3, 6, 5]其排序过程如以下所示
第一次: [

2

, 4, 3, 6, 5]
第二次: [

2, 3

, 4, 6, 5]
第三次: [

2, 3, 4

, 6, 5]
第四次: [

2, 3, 4, 5

, 6]
第五次: [

2, 3, 4, 5, 6

]

以下是@五分钟学算法大佬的动画,侵删。
在这里插入图片描述
java代码实现:

packagepaixu;importjava.util.Arrays;publicclassCode01_SelectionSort{publicstaticvoidmain(String[] args){int[] arr ={4,2,3,6,5};selectionSort(arr);System.out.println(Arrays.toString(arr));}publicstaticvoidselectionSort(int[] arr){if(arr ==null|| arr.length <2){return;}for(int i =0; i < arr.length -1; i++){int minIndex = i;for(int j = i +1; j < arr.length; j++){
                minIndex = arr[j]< arr[minIndex]? j : minIndex;}swap(arr, i, minIndex);}}publicstaticvoidswap(int[] arr,int i,int j){int tmp = arr[i];
        arr[i]= arr[j];
        arr[j]= tmp;}}

在这里插入图片描述

2. 冒泡排序

冒泡排序的英文Bubble Sort,是一种最基础的交换排序。之所以叫做冒泡排序,因为每一个元素都可以像小气泡一样,根据自身大小一点一点向数组的一侧移动。冒泡排序算法的原理如下:

  1. 比较相邻的元素。如果第一个比第二个大,就交换他们两个。
  2. 对每一对相邻元素做同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。
  3. 针对所有的元素重复以上的步骤,除了最后一个。
  4. 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

冒泡排序是稳定的排序方法。时间复杂度O(n^2), 空间复杂度O(1)。
在这里插入图片描述
java代码:

packagepaixu;importjava.util.Arrays;publicclassCode02_BubbleSort{publicstaticvoidmain(String[] args){int[] arr ={6,4,1,2,9,3,7,8,10,5};bubbleSort(arr);System.out.println(Arrays.toString(arr));}publicstaticvoidbubbleSort(int[] arr){if(arr ==null|| arr.length <2){return;}for(int e = arr.length -1; e >0; e--){boolean flag =true;for(int i =0; i < e; i++){if(arr[i]> arr[i +1]){swap(arr, i, i +1);
                    flag =false;}}if(flag){break;}}}publicstaticvoidswap(int[] arr,int i,int j){
        arr[i]= arr[i]^ arr[j];
        arr[j]= arr[i]^ arr[j];
        arr[i]= arr[i]^ arr[j];//        int tmp = arr[i];//        arr[i] = arr[j];//        arr[j] = tmp;}}

在这里插入图片描述

3. 异或运算

异或运算资源来自 https://blog.csdn.net/weixin_43614026/article/details/104341932

如果a、b两个值不相同,则异或结果为1。如果a、b两个值相同,异或结果为0。异或也叫半加运算,其运算法则相当于不带进位的二进制加法:二进制下用1表示真,0表示假,则异或的运算法则为:0⊕0=0,1⊕0=1,0⊕1=1,1⊕1=0(同为0,异为1),这些法则与加法是相同的,只是不带进位,所以 异或常被认作不进位加法。(来源于搜狗百科)

例如,计算 1011101^1000011:
在这里插入图片描述

异或性质与扩展
(用不进位相加较好理解)

  • 0 ^ N = N
  • N ^ N = 0

异或运算满足交换律和结合律

  • c =a ^ b =b ^ a
  • c =( a ^ b )^ c = a ^ ( b ^ c )

不用额外变量交换两个数:
在这里插入图片描述

  • 一个数组中有一种数出现了奇数次,其他数都出现了偶数次,怎么找到这个数? 例如,该数组为 a[]={1, 2, 2, 3, 3} 将所有的数全部异或运算,运算结果就是出现了奇数次的数。
  • 一个数组中有两种出现了奇数次,其他数都出现了偶数次,怎么找到这两个数? 例如,该数组为a[]={1,2,4,4,5,5},分析步骤如下:
  1. 让该数组中所有的数字做异或运算,那么设结果 eor == a ^ b != 0 ;
  2. 因为eor 不为 0 ,则可以假设 a 与 b在某位上,比如在第三位上,a第三位是1,则b的第三位为0;
  3. 在其余的出现偶数次的数字中,找出所有在第三位为1的数;
  4. 用变量 eor’ 与这个数组中所有第三位为1的数做异或运算 ,则 eor’ 最终的答案为a,因为所有第三位为1的数字,除了a,其余为偶数 个,异或运算后为0。(因为除了a 与 b ,其余数字的个数都为偶数个,那么可以确定第三位为1的和第三位为0的个数都为偶数个。因为 eor = a ^ b,且其余偶数运算之后结果为0,如果第三位为1的数字个数为奇数,那么第三位为0的数字个数也为奇数,那么将他们全部进行异或运算后,第三位数字为1,不为0,与实际不符。)
  5. 再用eor与eor’做异或运算,即a ^ b ^ a = b;

以下给出该题解的代码:首先了解如何取到该数最右端的1,就是该数取反+1再&该数 (核心:int rightOne = eor & ( ~ eor + 1 ); )
在这里插入图片描述
java代码:

packagepaixu.class01;publicclassCode07_EvenTimesOddTimes{publicstaticvoidmain(String[] args){int[] arr ={1,2,4,4,5,5};printOddTimesNum2(arr);}publicstaticvoidprintOddTimesNum2(int[] arr){int eor =0, onlyOne =0;for(int curNum : arr){
            eor ^= curNum;}//eor = a ^ b//eor != 0//eor 必然有一个位置上是 1int rightOne = eor &(~eor +1);//提取出最右的1System.out.println("右边第"+ rightOne +"位是0的有以下这些数");for(int cur : arr){if((cur & rightOne)==0){System.out.println(cur);
                onlyOne ^= cur;}}System.out.println("这两个数分别是:\t"+ onlyOne +"\t"+(onlyOne ^ eor));}}

在这里插入图片描述

4. 插入排序

插入排序的原理:
一般也被称为直接插入排序。对于少量元素的排序,它是一个有效的算法。插入排序是一种最简单的排序方法,它的基本思想是将一个记录插入到已经排好序的有序表中,从而得到一个新的、记录数增 1的有序表。在其实现过程使用双层循环,外层循环对除了第一个元素之外的所有元素,内层循环对当前元素前面有序表进行待插入位置查找,并进行移动 。
选择排序的基本思想是:

将未排序的元素一个一个地插入到有序的集合中,插入时把所有有序集合从后向前扫一遍,找到合适的位置插入。

插入排序是稳定的排序方法。时间复杂度O(n^2), 空间复杂度O(1)。
下图来源 https://blog.csdn.net/hcz666/article/details/126488359。插入排序的过程如下:
在这里插入图片描述
java代码:

packagepaixu.class01;importjava.util.Arrays;publicclassCode03_InsertSort{publicstaticvoidmain(String[] args){int[] arr ={9,7,8,2,5,1,3,6,4};insertionSort(arr);System.out.println(Arrays.toString(arr));}publicstaticvoidinsertionSort(int[] arr){if(arr ==null|| arr.length <2){return;}//0~0 有序//0~i 想有序for(int i =1; i < arr.length; i++){// 0~i 做到有序for(int j = i -1; j >=0&& arr[j]> arr[j +1]; j--){swap(arr, j, j +1);}}}publicstaticvoidswap(int[] arr,int i,int j){
        arr[i]= arr[i]^ arr[j];
        arr[j]= arr[i]^ arr[j];
        arr[i]= arr[i]^ arr[j];}}

在这里插入图片描述

5. 二分法的详解与扩展

  • 在一个有序数组中,找某个数是否存在。时间复杂度O(logN) java代码:
packagepaixu.class01;publicclassCode04_BSExist{publicstaticvoidmain(String[] args){int[] sortedArr ={1,2,3,4,5,6,7,8,9};System.out.println(exist(sortedArr,5));}publicstaticbooleanexist(int[] sortedArr,int num){intL=0;intR= sortedArr.length -1;while(L<=R){int mid =L+((R-L)>>1);if(sortedArr[mid]== num){System.out.println("目标数下标:"+ mid);returntrue;}if(sortedArr[mid]> num){R= mid -1;}else{L= mid +1;}}returnfalse;}}

在这里插入图片描述

  • 在一个有序数组中, 找>=某个数最左侧的位置

java代码

packagepaixu.class01;publicclassCode05_BSNearLeft{publicstaticvoidmain(String[] args){int[] arr ={1,2,3,3,3,3,3,3,4,4,4,4,4,5,5,5,5,5,6,6,6,6};System.out.println("最左边的值为:"+nearestIndex(arr,6));}// 在arr上,找满足>=value的最左位置publicstaticintnearestIndex(int[] arr,int value){intL=0;intR= arr.length -1;int index =-1;while(L<=R){int mid =L+((R-L)>>1);if(arr[mid]>= value){R= mid -1;
                index = mid;}else{L= mid +1;}}return index;}}

在这里插入图片描述

  • 局部最小值问题题目描述 局部最小值定义:
  1. 最左边边界处,如果最左边的数小于左边第二个数,则最左边为局部最小值。
  2. 最右边边界处,如果最右边的数小于右边第二个数,则最右边为局部最小值。
  3. 中间处,如果一个数小于它两边的数,则这个数就是局部最小值。

说白了,就是二维坐标系中的任意一个最低点,都是局部最小值。现在,有一个数组,相邻的两个数不相等,请求出一个数组中的一个局部最小值。
算法思路

  1. 首先,先观察最左边的第一个和第二个数,判断是否是局部最小值。
  2. 然后,再观察最右边第一个和第二个数,判断是否是局部最小值。
  3. 如果最左边和最右边有一个是局部最小值,则此题结束。
  4. 否则,说明一个什么问题?说明左边的曲线是向下递减的,右边的曲线也是向上递增的,对吧?那么,中间是必定有局部最小值的,这是在高数最大值最小值中有类似的定义,对吧?
  5. 然后,直接用二分法,选取中间的数,判断其是不是局部最小值?如果不是的话,观察他左右趋势,假如,它左边一个数比他小,说明什么?说明它左边是递增的,而此时最左边的递减的,通过上面分析4的判断,说明它左边存在局部最小值,然后,再其左边区间,再次二分法,直到找到局部最小值。

总结:
这题代码其实就是二分查找。关键是此题的思路,这是重点,此题说明了,二分查找并不一定只能求解有序数组中的某个数。在一些能够直接排除掉一半区间的例子中,也同样可以使用二分法来解决,将时间复杂度直接降低到O(logn)。
就比如此题,可以根据一个区间两边的递增递减性,来判断区间内是否有局部最小值,那么,就可以直接用二分法从中间划分,然后根据判断条件,可以直接排除掉一半区间。

java代码:

packagepaixu.class01;publicclassCode09_FindOneLessValueIndex{publicstaticvoidmain(String[] args){int[] arr ={6,5,3,4,6,7,8};int[] arr1 ={1,2,3,4,5,6,7,8};int[] arr2 ={2,1,3,4,5,6,8,7};System.out.println("(中间情况)arr局部最小索引为:"+getLessIndex(arr)+"\t值为"+ arr[getLessIndex(arr)]);System.out.println("(左边情况)arr1局部最小索引为:"+getLessIndex(arr1)+"\t值为"+ arr1[getLessIndex(arr1)]);System.out.println("(右边情况)arr2局部最小索引为:"+getLessIndex(arr2)+"\t值为"+ arr2[getLessIndex(arr2)]);}publicstaticintgetLessIndex(int[] arr){if(arr ==null|| arr.length ==0){return-1;// no exist}//1.先观察最左边的第一个和第二个数,判断是否是局部最小值if(arr.length ==1|| arr[0]< arr[1]){return0;}//2.再观察最右边第一个和第二个数,判断是否是局部最小值if(arr[arr.length -1]< arr[arr.length -2]){return arr.length -1;}//3.局部最小值在中间intL=1;intR= arr.length -2;while(L<=R){int mid =L+((R-L)>>1);if(arr[mid]< arr[mid -1]&& arr[mid]< arr[mid+1]){return mid;}if(arr[mid]< arr[mid+1]){R= mid -1;}else{L= mid +1;}}return-1;}}

在这里插入图片描述

6. 对数器的概率和使用

  1. 有一个你想要测的方法a
  2. 实现复杂度不好但是容易实现的方法b
  3. 实现一个随机样本产生器
  4. 把方法a和方法b跑相同的随机样本,看看得到的结果是否一样。
  5. 如果有一个随机样本使得比对结果不一致,打印样本进行人工干预,改对方法a或者方法b
  6. 当样本数量很多时比对测试依然正确,可以确定方法a已经正确。

本文转载自: https://blog.csdn.net/qq_41246557/article/details/128074784
版权归原作者 韩顺平的小迷弟 所有, 如有侵权,请联系我们删除。

“1. 认识复杂度和简单排序算法”的评论:

还没有评论