1.冒泡排序
时间复杂度:O(n^2)
1.1初级
// 冒泡排序-初级
func bubbleSort0(list: inout [Int]) {
for i in 0..<list.count { // 头部开始遍历
var j = i + 1
while j < list.count { // j=i的下一位置开始遍历
let a = list[i]
let b = list[j]
if a > b { // 比较的值是i和j
list.swapAt(i, j) // 交换指定下标的两个元素
}
j += 1
}
}
}
image.png
1.2正宗冒泡排序
// 冒泡排序-正宗
func bubbleSort1(list: inout [Int]) {
for i in 0..<list.count { // 头部开始遍历
var j = list.count - 2
while j >= i { // 遍历从j=倒数第二个元素，到i
let a = list[j]
let b = list[j + 1]
if a > b { // 比较的值是下标j和j+1
list.swapAt(j + 1, j)
}
j -= 1
}
}
}
image.png
1.3冒泡排序优化
问题:排序过程中,如果数据中有部分有序,那么就会出现很多没必要的比较.例如:[2,1,3,4,5,6,7,9,8],只有最后两位9和8的顺序不对.使用上述的正宗冒泡排序就会有很多没必要的操作.
先看看优化的代码,如下:
// 冒泡排序-优化
func bubbleSort2(list: inout [Int]) {
var flag = true // 增加一个标志，判断是否已经排序完成。初始化为true。
for i in 0..<list.count {
if flag { // 判断flag状态，false状态：说明已经排序完成
flag = false // 改变flag状态为false
var j = list.count - 2
while j >= i {
let a = list[j]
let b = list[j + 1]
if a > b {
list.swapAt(j, j+1)
flag = true // 有交换，说明排序未完成
}
j -= 1
}
} else {
return
}
}
}
- 增加
flag变量,用来表示上次循环体中是否有元素交换位置. - 有交换flag = true,没有则为false
- 如果为false,代表已经排序完成
image.png
- 图中可以看出执行次数上有优化
2.选择排序
选择排序:顾名思义,先选择出最大值或者最小值,放入到指定位置
时间复杂度:O(n^2)
// 选择排序
func selectSort(list: inout [Int]) {
for i in 0..<list.count { // 全量循环
var min = i // 初始当前位置为最小值
var j = i + 1
while j < list.count { // 遍历后续元素，找到最小值的下标
let a = list[min]
let b = list[j]
if a > b {
min = j
}
j += 1
}
if min != i { // 最小值的小标与当前下标如果不等，则进行位置交换
list.swapAt(i, min)
}
}
}
image.png
3.插入排序
时间复杂度:O(n^2)
3.1插入排序-普通
将当前遍历到的元素插入到前面已经排好顺序的指定位置中
// 插入排序
func insertSort(list: inout [Int]) {
var i = 1
while i < list.count { // 从第二个元素开始遍历
let a = list[i]
let b = list[i-1]
if a < b { // 当前的值与前一个元素的值比较
var j = i - 1
while j >= 0 && list[j] > a { // 找到已经排序好中的位置，并依次后移元素
list[j+1] = list[j]
j -= 1
}
list[j+1] = a // 在找到的位置中赋值
}
i += 1
}
}
image.png
3.2插入排序-希尔排序
希尔排序的特点是修改了比较元素之间的步长距离，之前的排序都是临近的两个元素进行比较，而希尔排序是可以让编写者根据需求自行修改比较步长。这样有一个优点，根据步长的不同与业务需求，会得到不同的时间复杂度。
// 希尔排序
func shellSort(list: inout [Int]) {
var step = list.count // 初始化步长
repeat {
step = step / 3 // 步长设置为总长度的1/3
var i = step
while i < list.count {
if list[i] < list[i - step] { // 跨步长的元素之间比较
let temp = list[i]
var j = i - step
while j >= 0 && list[j] > temp {
list[j + step] = list[j]
j -= step
}
list[j + step] = temp
}
i += 1
}
} while step > 1
}
image.png
4.堆排序
时间复杂度:O(nlogn)
利⽤堆(假设我们选择小顶堆)进⾏排序的算法.
- 大顶堆:根的值大于所有子结点.
- 小顶堆:根的值小于所有子结点.
/// 堆调整
/// - Parameters:
/// - list: 列表
/// - index: 当前的下标
/// - count: 需要调整的列表长度
func heapAdjust(list: inout [Int], index: Int, count: Int) {
var index = index
let temp = list[index] // 记录当前父结点的值
var i = 2 * index + 1 // 找到二叉树的左孩子
while i < count {
if i < (count - 1) && list[i] < list[i+1] { // 左孩子和右孩子取值小的下标
i += 1
}
if temp >= list[i] { // 如果左右孩子都小于等于父结点，则退出循环
break
}
// 交换结点的值，并记录下标
list[index] = list[i]
index = i
i = i * 2 + 1 // 将子结点作为父结点，继续循环
}
list[index] = temp
}
func heapSort(list: inout [Int]) {
var i = list.count / 2
while i >= 0 {
heapAdjust(list: &list, index: i, count: list.count) // 堆调整方法
i -= 1
}
i = list.count - 1
while i >= 0 { // 全量循环
list.swapAt(0, i) // 交换最后一个元素
heapAdjust(list: &list, index: 0, count: i) // 堆调整,长度为需要调整的列表长度
i -= 1
}
}
image.png
5.快速排序
通过⼀趟排序将待排序记录分割成独⽴的两部分; 其中⼀部分记录的关键字均为另⼀部分记录的关键字⼩,则可分别对两部分记录继续进⾏排序,以达到整个排序有序的⽬的。
时间复杂度:O(n^2)
/// 找到标志位下标
/// - Parameters:
/// - list: 列表数组
/// - low: 低位下标
/// - high: 高位下标
/// - Returns: 标志位下标
func partition(list: inout [Int], low: Int, high: Int) -> Int {
var low = low
var high = high
let key = list[low] // 初始化标志位的值为低位下标中的值
while low < high { // 低位到高位遍历
while low < high && list[high] > key { // 从后往前找小于key的位置
high -= 1
}
list.swapAt(low, high) // 找到后交换
while low < high && list[low] < key { // 从前往后找大于key的位置
low += 1
}
list.swapAt(low, high) // 找到后交换
}
return low // 返回找到的标志位下标
}
/// 快排的递归方法
/// - Parameters:
/// - list: 列表数组
/// - low: 低位下标
/// - high: 高位下标
func qSort(list: inout [Int], low: Int, high: Int) {
if low < high { // 递归出口判断
let index = partition(list: &list, low: low, high: high) // 找到标志位下标
qSort(list: &list, low: low, high: index - 1) // 递归低于标志位的部分
qSort(list: &list, low: index + 1, high: high) // 递归高于标志位的部分
}
}
/// 快排入口方法
/// - Parameter list: 列表数组
func quickSort(list: inout [Int]) {
qSort(list: &list, low: 0, high: list.count - 1)
}
image.png
6.归并排序
归并排序(Merging Sort) 就是利⽤归并的思想实现排序⽅法. 它的原理是假设初始序
列含有n个记录,则可以看成n个有序的⼦序列. 每个⼦序列的⻓度为1,然后两两合并.得 到[n/2]个⻓度为2或1的有序⼦序列, 再两两归并.......如此重复,直到得到⼀个⻓度为n
的有序序列为此. 这种排序⽅法称为2路归并排序。
时间复杂度:O(nlogn)
空间复杂度:O(n)
// 归并排序
/// 合并方法，将list中的数据依靠分成两段[low, mid]和[mid + 1, high]。按照值从小到大的顺序，存入到outList中
/// - Parameters:
/// - sList: 源数组数据
/// - outList: 输出数组数据
/// - low: 低位下标
/// - mid: 中间位下标
/// - high: 高位下标
func merge(sList: [Int], outList: inout [Int], low: Int, mid: Int, high: Int) {
var i = low
var j = mid + 1
var k = low
while i <= mid && j <= high { // 遍历数组中的两段，获取比较小的值
if sList[i] < sList[j] { // 前段中的值小
outList[k] = sList[i] // 加入到输出数组中
i += 1
} else { // 后段中的值小
outList[k] = sList[j] // 加入到输出数组中
j += 1
}
k += 1
}
if i <= mid { // 前端还有剩余值，依次加入到输出数组中
var l = 0
while l <= mid - i {
outList[k+l] = sList[i+l]
l += 1
}
}
if j <= high { // 后端还有剩余值，依次加入到输出数组中
var l = 0
while l <= high - j {
outList[k+l] = sList[j+l]
l += 1
}
}
}
/// 拆分list方法（递归）
/// - Parameters:
/// - sList: 源数组
/// - outList: 输出数组
/// - low: 低位下标
/// - high: 高位下标
func mSort(sList: [Int], outList: inout [Int], low: Int, high: Int) {
if low == high { // 递归出口
outList[low] = sList[low]
} else {
let mid = (low + high) / 2 // 取中间值
var tList = Array.init(repeating: 0, count: 9)
mSort(sList: sList, outList: &tList, low: low, high: mid) // 递归拆分数组，低位到中间位
mSort(sList: sList, outList: &tList, low: mid + 1, high: high) // 递归拆分数组，中间位到高位
merge(sList: tList, outList: &outList, low: low, mid: mid, high: high) // 合并方法
}
}
func mergeSort(list: inout [Int]) {
mSort(sList: list, outList: &list, low: 0, high: list.count - 1)
}
image.png
7.时间/空间复杂度表格
image.png
