LeetCode初中级算法题解：排序算法介绍篇
这是无量测试之道的第228篇原创
引言：
搜集题目的难度是在简单级别和中级级别，也是面试常考的题目。题目的题解，使用的开发语言是 Swift。
因为题目的描述很长，以及有各种案例提示，为了不占篇幅，所以没有展示出来，大家可以直接通过题号查询，或者通过搜索关键字去查看题目的描述。
文章的写作顺序是：
1. 展示题号和以及题目的链接
2. 核心思想的讲述
3. 代码实现
最后本文提供的代码都是在LeetCode上提交通过的。
Author: JefferyYu
1. Sort Algorithm Implementation Questions（排序算法）
1. 冒泡排序 2. 选择排序 3. 插入排序 4. 快速排序
1.冒泡排序O( n2 )
1.1 核心思想：
每次选择最小的往上冒，发现比我小，就换位置
1.1 代码实现：
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
}
}
}
}2.选择排序 O( n2 )
2.1 核心思想：
选择排序的意思就是：选好了，再换位置 具体的实现就是每次保存最小的那个下标，然后到最后再换一次即可
2.1 代码实现：
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
}
}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)
}
}
}
}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
}end
本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2021-07-21，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
