引用链接：
剑指offer题库
算法之剑指offer题目总结
2019 iOS面试题大全---全方面剖析面试
2018 iOS面试题---算法相关
1、七种常见的数组排序算法整理(C语言版本)
2、2019 算法面试相关(leetcode)--数组和链表
3、2019 算法面试相关(leetcode)--字符串
4、2019 算法面试相关(leetcode)--栈和队列
5、2019 算法面试相关(leetcode)--优先队列
6、2019 算法面试相关(leetcode)--哈希表
7、2019 算法面试相关(leetcode)--树、二叉树、二叉搜索树
8、2019 算法面试相关(leetcode)--递归与分治
9、2019 算法面试相关(leetcode)--贪心算法
10、2019 算法面试相关(leetcode)--动态规划(Dynamic Programming)
11、2019 算法面试相关(leetcode)--动态规划之背包问题
引用链接：
MARK: - 算法
十大编程算法助程序员走上高手之路
十大经典排序算法
1、冒泡排序：从第一个开始，往后比较相邻元素，交换位置，不交换时结束
2、选择排序：选择最小的交换，最后交换到前面的位置
3、插入排序：与前面排好序的对比，插入到前面
4、希尔排序：分治算法，二分增量排序（二分后继续二分，直到只有两个元素）
5、归并排序：分治算法，递归左右两边的排序，最后合并
6、快速排序：选择基准元素，递归左右两边的排序
7、堆排序：二叉树排序
8、计数排序：每个桶只存储单一键值（适合整数）
9、桶排序：每个桶存储一定范围的数值
10、基数排序：根据键值的每位数字来分配桶，从个位开始，然后十位，百位...
数据结构与算法
关于时间/空间复杂度，名词解释：
n：数据规模
k："桶"的个数
Out-place：占用额外内存
In-place：占用常数内存，不占用额外内存
稳定性：排序后 2 个相等键值的顺序和排序之前它们的顺序相同
根据数据结构和算法思想的分类，《剑指 Offer》可以分为以下几种标签，可点击链接，查看题解（正在不断更新中）：
引用：全部题目都提供动画解题思路，不用担心看不懂！
- 链表
- 06 --- 从尾到头打印链表
- 18 --- 删除链表的节点
- 22 --- 链表中倒数第 K 个节点
- 24 --- 反转链表
- 35 --- 复杂链表的复制
- 52 --- 两个链表的第一个公共结点
- 栈 & 队列
- 09 --- 用两个栈实现队列
- 30 --- 包含 min 函数的栈
- 59II --- 队列的最大值
- 59I --- 滑动窗口的最大值
- 树
- 07 --- 重建二叉树
- 26 --- 树的子结构
- 27 --- 二叉树的镜像
- 28 --- 对称的二叉树
- 32I --- 从上往下打印二叉树
- 32I --- 从上往下打印二叉树II
- 32II --- 从上往下打印二叉树III
- 34 --- 二叉树中和为某一值的路径
- 37 --- 序列化二叉树
- 54 --- 二叉搜索树的第 K 大节点
- 55I --- 二叉树的深度
- 55II ---平衡二叉树
- 68I --- 二叉搜索树的最近公共祖先
- 68II --- 二叉树的最近公共祖先
- 堆
- 40 --- 最小的 K 个数
- 41 --- 数据流中的中位数
- 哈希表
03 --- 数组中重复的数字
48 --- 最长不含重复字符的子字符串
50 --- 第一个只出现一次的字符- 动态规划
14I --- 剪绳子
14II --- 剪绳子II
19 --- 正则表达式匹配
42 --- 连续子数组的最大和
47 --- 礼物的最大值
63 --- 股票的最大利率
二分查找
01 --- 旋转数组的最小数字
53I --- 在排序数组中查找数字 I
53II --- 0 ~ n-1 中缺失的数字
回溯算法
38 --- 字符串的排列
分治算法
25 --- 合并两个排序的链表
36 --- 二叉搜索树与双向链表
排序
45 --- 把数组排成最小的树
位运算
15 --- 二进制中 1 的个数
39 --- 数组中出现次数超过一半的数字
计数排序
假设有一个待排序的列表 [4, 2, 2, 8, 3, 3, 1]，数据的范围是 1 到 8，计数排序的过程如下：
统计频率：
初始化计数数组 count，大小为 9（范围 0-8）。
遍历列表，统计每个元素的出现次数：
初始 count[element] = 0
count[element] = count[element] + 1
count[element] = 0 + 1，即：
for element in array { //存在的添加，不存在的始终为默认值 0
count[element] += 1 //将countArray数组中索引为 element 的值加 1。
}
count[0] = 0
count[1] = 1
count[2] = 2
count[3] = 2
count[4] = 1
count[5] = 0
count[6] = 0
count[7] = 0
count[8] = 1
计数数据次序：[0, 1, 2, 3, 4, 5, 6, 7, 8]。
计数数组分布：[0, 1, 2, 2, 1, 0, 0, 0, 1]。
累加频率：
将计数数组中的值累加，得到每个元素的最终位置：
countArray[i] = countArray[i] + countArray[i-1]
元素位置依次增加：在前面的位置数+当前的个数
count[0] = 0
count[1] = 1 + 0 = 1
count[2] = 2 + 1 = 3
count[3] = 2 + 3 = 5
count[4] = 1 + 5 = 6
count[5] = 0+ 6 = 6
count[6] = 0+ 6 = 6
count[7] = 0+ 6 = 6
count[8] = 1 + 6 = 7
累加后的计数数组：[0, 1, 3, 5, 6, 6, 6, 6, 7]。
放置元素：
初始化结果数组 output，count大小为 7。
遍历原始列表，根据计数数组中的位置信息，将元素放入结果数组：
原列表 [4, 2, 2, 8, 3, 3, 1]
位置i： i = count[4] - 1 = 6-1 = 5
位置i： i = count[2] - 1 = 3-1 = 2
位置i： i = count[2] - 1 = 2-1 = 1 这里的 count[2] 替换上面的结果
位置i： i = count[8] - 1 = 7-1 = 6
...
arr[5] = 4
arr[2] = 2
arr[1] = 2
arr[6] = 8
...
元素 4：count[4] = 6，放入 output[5]，count[4] -= 1。
元素 2：count[2] = 3，放入 output[2]，count[2] -= 1。
元素 2：count[2] = 2，放入 output[1]，count[2] -= 1。
元素 8：count[8] = 7，放入 output[6]，count[8] -= 1。
元素 3：count[3] = 5，放入 output[4]，count[3] -= 1。
元素 3：count[3] = 4，放入 output[3]，count[3] -= 1。
元素 1：count[1] = 1，放入 output[0]，count[1] -= 1。
结果数组：[1, 2, 2, 3, 3, 4, 8]。
//计数排序
func countingSort(_ array: [Int]) -> [Int] {
guard array.count > 0 else { return array }
// 找到数组中的最大值
// 创建一个计数数组，大小为最大值 + 1
let maxElement = array.max() ?? 0
var countArray = [Int](repeating:0, count: maxElement + 1)
// 统计每个元素的出现次数：初始 countArray[element] = 0
for element in array {
countArray[element] += 1 //意思是：将countArray数组中索引为 element 的值加 1。
}
// 累加计数数组，确定每个元素的最终位置
for i in 1..<countArray.count {
countArray[i] += countArray[i-1]
}
// 创建一个临时数组存储排序结果
// 从后向前遍历原数组，将元素放到正确的位置
var sortedArray = [Int](repeating: 0, count: array.count)
for element in array.reversed() {
countArray[element] -= 1
sortedArray[countArray[element]] = element
}
return sortedArray
}
func test_counting() {
//示例使用
let array = [4, 2, 2, 8, 3, 3, 1]
let sortedArray = countingSort(array)
print("排序后的数组: \(sortedArray)")
}
