排序（Sort）是计算机程序设计中十分常见且重要的操作。是将一个数据元素的序列，重新排列成一个按关键字有序的序列。最近学习算法，从最基础的排序开始，记录一下。简单温习下最基础的三类算法：选择，冒泡，插入。
冒泡排序
冒泡排序（Bubble Sort）的基本思想是，对相邻的元素进行两两比较，顺序相反则进行交换，这样，每一趟会将最小或最大的元素“浮”到顶端，最终达到完全有序
冒泡排序示意图
在代码实现中，为了避免不必要的比较，可以设置标志位，如果某一趟执行完毕，没有做任何一次交换操作，则待排序列已经有序，排序已经完成。冒泡排序每一趟找到最大值，所以外层循环只需要到n-1即可（最后一个必然是最小的）。内层循环每次比较都是除去 数组最右边已经有序的部分。
// 冒泡排序swift
public func bubbleSort(array: inout [Int]) {
let count = array.count
for i in 0..<count-1 {
/*设定一个标记，若为true，则表示此次循环没有
进行交换，则待排序列已经有序，排序已然完成。*/
var flag = true
for j in 0..<count-1-i {
if array[j] > array[j+1] {
swap(&array[j], &array[j+1])
flag = false
}
}
if flag {
break
}
}
}
时间复杂度：如果初始序列就是有序的（最好情况），仅需n-1次比较就可完成。如果初始序列是反序的，需要进行n-1趟排序。每趟排序要进行n-i次关键字的比较(1≤i≤n-1)，且每次比较都必须移动记录来达到交换记录位置。在这种情况下，比较次数为 n-1+n-2+...+1=n(n-1)/2，因此冒泡排序时间复杂度为$ O(n^2) $。
选择排序
选择排序（Selection Sort）基本思想是：每一趟在n-i+1(i=1,2,...,n-1)个记录中选择选取最小的记录作为有序序列中第i个元素。
在代码实现中，可以通过变量记录每一趟的最小值，每一趟循环完毕之后，最后与位置i交换。代码比较简单明了，外层循环从0到n-1，内层循环假设位置i为最小值，所以比较直接从i+1的位置开始。
// 选择排序swift
public func selectionSort(array: inout [Int]) {
let count = array.count
for i in 0..<count-1 {
// 选择出最小的数
var minIndex = i
for j in i+1..<count {
if array[j] < array[minIndex] {
minIndex = j
}
}
//进行交换，如果minIndex发生变化，则进行交换
if i != minIndex {
swap(&array[i], &array[minIndex])
}
}
}
时间复杂度：
选择排序过程中，所需要进行记录移动的操作较少，但是，无论记录初始化排列如何，需要进行关键字的比较次数相同，均为n(n-1)/2，因此，选择排序的时间复杂度为$ O(n^2) $
直接插入排序
直接插入排序基本思想是将一个记录插入到已排好序的有序序列中，从而得到一个新的，记录数增1的序列。
直接插入排序示意图
算法代码实现，从示意图上，待插入元素不断与前面元素进行比较，交换位置，直到合适的位置。
其实每次交换是并不是必须的。可以用变量value 记录将待插入元素，需要交换元素的时候，不交换元素，而是将更大的元素向右移动一个位置，最后value赋值到正确位置即可，减少交换次数，代码如下。
// 插入排序swift
public func insertSort(array: inout [Int]) {
let count = array.count
for i in 1..<count {
let value = array[i]
var j = i
while j > 0 && array[j-1] > value {
array[j] = array[j-1]
j -= 1
}
array[j] = value
}
}
直接插入排序在最好情况下，需要比较n-1次，无需交换元素，时间复杂度为$ O(n) $;在最坏情况下，时间复杂度依然为$ O(n^2) $，但是总体来说插入排序比上面两种排序更优，主要原因大概有两点，插入排序与哦
总结
上面三种最基本的算法（选择，冒泡，插入），这三种排序算法的时间复杂度均为$ O(n^2) $。
其实排序算法已经有像快速排序，堆排序这种时间复杂度为 $ n\log(n) $的排序，还有必要学习简单排序算法么？当然有必要，学习简单排序的原因，简单排序算法比较基础，编码上比较简单，可以加深对排序算法的理解和了解。更重要的是高级复杂的排序也是从简单排序中演化出来的，而且简单排序在规模较小的时候，实际速度并不比快速排序慢。
后续会接着写更复杂一些的排序算法如堆排序，快速排序，都会在github上更新，希望关注，有问题可以指出。
参考
- 数据结构与算法分析
- 算法导论
网友评论