iOS 基础知识:算法基础


概念理解

说说你所知道的排序算法及其时间复杂度?

类别排序方法平均时间复杂度最优时间复杂度最差时间复杂度空间复杂度稳定性复杂性
插入排序直接插入O(n2)O(n)O(n2)O(1)稳定简单
插入排序希尔排序O(n1.3)O(n)O(n2)O(1)不稳定复杂
选择排序直接选择O(n2)O(n2)O(n2)O(1)不稳定简单
选择排序堆排序O(nlog2n)O(nlog2n)O(nlog2n)O(1)不稳定复杂
交换排序冒泡排序O(n2)O(n)O(n2)O(1)稳定简单
交换排序快速排序O(nlog2n)O(nlog2n)O(n2)O(nlog2n)~O(n)不稳定复杂
归并排序O(nlog2n)O(nlog2n)O(nlog2n)O(n)稳定复杂
基数排序O(d(r+n))O(d(r+n))O(d(r+n))O(rd+n)稳定复杂

基数排序中,r 代表关键字的基数,d 代表长度,n 代表关键字个数。

如何不用中间变量交换 A 和 B ?

加减法

该方法可以交换整型和浮点型数值的变量,但在处理浮点型的时候有可能出现精度的损失。

a = a + b;
b = a - b;
a = a - b;

异或法

可以完成对整型变量的交换,对于浮点型变量它无法完成交换。

a = a^b;
b = a^b;
a = a^b;

乘除法

可以处理整型和浮点型变量,但在处理浮点型变量时也存在精度损失问题。而且要求:b ≠ 0

a = a * b;
b = a / b;
a = a / b;