本文只是自己的笔记，并不具备过多的指导意义。

代码的初衷是便于理解，网上大神优化过的代码很多，也不建议在项目中copy本文代码。

时间复杂度

常数时间的操作

时间复杂度的计算

常数操作表达式类型的时间复杂度

时间复杂度相同的比对

冒泡排序

改进版的冒泡排序

选择排序

二元选择排序

插入排序

时间复杂度的最差情况，最好情况，平均情况

*对数器

衡量代码的好坏，包括两个非常重要的指标：运行时间与占用空间。

而时间复杂度正代表前者，后者由空间复杂度(即算法在运行过程中临时占用存储空间大小的量度)表示。

常数时间的操作

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

比如数组下标的寻址，一对下标交换。

常数操作数量

单次常数时间的操作，写作做O(1)。读作big O 1 。

时间复杂度的计算

法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示。

若有一个函数，f(N)。当N趋近于无穷大时，使得T(n)/f(n)趋近于一个不为0的常数。

则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n))，称O(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。

线性的时间复杂度

比如一个算法共需要执行N次循环，每次循环内部都是常数操作O(1)

for i in 1..

//常数操作

let firstItem = arr[i-1]

let secondItem = arr[i]

if firstItem > secondItem {

arr.swapAt(i-1, i)

}

}

的T(N)=F(N)=N，时间复杂度为O(F(N))=O(N)。

常数操作表达式类型的时间复杂度

对于T(N)为达式类型的时间复杂度，F(N)简而言之就是要简化成当N趋近无穷大时,表达式中对其影响最大的一项的表达式。

具体来说。在常数操作数量的表达式中， 只要高阶项，不要低阶项，也不要高阶项的系数，剩下的部分 如果记为f(N)，那么时间复杂度为O(f(N))。

借用百度百科上的例子：

for(i=1; i<=n; ++i)

{

c[i];//该步骤属于基本操作执行次数：n

for(j=1; j<=n; ++j)

{

c[i][j] = 0;//该步骤属于基本操作执行次数：n的平方次

for(k=1; k<=n; ++k)

c[i][j] += a[i][k] * b[k][j];//该步骤属于基本操作执行次数：n的三次方次

}

}

T(N) = A×N³+B×N²+C×N。当N趋近于无穷大时，三次方的影响远大于二次方以及一次方。当然也大于常数项A的影响。

所以表达式f(N)=N³。

时间复杂度为O(N)=O(f(N))=O(N³)

领附一张图方便理解高阶项在基数变大时的变化：

时间复杂度相同的比对

评价一个算法流程的好坏，先看时间复杂度的指标，然后再分

析不同数据样本下的实际运行时间，也就是常数项时间。

冒泡排序

在冒泡排序过程中会将数组分成两部分，前半部分是无序的数列，后半部分为有序的数列。无序数列中不断的将其中最大的值往有序序列中冒泡，泡冒完后，我们的序列就创建好了。

具体操作上，如果相邻的两个数字前者较大，则将二者交换，到达无序数组边界则停止。

func bubbleSort(arr: inout [Int]) {

if arr.count < 2 {

return

}

for i in 0..

for j in 0..

if arr[j] > arr[j+1] {

let temp = arr[j]

arr[j] = arr[j+1]

arr[j+1] = temp

}

}

}

}

时间复杂度O(N²)，额外空间复杂度O(1)。

时间复杂度的来源f(N) = N +( N -1) + (N-2) + ...+ 2 + 1 为一个等差数列。前N项和的通用公式为:N*(N-1)/2化简后f(N)=N²。

改进版的冒泡排序

经典的冒泡排序，无论数组是否已经有序。都会一次次的遍历，从这一点上我们可以进行改进

func bubbleSort2(arr: inout [Int]) {

if arr.count < 2 {

return

}

var swapped = false //记录是否有交换动作的变量

for i in 0..

swapped = false

for j in 0..

if arr[j] > arr[j+1] {

let temp = arr[j]

arr[j] = arr[j+1]

arr[j+1] = temp

swapped = true //有交换动作则记录

}

}

if swapped == false {

break //没有交换动作，说明已经有序

}

}

}

极端情况下(对于一个已经有序的数组)，算法完成第一次外层循环后就会返回。

实际上只发生了 N - 1次比较，所以最好的情况下，该算法复杂度是O(N)。

选择排序

基本思想与冒泡排序相同。前半部分为序的数列，只不过后半部分是无序的数列。无序数列中不断的将其中最大的值往有序序列中冒泡，泡冒完后，我们的序列就创建好了。

具体操作上，每次遍历记录无序序列中最小值的位置，并在结束时与无序序列的首位置交换，使其变成有序序列的最后一位。

func selectionSort(arr : inout [Int]) {

if arr.count<2 {

return

}

var minIndex :Int

for i in 0..

minIndex = i

for j in i+1..

minIndex = arr[j]

}

arr.swapAt(i, minIndex) //将无序数组的第一位与最小一位交换

}

}

二元选择排序

选择排序本身没有什么可改进的，但是我们可以左右开弓。

