算法的一点一滴
最近急于强补算法知识去面大公司，经过自己不自量力地在 leetcode 上做了几题算法题后，终于静下心来。 急功近利的焦躁的样子真是太low了，不会就一点点学，希望以后能更好地调整自己心态。
从排序入门
仿佛所有算法教程都从排序讲起。虽然现在在编码时都是调个 api 就完事了，但是其中的思想还是值得学习研究的。
[8,2,3,7,5,6,4,1],将该数组从小到大排列。
选择排序
肉眼一看就知道，1最小，就先把1排出来 -> [1]
然后是2 -> [1,2]
…
最后排序完成
第 1 次找了 n-1 次，第 2 次找了 n-2 次，第 3 次找了 n-3 次…
共 n(n-1)/2 次
代码示例:
func choseSorting(nums: [Int]) -> [Int] {
guard nums.count > 0 else {
return []
}
var temp = nums
var result = [Int]()
while temp.count != 0 {
var m = temp.first!
var mi = 0
for i in 0..<temp.count {
if m > temp[i] {
m = temp[i]
mi = i
}
}
result.append(m)
temp.remove(at: mi)
}
return result
}
插入排序
请在脑海里想象扑克牌理牌的情形! 先随机取一个数扔到一个新的数组，比如取了2 -> [2]
再从剩下的数中随机取一个数，按指定的顺序插入，比如取了7 -> [2,7]
再从剩下的数中随机取一个数，按指定的顺序插入，比如取了4 -> [2,4,7]
再从剩下的数中随机取一个数，按指定的顺序插入，比如取了8 -> [2,4,7,8]
…
最后排序完成
第 1 次比较了 0 次，第 2 次比较了 1 次，第 3 次最多需要比较 2 次，第 4 次最多需要比较 3 次…
共 n(n-1)/2 次
代码示例:
func insertSorting(nums: [Int]) -> [Int] {
guard nums.count > 0 else {
return []
}
var temp = nums
var result = [Int]()
result.append(nums.first!)
temp.removeFirst()
while temp.count != 0 {
let n = temp.first!
for i in 0..<result.count{
if n < result[i] {
result.insert(n, at: i)
break
}
result.append(n)
}
temp.removeFirst()
}
return result
}
冒泡排序
[8,2,3,7,5,6,4,1]
首先比较第一个数字跟第二个数字 -> [2,8,3,7,5,6,4,1]
然后比较第二个数字跟第三个数字 -> [2,3,8,7,5,6,4,1]
然后比较第三个数字跟第四个数字 -> [2,3,7,8,5,6,4,1]
然后比较第四个数字跟第五个数字 -> [2,3,7,5,8,6,4,1]
…
一次排序后，8就会到达数组的最后一个位置
然后再对前面的数字同样的方式进行一次
第 1 次排了 n-1 次，第 2 次排了 n-2 次，第 3 次排了 n-3 次…
共 n(n-1)/2 次
代码示例:
func bubbleSorting(nums: [Int]) -> [Int] {
guard nums.count > 0 else {
return []
}
var temp = nums
var i = temp.count - 1
while i != 0 {
for j in 0..<i {
if temp[j] > temp[j + 1]{
let t = temp[j]
temp[j] = temp[j + 1]
temp[j + 1] = t
}
}
i -= 1
}
return temp
}
快速排序
待研究
