插入排序
思想: 从无序区中选择一个数据插入到有序区中
代码:
// 插入排序
func insertSort(array: inout [Int]) -> Void{
if array.count < 2 { // 数组长度小于 2 则直接返回
return
}
for i in 1..<array.count { // 遍历数组, 从 1 开始是因为默认首位为有序区
let temp = array[i] // 当前待插入的数据
var j = i - 1 // 待插入数据位的前一位
while j >= 0 && temp < array[j] { // 移位操作, 将比 temp 大的都往后移位
array[j + 1] = array[j];
j -= 1
}
array[j + 1] = temp; // 空出的位置插入 temp
}
}
选择排序
思想: 从无序区依次选择最小的一位插入到有序区的最后一位
代码:
func selectSort(array:inout [Int]) -> Void {
if array.count < 2 { // 数组长度小于 2 则直接返回
return
}
for i in 0..<(array.count - 1) {
var min = i // 有序区的最后一个位置
for j in (i + 1)...(array.count - 1) { // 注意边界, 是遍历到最后一个
if array[min] > array[j] {
min = j; // 找到无序区中最大值的下标
}
}
if i != min { // 防止相同位置交换操作(swap 函数会报错)
swap(&array[min], &array[i])
}
}
}
冒泡排序
思想: 每次将无序区中相邻两数比较, 前者比后者大则交换位置, 类似于较大值慢慢地从底部冒泡上去
代码:
func bubbleSort(array:inout [Int]) -> Void {
if array.count < 2 { // 数组长度小于 2 则直接返回
return
}
for i in 0..<(array.count - 1) { // 外层循环为 数组长度 - 1
for j in 0..<(array.count - 1 - i) { // 内层循环为 外层循环 - i
if array[j] > array[j + 1] { // 冒泡操作
swap(&array[j], &array[j + 1])
}
}
}
}
快速排序
思想: 将原问题分解为若干个规模更小但结构与原问题相似的子问题
代码:
最容易理解版本
取数组末位的中值, 比中值小的排左边, 其余则排右边, 同理递归操作左右数组。缺点是需要辅助空间。
func quickSort(array:[Int]) -> [Int]{
if array.count < 2 {
return array
}
var left = [Int]() // 比中值小的数组
var right = [Int]() // 比中值大的数组
let pivot = array[array.count - 1] // 取末位为中值
for i in 0..<(array.count - 1) {
if array[i] < pivot {
left.append(array[i]) // 比中值小的数据插入左数组
}else{
right.append(array[i]) // 比中值大的数据插入右数组
}
}
var leftResult = quickSort(array: left) // 对左数组递归处理
leftResult.append(pivot) // 处理完后数组接回中值
let rightResult = quickSort(array: right) // 对右数组递归处理
leftResult.append(contentsOf: rightResult) // 左数组接回右数组
return leftResult
}
经典快排
不需要辅助空间
func partiton( array:inout [Int], low: Int, high: Int) -> Int {
if low > high {
return -1
}
var left = low, right = high // 设置左右起点
let x = array[low] // 设置基准
repeat{
while array[right] > x && left < right{ // 从右往左找, 找出比基准小的数
right -= 1
}
while array[left] <= x && left < right{ // 从左往左找, 找出比基准大的数
left += 1
}
if left < right {
swap(&array[left], &array[right]) // 交换操作
}
} while left < right
if low != right { // 防止交换位置相同, swap 函数会出错
swap(&array[low], &array[right]) // 将中值和左边有序区的的最后一个数交换
}
return right // 返回中值位置
}
第二种划分
func partiton2( array:inout [Int], low: Int, high: Int) -> Int {
let pivot = array[high] // 选取数组最后一个元素为中值
var j = low
for i in low..<high {
if array[i] < pivot { // 比中值小
if i != j {
swap(&array[i], &array[j])
}
j += 1
}
}
if high != j {
swap(&array[high], &array[j])
}
return j
}
func quickSort ( array:inout [Int], low: Int, high: Int) -> Void {
if low < high {
let pivot = partiton(array: &array, low: low, high: high)
quickSort(array: &array, low: low, high: pivot - 1)
quickSort(array: &array, low: pivot + 1, high: high)
}
}
合并排序
思想: 对两个子数组递归排序, 然后将两个子数组合并为一个有序数组
代码:
func merge( array:inout [Int], low:Int, mid:Int, high:Int){
var tempArray = Array<Int>()
var indexA = low
var indexB = mid
while indexA < mid && indexB < high {
if array[indexA] < array[indexB]{
tempArray.append(array[indexA])
indexA += 1
}else{
tempArray.append(array[indexB])
indexB += 1
}
}
while indexA < mid {
tempArray.append(array[indexA])
indexA += 1
}
while indexB < high{
tempArray.append(array[indexB])
indexB += 1
}
var index = 0
for item in tempArray{
array[low + index] = item
index += 1
}
}
func mergeSort(array:inout [Int], low: Int, high: Int) -> Void {
if low + 1 < high {
let mid = (low + high) / 2
mergeSort(array: &array, low: low, high: mid)
mergeSort(array: &array, low: mid, high: high)
merge(array: &array, low: low, mid: mid, high: high)
}
}
未完待续...
