本文只是自己的笔记，并不具有任何指导意义。
代码的初衷是便于了解，网上大神优化过的代码很多，也不建议在项目中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..<N+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×N3+B×N2+C×N。当N趋近于无穷大时，三次方的影响远大于二次方以及一次方。当然也大于常数项A的影响。
所以表达式f(N)=N3。
时间复杂度为O(N)=O(f(N))=O(N3)
领附一张图方便了解高阶项在基数变大时的变化：
评价一个算法流程的好坏，先看时间复杂度的指标，而后再分
析不同数据样本下的实际运行时间，也就是常数项时间。
在冒泡排序过程中会将数组分成两部分，前半部分是无序的数列，后半部分为有序的数列。无序数列中不断的将其中最大的值往有序序列中冒泡，泡冒完后，我们的序列就创立好了。
具体操作上，假如相邻的两个数字前者较大，则将二者交换，到达无序数组边界则中止。
func bubbleSort(arr: inout [Int]) { if arr.count < 2 { return } for i in 0..<arr.count { for j in 0..<arr.count - (i+1) { if arr[j] > arr[j+1] { let temp = arr[j] arr[j] = arr[j+1] arr[j+1] = temp } } }}时间复杂度O(N2)，额外空间复杂度O(1)。
时间复杂度的来源f(N) = N +( N -1) + (N-2) + ...+ 2 + 1 为一个等差数列。前N项和的通用公式为:N*(N-1)/2化简后f(N)=N2。
经典的冒泡排序，无论数组能否已经有序。都会一次次的遍历，从这一点上我们可以进行改进
func bubbleSort2(arr: inout [Int]) { if arr.count < 2 { return } var swapped = false //记录能否有交换动作的变量 for i in 0..<arr.count { swapped = false for j in 0..<arr.count - (i+1) { 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..<arr.count { minIndex = i for j in i+1..<arr.count { //循环从i+1开始，也就是无序数组的第二位开始 minIndex = arr[j]<arr[minIndex] ? j:minIndex //比对当前位置与记录位置的值，记录其中最小的。 } arr.swapAt(i, minIndex) //将无序数组的第一位与最小一位交换 }}选择排序本身没有什么可改进的，但是我们可以左右开弓。
将序列分成三个部分，前段有序部分，中段无序部分，后台有序部分。
每次循环，将最大值与最小值分别置入前后两个有序序列。
func selectionSort2(arr : inout [Int]) { if arr.count<2 { return } var minIndex :Int var maxIndex :Int for i in 0..<arr.count { minIndex = i maxIndex = i if i+1 >= arr.count - i { return // 因为这一步的存在，实际上会在i=arr.count/2处结束循环 } for j in i+1..<arr.count - i { //循环从i+1开始，也就是无序数组的第二位开始。并且在后台有序序列的前一位中止 minIndex = arr[j]<arr[minIndex] ? j:minIndex //比对当前位置与记录位置的值，记录其中最小的。 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(N2)，但实际上的表达式系数比经典选择排序不止缩小了1/2。
基本思想也是前半部分为序的数列，后半部分是无序的数列。无序数列不断将其首位元素推给有序数列，有序数列将其插入适当的位置。
具体操作上，会从有序数列的尾部依次向前比较，若前位大于后位则进行交换。
func insertionSort(arr : inout [Int]) { if arr.count<2 { return } for i in 1..<arr.count { //无序数组从i=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(N2)。
平均情况是指在大数状况下的平均期望复杂度。
不过，我们可以利用主动打乱数据状况影响的方式。将复杂度易数学期望的方式表达(参考随机快排)。
对数器是用来测试代码正确性的，我们在找不到合适的oj系统测试自己的代码时，可以自己写一个对数器对代码进行测试。
1.有一个你要测的方法a； 自己写的方法
2.实现一个绝对正确即便复杂度不好的方法b； 系统自带方法就可
3.实现一个随机样本产生器；
4.实现比对的方法； 比对两个结果最后能否一致
5.把方法a和方法b比对很屡次来验证方法a能否正确
6.假如有一个样本使得比对出错，打印样本分析是哪个方法出错
7.当样本数量很多时比对测试仍然正确，可以确定方法a已经正确
其中1，2，4已经说了。6，7也没啥好说的。
/// 随机数组生成器////// - Parameters:/// - size: 最大长度/// - value: 最大值/// - Returns: 随机数组func generateRandomArray(size : Int ,value : Int) -> [Int] { var arr :[Int] arr = Array.init() for i in 0..<Int(arc4random() % 10) * size / 10 { let item = Int(arc4random() % 10)*value/10 arr.append(item) } print(arr) return arr}var checkOK = truefor 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)左神牛课网算法课
时间复杂度和空间复杂度的简单讲解
选择排序及改进方法