一、复杂度是什么？

复杂度是帮助我们衡量一个算法优劣的指标。分为时间复杂度和空间复杂度。

1.1时间复杂度

衡量算法运行速度的指标。
一个算法执行所耗费的时间理论上说只有把程序放在机器上跑起来，才能知道。但是我们一般不这样做，而是用时间复杂度分析公式代替。

1.1.1时间复杂度计算

一个算法流程中发生了多少次常数操作，进而总结出常数操作数量的表达式。
那么何为常数操作呢？
一个操作如果和样本的数据量没有关系，每次都是固定时间内完成的操作，叫做常数操作。
例如：加减乘除、位运算等。

1.1.2时间复杂度表示:大O渐进表示法

大O符号（Big O notation）：是用于描述函数渐进行为的数学符号。
推导大O阶方法：
1、用常数1取代运行时间中的所有加法常数。
2、在修改后的运行次数函数中，只保留最高阶项。
3、如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶。
对于算法的时间复杂度来说存在最好、平均和最坏情况，一般我们最常用的是最坏情况。

一个算法所花费的时间与其中语句的执行次数成正比例，算法中的基本操作的执行次数，为算法的时间复杂度。最坏情况代表的是该算法最多执行的次数。

1.2空间复杂度

空间复杂度是对一个算法在运行过程中临时占用存储空间大小量度。

二、排序算法

对选择排序不熟悉的小伙伴可以看这个动态图解，这里有8个排序方法的动态图解，便于我们理解各种排序算法：
链接: 排序动态图解

2.1选择排序

原理：遍历整个数组，并将本次循环起始位置的值设置为最小值，然后通过循环来找到真正的最小值。
1、把第一个没有排序过的元素设置为最小值，遍历每个没有排序过的元素，如果元素 < 现在的最小值，则将此元素设置成为新的最小值；
2、将最小值和第一个没有排序过得位置交换；
3、从下一个没有排序过得元素开始，重复步骤1和2。
4、一共重复（元素个数 -1）次。

public void selectionSort(int[] arr){if(arr == null || arr.length < 2){return;}//第一个循环是交换多少轮for(int i = 0; i < arr.length; i++){int minIndex = i;//第二个循环是每一轮比较多少次for(int j = i + 1; arr.length; j++){minIndex = arr[j] < arr[minIndex] ? j : minIndex;}int temp = arr[i];arr[i] = arr[minIndex];arr[minIndex] = temp;}
}

2.2冒泡排序

从i = 0到最后一个没有排序过得原色的索引-1，如果左边元素 > 右边元素，则进行交换。

public void bubbleSort(int[] arr){if(arr == null || arr.length < 2){return;}for(int j = arr.length - 1; j > 0; j--){for(int i = 0; i < j; i++){if(arr[i] > arr[i+1]){//交换，即大的数往后冒泡//这里使用的位运算来进行两个数的交换，没有利用中间变量arr[i] = arr[i] ^ arr[i+1];arr[i+1] = arr[i] ^ arr[i+1];arr[i] = arr[i] ^ arr[i+1];}}}
}

对于利用位异或交换两个数的值是如何实现的，可以查看下面这篇文章：
链接: java交换两个数的值的三种方法：位异或运算交换、算数交换、中间变量交换

2.3练习

2.3.1找出一组数中的某个出现奇数次的数

public void printOddTimesNum1(int[] arr){int eor= 0;for(int cur : arr){eor  ^= cur;}System.out.println(eor);
}

原理就是通过相与将出现偶数次的数全部抵消掉了，最后只剩下出现基数次的那一个数。

2.3.2找出一组数中的某两个出现奇数次的数

假设出现奇数次的数分别为a和b

public void printOddTimesNum2(int[] arr){int eor= 0, onlyOne = 0;for(int cur : arr){eor  ^= cur;}//到这里为止，可知：//eor = a ^ b//eor != 0 即eor中必然有一个位置上为1int rightOne = eor ^ (~eor + 1);//获取eor中最右边第一个不为0的位for(int cur : arr){if((cur & rightOne) ==0){onlyOne ^= cur;}}System.out.println(onlyOne + " " + (eor ^ onlyOne));
}

2.4插入排序

从第1位开始，依次和它前面的数进行比较，如果小于前面的数则进行交换。
先看第1位，跟第0位比较大小，让0~0位置上有序
再看第2位，跟第1位比较大小，让0~1位置上有序
再看第3位，跟第2位比较大小，让0~1位置上有序
……
再看第n-1位，跟第n-2位比较大小，让0~n-1位置上有序
就是把已有序序列后的一个数插入已有序序列合适的位置。
联想：打牌的时候，让牌从小到大排列。也有点像反向冒泡。
时间复杂度O(N^2)，额外空间复杂度O(1)。

public void insertSort(int[] arr){if(arr == null || arr.length < 2){return;}for(int i = 1; i < arr.length - 1; i++){//0~0是有序的//0~i想有序for(int j = i-1; j >= 0 && arr[j] > arr[j+1]; j--){//交换，即小的数往前//这里使用的位运算来进行两个数的交换，没有利用中间变量arr[j] = arr[j] ^ arr[j+1];arr[j+1] = arr[j] ^ arr[j+1];arr[j] = arr[j] ^ arr[j+1];}}
}

词库加载错误:未能找到文件“E:\highferrum_mysql\Configuration\Dict_Stopwords.txt”。

上一篇：mysql-锁

下一篇：js深浅拷贝

算法与数据结构学习笔记一：认识复杂度与简单排序算法

文章目录