引言：
搜集题目的难度是在简单级别和中级级别，也是面试常考的题目。题目的题解，使用的开发语言是 Swift。
因为题目的描述很长，以及有各种案例提示，为了不占篇幅，所以没有展示出来，大家可以直接通过题号查询，或者通过搜索关键字去查看题目的描述。
文章的写作顺序是：
1. 展示题号和以及题目的链接
2. 核心思想的讲述
3. 代码实现
最后本文提供的代码都是在LeetCode上提交通过的。
Author: JefferyYu
1. Sort Algorithm Implementation Questions(排序算法)
1. 冒泡排序
2. 选择排序
3. 插入排序
4. 快速排序
1.冒泡排序O( n2 )
1.1 核心思想：
每次选择最小的往上冒，发现比我小，就换位置
1.2 代码实现：
func bubbleSort(_ nums: inout [Int]) {
for i in 0..<nums.count {
for j in i+1 ..< nums.count {
if nums[j] < nums[i] {
let temp = nums[i]
nums[i] = nums[j]
nums[j] = temp
}
}
}
}- 1.
- 2.
- 3.
- 4.
- 5.
- 6.
- 7.
- 8.
- 9.
- 10.
- 11.
2.选择排序 O( n2 )
2.1 核心思想：
选择排序的意思就是：选好了，再换位置
具体的实现就是每次保存最小的那个下标，然后到最后再换一次即可
2.2 代码实现：
func selectionSort(_ nums: inout [Int]) {
for i in 0..<nums.count {
var min = i
for j in i+1 ..< nums.count {
if nums[j] < nums[min] {
min = j
}
}
let temp = nums[i]
nums[i] = nums[min]
nums[min] = temp
}
}- 1.
- 2.
- 3.
- 4.
- 5.
- 6.
- 7.
- 8.
- 9.
- 10.
- 11.
- 12.
- 13.
3. 插入排序 O( n2 )
3.1 算法思想
将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。
3.2 代码实现
func insertSort(_ nums: inout [Int]) {
for i in 1..<nums.count {
for j in (0..<i).reversed() {
if j > nums[i] {
nums.swapAt(j, j+1)
}
}
}
}- 1.
- 2.
- 3.
- 4.
- 5.
- 6.
- 7.
- 8.
- 9.
4. 快速排序 O( NLogN )
4.1 算法思想
快排的思想还是很有用的，就是把大于我的部分放在我的右边，小于我的部分放在我的左边。
具体的大家想看实现的详细的情况，可以看我写的这篇文章：一文读懂快速排序
4.2 代码实现
func quickSort(nums: inout [Int]) -> [Int] {
sort(nums: &nums, begin: 0, end: nums.count)
return nums
}
func sort(nums: inout [Int], begin: Int, end: Int) {
if end - begin < 2 { return }
var rBegin = begin; var rEnd = end
let mid = pivotIndex(nums: &nums, begin: &rBegin, end: &rEnd)
sort(nums: &nums, begin: begin, end:mid)
sort(nums: &nums, begin: mid + 1, end: end)
}
//【1个大数组被分割成了左边和右边2个数组】
// 将pivot的位置抛出来，作为递归的时候的左边数组的end和右边数组的begin
private func pivotIndex(nums: inout [Int], begin: inout Int, end: inout Int) -> Int {
let pivot = nums[begin]
end -= 1
while begin < end {
while begin < end {
if pivot < nums[end] {
end -= 1
}else {
nums[begin] = nums[end]
begin += 1
break
}
}
while begin < end {
if pivot > nums[begin] {
begin += 1
}else {
nums[end] = nums[begin]
end -= 1
break
}
}
}
//将轴点元素放到最终的位置, 此时begin和end是重合的。所以下面使用begin或者end都是可以的
nums[begin] = pivot
return begin
}- 1.
- 2.
- 3.
- 4.
- 5.
- 6.
- 7.
- 8.
- 9.
- 10.
- 11.
- 12.
- 13.
- 14.
- 15.
- 16.
- 17.
- 18.
- 19.
- 20.
- 21.
- 22.
- 23.
- 24.
- 25.
- 26.
- 27.
- 28.
- 29.
- 30.
- 31.
- 32.
- 33.
- 34.
- 35.
- 36.
- 37.
- 38.
- 39.
- 40.
- 41.
- 42.
- 43.
- 44.