harrysimply
commented
2 years ago 选择排序
选择排序定义：从0到N-1找到最小值，放在第0位；之后再从1到N-1找到最小值，放到第1位....直到第N-1位数字。
分析时间： 第一次N次查询，N次比较，1次交换； 第二次N-1次查询，N-1次比较，1次交换...
总共时间：
查询：N+ N-1 + N-2+ N-3 +... (等差数列求和出现平方) 比较：N + N-1 + N-2 + N-3+... 交换： N
= aN^2 + bN + c
因此时间复杂度位O(n^2)
有限几个变量，额外的空间复杂度为O(1)
Big O表示的是操作时间数上限。
在表达式中，只要高阶项，不要低阶项的系数，剩下的部分如果为f(N),那么时间复杂度为O(f(N))。