devbox
很楠不爱3
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

算法从入门到精通（一）：认识复杂度和简单的排序算法

作者：很楠不爱3 | 2024-05-21 11:31:06

赞

踩

算法从入门到精通

 一、概述

    算法是进入大厂的敲门砖，也是每位程序员必备技能，从今天开始，博主将仔细和大家聊聊算法和数据结构，努力记下这些，在面试中立于不败之地！

二、分析

    1.认识时间复杂度

    常数操作：一个操作如果与样本的数据量没有关系，每次都是固定时间内完成的操作，称为常数操作。

    时间复杂度为一个算法流程中，常数操作数量的一个指标。常用0（读作big o）来表示。具体来说，先要对一个算法流程非常熟悉，然后去写出这个算法流程中，发生了多少常数操作，进而总结出常数操作数量的表达式。在表达式中，只要高阶项，不要低阶项，也不要高阶项的系数，如果剩下的部分为f(N)，那么时间复杂度为O(f(N))。

    评价一个算法流程的好坏，先看时间复杂度的指标，然后再分析不同数据样本下时间运行的时间，也就是“常数项时间”。

    2.选择排序——细节与复杂度分析

    代码如下：

  1.     /**
  2.      * 选择排序
  3.      * @param arr 目标数组
  4.      */
  5.     public static void selectionSort(int[] arr){
  6.         if(arr==null||arr.length<2){ //如果条件是arr.length<1，则无法产生双重for循环
  7.             return ;
  8.         }
  9.         for (int i = 0; i < arr.length-1; i++) { //不写i < arr.length是因为j = i+1会越界
  10.             int index = i;
  11.             //获得i循环内元素值最小的下标
  12.             for (int j = i+1; j < arr.length; j++) {
  13.                 //这段代码可以被优化
  14.                 /*if(arr[index]>arr[j]){
  15.                     index = j;
  16.                 }*/
  17.                 //巧用三元运算减少代码行
  18.                 index = arr[index]>arr[j]?j:index;
  19.             }
  20.             if(i!=index){
  21.                 //交换数组arr下标为a和下标为b的值
  22.                 swap(arr,i,index);
  23.             }
  24.         }
  25.     }
  26.  
  27.     /**
  28.      * 交换数组arr下标为a和下标为b的值
  29.      * @param arr
  30.      * @param a
  31.      * @param b
  32.      */
  33.     public static void swap(int[] arr,int a,int b){
  34.         arr[a] = arr[a] ^ arr[b];
  35.         arr[b] = arr[a] ^ arr[b];
  36.         arr[a] = arr[a] ^ arr[b];
  37.     }

    复杂度分析：因为是双重for循环，那么时间复杂度自然是O(N^2)，额外空间复杂度为O(1)。

    3.冒泡排序——细节与复杂度分析

    代码如下：

  1.     /**
  2.      * 冒泡排序
  3.      * @param arr 目标数组
  4.      */
  5.     public static void selectionSort(int[] arr){
  6.         if(arr==null||arr.length<2){ //如果条件是arr.length<1，则无法产生双重for循环
  7.             return ;
  8.         }
  9.         for (int i = 0; i < arr.length; i++) {
  10.             for (int j = 0; j < arr.length-1; j++) {
  11.                 //每次比较，将较大的数往后移
  12.                 if(arr[j]>arr[j+1]){
  13.                     swap(arr,j,j+1);
  14.                 }
  15.             }
  16.         }
  17.     }
  18.  
  19.     /**
  20.      * 交换数组arr下标为a和下标为b的值
  21.      * @param arr
  22.      * @param a
  23.      * @param b
  24.      */
  25.     public static void swap(int[] arr,int a,int b){
  26.         arr[a] = arr[a] ^ arr[b];
  27.         arr[b] = arr[a] ^ arr[b];
  28.         arr[a] = arr[a] ^ arr[b];
  29.     }

    复杂度分析：因为也是双重for循环，那么和选择排序一样，时间复杂度自然是O(N^2)，额外空间复杂度为O(1)。

    3.补充：异或运算如何交换两个int变量的值？

    基本：二进制位上，同一位上相同，则取0，不同则取1。

    举例：0^1=1 ，1^0=1，0^0=0，1^1=1

    理解：无进位相加

    性质：

        （1）0^N=N，N^N=0

        （2）满足交换律和结合律：a^b = b^a，(a^b)^c=a^(b^c)

        （3）当一组数异或一个数N，得到的结果是不随着这组数中与N异或顺序的改变而改变的。

    由上诉性质，我们就能明白为什么不需要额外变量就可以交换a和b的值，具体步骤如下：

    注意：当a和b值相同，却不指向同一内存空间时，可以采用此方法。但是a和b指向同一块内存空间的时候，不能采用此方法，因为等同于同一个内存空间异或，最终值会变成0。

    拓展练习题：

    1、在一个int数组arr中，只有一种数字出现了奇数次，其他数字出现了偶数次，如何找到这种数？

        解答：将arr中所有数进行异或运算，得出的结构，就是奇数次的数。

    2、若在题1中，有两种数字出现了奇数次，其他数字出现了偶数次，如何找到这两种数？

        解答：

        （1）假设出现了奇数次的数是a和b；

        （2）设eor为arr中所有数进行异或运算得出的结果，则eor = a ^ b；

        （3）又因为a不等于b，且a，b都不等于0，所以eor化为二进制后，至少有一位不为0，假设次位是k位；

        （4）将数组arr分为两类，一类是k位为1的数组成arr1，一类是k位为0的数arr0；

        （5）将k位是1，其他位是0的数字与arr1或arr0进行异或得到eor2，eor2便是a或者b；

        （6）再将eor2和eor进行异或，便可以得到另一个数。

        取出eor为1的最低位的数字原理如下：

    4.插入排序——细节与复杂度分析

    代码如下：

  1.     /**
  2.      * 插入排序
  3.      * @param arr 目标数组
  4.      */
  5.     public static void insertionSort(int[] arr){
  6.         if(arr==null||arr.length<2){ //如果条件是arr.length<1，则无法产生双重for循环
  7.             return ;
  8.         }
  9.         for (int i = 1; i < arr.length; i++) {
  10.             for (int j = i-1; j>=0&&arr[j]>arr[j+1]; j--) { //不能写作arr[j]>arr[i]，会导致后续每个位置都是和i位置比较
  11.                 //j+1位置上的数如果小于j位置上的数，则交换
  12.                     swap(arr,j+1,j);
  13.             }
  14.         }
  15.     }
  16.  
  17.     /**
  18.      * 交换数组arr下标为a和下标为b的值
  19.      * @param arr
  20.      * @param a
  21.      * @param b
  22.      */
  23.     public static void swap(int[] arr,int a,int b){
  24.         arr[a] = arr[a] ^ arr[b];
  25.         arr[b] = arr[a] ^ arr[b];
  26.         arr[a] = arr[a] ^ arr[b];
  27.     }

        注意：插入排序比较特殊，时间复杂度会因为数据本身的顺序所影响。例如int a[] = {6,5,4,3,2,1}，时间复杂度是O(N^2)；而int a[] = {1,2,3,4,5,6}，则时间复杂度是O(N)。额外的空间复杂度都是O(1)。但是算法流程一般都是按照最差的情况来估算时间复杂度，所以插入排序的时间复杂度也是O(N^2)。

    5.二分法的详解与扩展

    （1）在一个有序数组arr[]中，找某个数num是否存在

        解析：arr[]先取中点k的数，如果arr[k]>num，则表示可以抛弃arr[k]右边的元素；继续在arr[0]到arr[k-1]上进行上述操作，直至找到等于num的位置。时间复杂度为O(logN)，如下图：

    （2）在一个有序数组arr[]中，找>=某个数num最左侧的位置（<=某个数同理）

        解析：arr[]先取中点k的数，如果arr[k]>=num，则用t记录下此时k的位置；继续在arr[0]到arr[k-1]上进行上述操作，若中点的数还是满足>=num，则更新t为此时的位置，继续进行上述操作，直至不能继续二分；若在arr[0]到arr[k-1]上进行上述操作，中点的数不满足>=num，则不更新t的值，而在右侧继续进行上述操作，直至不能继续二分。时间复杂度为O(logN)，如下图：

    （3）局部最小值(在0到1位置上，若arr[0]<arr[1]，则arr[0]是局部最小；在n到n-1位置上，若arr[n]<arr[n-1]，则arr[n]是局部最小；在i-1到i+1位置上，若arr[i]<arr[i-1]&&arr[i]<arr[i+1]，则arr[i]是局部最小)问题：在一个长度为N-1数组中arr[]无序，但任意两个相邻的数不相等，求一个局部最小的位置。

        解析：先判断0位置和N-1位置是不是局部最小，若不是则取中点位置M，判断在M-1到i+M位置上，M是否局部最小；若不是，则看趋势是往左递减还是往右递减，往哪边递减，就在哪边再取中间位置重复上述操作即可。时间复杂度为O(logN)，如下图：

    注意：不是所有的二分都是在有序数组上进行的。

    流程优化方向：

        （1）数据状况。数据状况特殊，可以被优化。

        （2）求的问题的标准。问的问题比较特殊，可以被优化。

    6.对数器的概念和使用

    概念：

    （1）有一个你想要测的方法a;

    （2）实现复杂度不好，但是容易实现的方法b;

    （3）实现一个随机的样本产生器

    （4）把方法a和方法b跑相同的随机样本，看得到的结果是否一样

    （5）如果有一个随机样本使得比对结果不一致，打印样本进行人工干预，改对方法a或者b

    （6）当样本数量很多是比对测试依然正确，则可以确定方法a已经正确

    使用：

  1. public class test2 {
  2.  
  3.     /**
  4.      * 测试冒泡
  5.      * @param args
  6.      */
  7.     public static void main(String[] args) {
  8.         int testTime = 500;
  9.         int maxSize = 100;
  10.         int maxValue = 100;
  11.         boolean succeed = true;
  12.         for (int i = 0; i < testTime; i++) {
  13.             int[] arr1 = generateRandomArray(maxSize,maxValue);
  14.             int[] arr2 = copyArray(arr1);
  15.             selectionSort(arr1);
  16.             comparator(arr2);
  17.             if(!isEqual(arr1,arr2)){
  18.                 succeed = false;
  19.                 break;
  20.             }
  21.         }
  22.  
  23.         System.out.println(succeed?"Nice!":"Bad!");
  24.     }
  25.  
  26.     /**
  27.      * 冒泡排序
  28.      * @param arr 目标数组
  29.      */
  30.     public static void selectionSort(int[] arr){
  31.         if(arr==null||arr.length<2){ //如果条件是arr.length<1，则无法产生双重for循环
  32.             return ;
  33.         }
  34.         for (int i = 0; i < arr.length; i++) {
  35.             for (int j = 0; j < arr.length-1; j++) {
  36.                 //每次比较，将较大的数往后移
  37.                 if(arr[j]>arr[j+1]){
  38.                     swap(arr,j,j+1);
  39.                 }
  40.             }
  41.         }
  42.     }
  43.  
  44.     /**
  45.      * 交换数组arr下标为a和下标为b的值
  46.      * @param arr
  47.      * @param a
  48.      * @param b
  49.      */
  50.     public static void swap(int[] arr,int a,int b){
  51.         arr[a] = arr[a] ^ arr[b];
  52.         arr[b] = arr[a] ^ arr[b];
  53.         arr[a] = arr[a] ^ arr[b];
  54.     }
  55.  
  56.  
  57.     public static int[] generateRandomArray(int maxSize,int maxValue){
  58.         //Math.random() -> [0,1) 所有的小数，等概率返回一个
  59.         //Math.random()*N -> [0,N) 所有的小数，等概率返回一个
  60.         //(int)Math.random()*N -> [0,N-1] 所有的整数，等概率返回一个
  61.         int[] arr = new int[(int)((maxSize+1)*Math.random())]; //长度随机
  62.         for (int i = 0; i < arr.length; i++) {
  63. //            arr[i] = (int)((maxSize+1)*Math.random());
  64.             arr[i] = (int)((maxSize+1)*Math.random())-(int)((maxSize)*Math.random()); //可以得到负数，增加随机性
  65.         }
  66.         return arr;
  67.     }
  68.  
  69.     /**
  70.      * 判断两个数组元素顺序是否完全一致
  71.      * @param arr1
  72.      * @param arr2
  73.      * @return
  74.      */
  75.     public static boolean isEqual(int[] arr1, int[] arr2){
  76.         if((arr1==null&&arr2!=null)||(arr1!=null&&arr2==null)){
  77.             return false;
  78.         }
  79.         if(arr1==null&&arr2==null){
  80.             return true;
  81.         }
  82.         if(arr1.length!=arr2.length){
  83.             return false;
  84.         }
  85.         for (int i = 0; i < arr1.length; i++) {
  86.             if(arr1[i] != arr2[i]){
  87.                 return false;
  88.             }
  89.         }
  90.         return true;
  91.     }
  92.  
  93.     /**
  94.      * 复制一个数组arr
  95.      * @param arr
  96.      * @return
  97.      */
  98.     public static int[] copyArray(int[] arr){
  99.         if(arr==null){
  100.             return null;
  101.         }
  102.         int[] res = new int[arr.length];
  103.         for (int i = 0; i < arr.length; i++) {
  104.             res[i] = arr[i];
  105.         }
  106.         return res;
  107.     }
  108.  
  109.     /**
  110.      * 默认排序
  111.      * @param arr
  112.      */
  113.     public static void comparator(int[] arr){
  114.         Arrays.sort(arr);
  115.     }
  116.  
  117. }

三、总结

    本文介绍了选择排序、冒泡排序、插入排序等基础排序，主要是希望根据简单的基础排序带领大家认识时间复杂度的概念。下一篇博主将介绍几个重要的排序算法如归并排序、堆排序等详解，敬请期待《算法从入门到精通（二）：认识O(NlogN)的排序》。

    更多精彩内容，敬请扫描下方二维码，关注我的微信公众号【Java觉浅】，获取第一时间更新哦！

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/很楠不爱3/article/detail/602334
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号