将序列分成三个部分，前段有序部分，中段无序部分，后端有序部分。

每次循环，将最大值与最小值分别置入前后两个有序序列。

func selectionSort2(arr : inout [Int]) {

if arr.count<2 {

return

}

var minIndex :Int

var maxIndex :Int

for i in 0..

minIndex = i

maxIndex = i

if i+1 >= arr.count - i {

return // 由于这一步的存在，实际上会在i=arr.count/2处结束循环

}

for j in i+1..

minIndex = arr[j]

maxIndex = arr[j]>arr[maxIndex] ? j:maxIndex //比对当前位置与记录位置的值，记录其中最大的。

}

if maxIndex == i && minIndex == arr.count - (i+1) {

//如果最大值与最小值恰好处于边界，直接交换会导致乱序。需要手动赋值

let maxValue = arr[maxIndex];

let minValue = arr[minIndex];

let maxToValue = arr[arr.count - (i+1)]

let minToValue = arr[i]

arr[maxIndex] = maxToValue

arr[arr.count - (i+1)] = maxValue

arr[minIndex] = minToValue

arr[i] = minValue

}else if maxIndex == i{

//如果最大值位置处于最小值将要交换的位置，先交换最大值

arr.swapAt(arr.count - (i+1) , maxIndex) //将无序数组的最后一位与最大一位交换

arr.swapAt(i, minIndex) //将无序数组的第一位与最小一位交换

}else {

arr.swapAt(i, minIndex) //将无序数组的第一位与最小一位交换

arr.swapAt(arr.count - (i+1) , maxIndex) //将无序数组的最后一位与最大一位交换

}

}

}

这样虽然复杂度还是O(N²)，但实际上的表达式系数比经典选择排序不止缩小了1/2。

插入排序

基本思想也是前半部分为序的数列，后半部分是无序的数列。无序数列不断将其首位元素推给有序数列，有序数列将其插入适当的位置。

具体操作上，会从有序数列的尾部依次向前比较，若前位大于后位则进行交换。

func insertionSort(arr : inout [Int]) {

if arr.count<2 {

return

}

for i in 1..

for j in (0...i-1).reversed() { //从 i-1 位置到 0位置的有序数组内进行循环

if arr[j+1] > arr[j] { //j+1当第一次执行的时候，正位于无序数组的首位置

break //如果后位置大于前位置，说明已经有序。退出当前循环

}

arr.swapAt(j, j+1)//否则交换

}

}

}

改进的话，或许可以试试用二分法确定具体位置然后进行整体后移并插入。

时间复杂度的最差情况，最好情况，平均情况

对于插入排序这种有明确终止条件的排序，实际的时间复杂度与数据的实际状况有关。

最好情况是最开始便有序，我们只需要执行一次大循环，复杂度为O(N)。

最差情况是将整个数组倒序排列一次，复杂度为O(N²)。

平均情况是指在大数状况下的平均期望复杂度。

在数据的实际状况对算法流程存在影响时，使用最差情况作为时间复杂度。

不过，我们可以利用主动打乱数据状况影响的方式。将复杂度易数学期望的方式表达(参考随机快排)。

对数器

对数器是用来测试代码正确性的，我们在找不到合适的oj系统测试自己的代码时，可以自己写一个对数器对代码进行测试。

设计对数器的一般步骤为：

1.有一个你要测的方法a； 自己写的方法

2.实现一个绝对正确即使复杂度不好的方法b； 系统自带方法即可

3.实现一个随机样本产生器；

4.实现比对的方法； 比对两个结果最后是否一致

5.把方法a和方法b比对很多次来验证方法a是否正确

6.如果有一个样本使得比对出错，打印样本分析是哪个方法出错

7.当样本数量很多时比对测试依然正确，可以确定方法a已经正确

实现对数器

其中1，2，4已经说了。6，7也没啥好说的。

3.实现一个随机样本产生器

/// 随机数组生成器

///

/// - Parameters:

/// - size: 最大长度

/// - value: 最大值

/// - Returns: 随机数组

func generateRandomArray(size : Int ,value : Int) -> [Int] {

var arr :[Int]

arr = Array.init()

for i in 0..

let item = Int(arc4random() % 10)*value/10

arr.append(item)

}

print(arr)

return arr

}

把方法a和方法b比对很多次来验证方法a是否正确

var checkOK = true

for i in 0..<10000 {

var arr1 = generateRandomArray(size: 5, value: 20)

var arr2 = arr1 //数组在swift里属于值类型，赋值动作会自动copy

let originalArr = arr1

arr1.sort()

heapSort(arr: &arr2)

if arr1 != arr2 {

checkOK = false

print(originalArr)

print(arr2)

break

}

}

print(checkOK ? "比对成功":"比对失败")

//打印

[0, 6, 2, 12, 18]

[0, 6, 12, 2, 18]

比对失败

错误的原始数据已经打印出来了，你就可以随意重现这个数据进行调试了。

var arr = [0, 6, 12, 2, 18];

print(arr)

heapSort(arr: &arr)

print(arr)

参考资料