|
目录
快速排序
归并排序
堆排序
基础知识：
堆的性质：
实现步骤
1、维护堆节点方法
2、建堆
3、排序堆
4、整合
快速排序
时间复杂度O( Nlog2N)）
1、选择基准点P，大的放在右边，小的放在左边。
2、递归调用左边，右边
func quickSorted (_ nums: inout [Int], _ left: Int, _ right: Int) {
if left >= right {
return ;
}
var l = left
var r = right
let pivot = nums[l]
while l < r {
while nums[r] >= pivot && l < r {//以l为基准点就要先从r处先遍历
r -= 1
}
nums[l] = nums[r]//l的位置付给了pivot，所有可以把r的值放在l了
while nums[l] <= pivot && l < r {
l += 1
}
nums[r] = nums[l]//同理可以把l的位置放在r处，因为r的数字已经放在上一个了处
}
// 此时 l 等于中间位置 （可能等于 r）
nums[l] = pivot //pivot的位置已经a安排好了
quickSorted(&nums, left, l - 1)
quickSorted(&nums, l + 1, right)
}
归并排序
时间复杂度O( N logN）
先分治，再合并
func mergeSorted(_ nums: inout [Int]) { //先分治，再合并
let length = nums.count - 1
var temp = Array<Int>(repeating: 0, count: nums.count) //临时数组
mergePass(&nums, &temp, 0, length)
}
//分治
func mergePass(_ nums: inout [Int], _ temp: inout [Int], _ left: Int , _ right: Int) {
if left < right { //元素数据大于 1
let mid = (right + left) / 2
print ("left == :\(left), mid = \(mid), right = \(right) ")
//递归划分左半区
mergePass(&nums, &temp, left, mid)
//递归划分右半区
mergePass(&nums, &temp, mid + 1, right)
merge(&nums, &temp, left, mid, right)
}
}
//合并已经排序的部分
func merge(_ nums: inout [Int], _ temp: inout [Int], _ left:Int, _ mid: Int, _ right: Int ) {
var lP = left //左半区为合并的元素
var rP = mid + 1 //右半区为合并的第一个元素
var pos = left //临时数组的元素下标
//合并
while lP <= mid && rP <= right {
if nums[lP] < nums[rP] {
temp[pos] = nums[lP]
pos += 1
lP += 1
} else {
temp[pos] = nums[rP]
pos += 1
rP += 1
}
}
// 合并剩余部分
while lP <= mid {
temp[pos] = nums[lP]
pos += 1
lP += 1
}
while rP <= right {
temp[pos] = nums[rP]
pos += 1
rP += 1
}
//将排序好的序列复制回原数组
var left = left
while left <= right {
nums[left] = temp[left]
left += 1
}
}
堆排序
时间复杂度O( N logN）不稳定。
基础知识：
堆：一种特殊的树。 大顶堆： 根节点比 左右子节点大。 小顶堆： 根节点比 左右子节点小
堆的性质：
??????????????1、下标为i 的节点的父节点的下标为：（i-1）/2
? ? ? ? ? ? ? 2、下标为i 的父亲节点，左孩子下标为 i*2 + 1
? ? ? ? ? ? ? 3、下标为i 的父亲节点，左孩子下标为 i*2 + 2
实现步骤
? ? ? ? ?1、实现堆节点调整 O(logN)
? ? ? ? ? 2、 建堆? 时间复杂度：O（n）
? ? ? ? ? 3、 移除第一个元素。然后调整堆。
? ? ? ? ? 4、 递归3 完成
1、维护堆节点方法
????????思路 ：1、找到维护点的左右子节点。把最大的放在根节点。
? ? ? ? ? ? ? ? ? ? ??2、 如果根与子节点有交互，则需要递归交换，子节点的所有子节点
//维护堆节点 :nums:堆数组（需要维护）， l：堆数组的长度， n：维护的节点在堆数组中的下标. O(logN)
func heapVerify(_ nums: inout [Int], _ l: Int, _ n: Int) { ///
var largest = n
let lSon = 2*n + 1 //堆的子节点在数组中的位置和父亲节点在数组中位置的关系
let rSon = 2*n + 2
//两次比较找出最大的 三者中最大的数字位置，放在Largest
if lSon < l && nums[largest] < nums[lSon] {
largest = lSon
}
if rSon < l && nums[largest] < nums [rSon] {
largest = rSon
}
if largest != n {
nums.swapAt(largest, n)
heapVerify(&nums, l, largest) //因为交换后的s位置已经放在了 largest里了
}
}
2、建堆
func buildHeap(_ nums: inout [Int]) {
let n = nums.count
var i = n/2 - 1 //从堆的最后一个有子节点的元素开始。即数组最后一个元素n-1 => 的父节点为:((n-1)-1)/2
while i >= 0 {
heapVerify(&nums, n, i)
i -= 1
}
print("建堆为：\(nums)")
}
3、排序堆
//排序堆
func sortHeap(_ nums: inout [Int] ) {
var i = nums.count - 1
while i > 0 {
nums.swapAt(i, 0) //大顶堆最大元素在堆顶。把最大元素移到堆尾部
heapVerify(&nums, i, 0) //维护堆除去堆底（最大）元素后的，堆顶元素的性质
i -= 1
}
}
4、整合
其实2、3 可以放在一起。
func heapSorted(_ nums: inout [Int]) {
buildHeap(&nums)
sortHeap(&nums)
}
总结
? ? ? ? 面试中考到的频率还是比较高的，也是easy的算法题。以上三种排序必须毫无卡顿，毫无差错的撸出来才行。每天没事的时候写一下练个手，可以看最快多长时间写完成。与君共勉
|