美文网首页
数据结构与算法一:复杂度和简单排序算法

数据结构与算法一:复杂度和简单排序算法

作者: 菜鸟养成记 | 来源:发表于2021-07-02 01:12 被阅读0次

    时间复杂度O

    常数时间的操作

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

    时间复杂度为一个算法流程中,常数操作数量的一个标志。常用大O来表示。具体来说,首先对一个算法流程非常熟悉,然后去写出这个算法流程中,发生了多少常数操作,进而总结出常数操作数量的表达式。

    在表达式中,只要高阶项,不要低阶项,也不要高阶的系数,剩下的部分如果为f(N),那么时间复杂度为O(f(N))。
    评价一个算法流程的好坏,先看时间复杂度的指标,然后在分拆不同数据样本下的实际运行时间,也就是“常数项时间”。

    简单排序算法

    选择排序、冒泡排序细节的讲解与复杂度分析(稳定)

    时间复杂度O(N^2),额外空间复杂度O(1)

    选择排序源码分析:(Java)

    public class Code01_SelectionSort {
        //测试函数
        public static void main(String[] args){
            int arr[] = {3,1,2,6,7,8};
            System.out.print("排序前:");
            for (int a : arr)
                System.out.print(a);
            selectionSoet(arr);
            System.out.print("\n排序后:");
            for (int a : arr)
                System.out.print(a);
        }
        //选择排序算法
        public static  void  selectionSoet(int[] arr){
            if(arr == null || arr.length < 2){
                return;
            }
            for (int i = 0;i < arr.length - 1; i++){ //i ~ N-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;
        }
    }
    

    冒泡排序源码分析:(Java)

    public class Code02_BubbleSort {
    
        public static void main(String[] args){
            int arr[] = {3,1,2,6,7,8};
            System.out.print("排序前:");
            for (int a : arr)
                System.out.print(a);
            bubbleSort(arr);
            System.out.print("\n排序后:");
            for (int a : arr)
                System.out.print(a);
        }
        //冒泡排序算法
        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]){
                        swap(arr, i, i+1);
                    }
                }
            }
        }
        // 交换arr的i和j的值
        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];
        }
    }
    

    异或运算(^)

    1、0 ^ N = N
    2、满足交换律、结合律

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

    常见面试题(异或)

    1. 一个数组中只有一种数出现奇数次,找出这一个数 {3,3,2,2,7,8,7}
    2. 一个数组中只有两种数出现奇数次,找出这两个数{3,3,2,7,8,7,8,9,2,10}

    异或题解源码实现(提示:偶数次的异或为0,0与任何数异或为任何数)

    public class Code07_EvenTimesOddTimes {
    
        //一个数组里面只有一种数出现奇数次,剩下所有数均出现偶数次,找到这个奇数值
        public static void printOddTimesNum1(int[] arr){
            int eor = 0;
            for (int cur : arr){
                eor ^= cur;
            }
            System.out.println(eor);
        }
    
    
        //一个数组里只有两种数出现奇数次,找到这两个出现奇数次的数
        public static void printOddTimesNum2(int[] arr){
            int eor = 0;
            for (int i = 0; i < arr.length; i++){
                eor ^= arr[i];
            }
            // eor = a ^ b
            // eor != 0
            // eor必然有一个位置上是1
            int rightOne = eor & (-eor + 1); // 提取出最右边的1
            int onlyOne = 0; //eor'
            for(int cur : arr){
                if((cur & rightOne) == 0){
                    onlyOne ^= cur;
                }
            }
            System.out.println(onlyOne + " " + (eor ^ onlyOne));
        }
    
    
        public static void main(String[] args){
            int arrOne[] = {3,3,2,2,7,8,7};
            int arrTwo[] = {3,3,2,7,8,7,8,9,2,10};
            System.out.print("只有一种数现奇数次:");
            printOddTimesNum1(arrOne);
            System.out.print("\n只有2种数现奇数次:");
            printOddTimesNum2(arrTwo);
        }
    }
    

    插入排序讲解与复杂度分析(不稳定)

    时间复杂度O(N^2),额外空间复杂度O(1)
    算法流程按照最差情况来估计时间复杂度(某些数据状况的时间复杂度要优于选择排序和冒泡排序)

    插入排序源码分析:(Java)

    public class Code03_InsertionSort {
        public static  void insertionSort(int[] arr){
            if(arr == null || arr.length < 2){
                return;
            }
            //0~0有序
            //0~i有序
            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);
                }
            }
        }
        //i 和j是一个位置会出错
        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];
        }
    }
    

    相关文章

      网友评论

          本文标题:数据结构与算法一:复杂度和简单排序算法

          本文链接:https://www.haomeiwen.com/subject/mcxeultx.html