搜索
写经验 领红包

选择排序冒泡排序的区别(选择排序和冒泡排序的时间复杂度和稳定性)

导语:选择排序、冒泡排序、异或运算

选择排序

数组取数时间复杂度是常数

int a= arr[i]

从数组中获取第i位置的数即获取某个偏移量或距离的数 时间复杂度是一个常数

数组在内存中的地址空间是连续的 所以通过偏移量就可以获取到指定位置上的值

集合取数时间复杂度不是常数,和数据量有关

int b = list.get(i)

从list集合中获取某一个位置的值 时间复杂度不是一个常数 因为和集合中的数据量有关

集合中的数据越多 耗时越长

list集合中的元素在内存中的地址不是连续的

先找第一个元素 再找第二个元素 再找第三个元素 ,元素越多,耗时越长

选择排序的时间复杂度

第一次排序是 从0到N-1个数中找最小的值放在第一位 确定了一个最小值

第二次排序是 从1到N-1个数中找最小的值放在第二位 确定了次次小的值

第三次排序是 从2到N-1个数中找最小的值放在第三位 确定了第三小的值

第四次排序是 从3到N-1个数中找最小的值放在第四位 确定了第四小的值

要计算该过程的时间复杂度需要先看下有多少个常数操作

每次排序都需要遍历一下 第一次排序遍历数组中所有的值即N次 第二次排序遍历N-1次 第三次排序遍历N-2次 第四次排序遍历N-3次每次遍历都需要比较一下 第一次排序比较了N-1次姑且认为N次 第二次排序比较了N-1次 第三次排序比较了N-2次 第四次排序比较了N-3次把最小值找到并且放到第0下标的位置上 每一次排序都需要1次这样的操作

一共做了这么多次常数操作

因为求等差数列一定有N^2 一定有N项

所以可以写成 a N^2+b N+c

这个就是常数数量的表达式

而时间表达式就是在常数数量级的表达式中不要低级项 只要最高阶级的项 而且忽略掉高级项的系数 所剩下的

所以时间复杂度是O(N^2)的算法

小结

当两个时间复杂度不同的算法在评估好坏的时候 时间复杂度越小越好 比如O(N) 比 O(N^2)好同样的时间复杂度比如都是O(N)就要看常数项了 虽然可以估算常数操作发生的具体数量 但每一个常数操作虽然是固定时间 但每个时间是不一样的 比如一个常数项是10 常数操作是乘法 另一个常数项是100 常数操作是位运算 此时没发估计 只能实际测试得出每个常数操作的具体时间

这两个算法 每个算法的常数操作执行O(N)次 每次都进行三个常数次操作 所以这2个算法的时间复杂度都是O(N)的 通过理论比较不出只能实际跑一下

额外空间复杂度

只需要有限几个变量就可以完成算法流程的话 就是额外空间复杂度O(1)

若必须开辟一个额外数组 这个额外数据和原来数组等规模的时候 额外的空间复杂度就是O(N)了

选择排序代码

在i到N-1范围选一个最小值 并且把最小值放到i位置上去

只用到了几个变量 i,j,minindex(每次都会释放)

所以额外空间复杂度是O(1)

冒泡排序

初始数据 3,2,5,4,3,6

下标依此是0,1,2,3,4,5

第一次排序:

0,1位置上的数据比较 谁大谁往右移动

1,2位置比较谁大谁往右移动

依此类推 最后确定位置5上的数据是6

第二次排序确定了位置4上的数据是5

小结

第一次排序在0~N-1个数上 确定了N-1位置上的数

第二次排序在0~N-2个数上 确定了N-2位置上的数

第三次排序在0~N-3个数上 确定了N-3位置上的数

还是一个等差数列 a N^2 + b N + c

还是O(N^2)复杂度的算法

冒泡排序代码

异或运算

相同为0 不同为1

二进制异或也是一样的

异或还可以理解为无进位相加

比如0和1相加是1 1和1项加是0 不进位

异或运算性质

0^N=N;N^N=0

0和任何数异或都是N 任何数和自己异或都是0

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

a^b=b^a;(a^b)^c=a^(b^c)

同样一批数亦或得到的结果和选择谁先谁后去异或无关

a、b值交换

第一行 a=a^b a为甲 b为乙 a=a^b即a=甲^乙,b为乙

第二行 b=a^b

a=甲^乙,b=甲^乙^乙

根据任何一个数异或自己都为0得乙^乙=0

根据任何一个数异或0都为自己得甲^0为甲 所以b=甲

第三行a=a^b 甲^乙^甲=乙

所以就实现了交换数据的效果

用异或的前提是 a和b所指向的内存是两块不同的东西,值可以一样 比如甲=乙

如果内存一样 同样的内存区域和自己异或 值都会变成0了

大厂面试题

要求

时间复杂度O(N)、额外空间复杂度O(1) 只用有限几个变量

2个题目

1)

一个int[]整型数组中只有一种数出现了奇数次

其他数出现偶数次

怎么找到出现了奇数次的数

解题

定义一个变量 int eor=0;

定义一个数组int [a,b,c....]

用这个变量去异或数组中的每一个元素

eor ^ a eor ^ b eor ^ c

最后这个eor就是出现了奇数次的数

比如这个数组是 [2,1,3,1,3,1,3,2,1]

因为异或运算顺序无所谓

等同于 [1,1,1,1,2,2,3,3,3]

4个1异或完是0 2个2异或完是0 3个3异或完是3

代码

原理介绍

比如每个数有5个二进制位

如果最高位的1出现奇数个的话 无进位相加的结果就是1

如果最高位出现偶数次1的话 最终结果就是0

所以最终的结果和某一位上1的个数有关 和顺序没有关系

2)

一个int[]整型数组中两种数出现了奇数次

其他数出现偶数次

怎么找到出现了奇数次的数

假设一个数组中 a和b 出现奇数次 其他的数字others都出现偶数次

如果一个变量eor 从头异或到尾 最终结果是a^b

即先把偶数次异或掉都是0

再和奇数个a异或得到a

再和奇数个b异或得到a^b

又因为是2种数 所以a != b

那么eor一定是不等于0的

即eor 这个32位整数的某一位上至少有一位不等于0

假设eor在第8位上是1

说明a数和b数在第8位上是不一样的

再定义一个变量 eor&39;异或上第8位不是1的那些数

只有某一个数字在第8位不是1才异或进eor‘中 得到a或者b

假设eor&39;=a^b^a=b

本文内容由快快网络小竹整理编辑!