LeetCode初中级算法题解:排序算法介绍篇
2023-02-25 18:26:42 时间
引言:
搜集题目的难度是在简单级别和中级级别,也是面试常考的题目。题目的题解,使用的开发语言是 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
}
}
}
}
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
}
}
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
}
相关文章
- 构建基于Transformer的推荐系统
- 4种大文件传输工具和软件,用于共享大文件
- 大数据NiFi(四):NiFi单节点安装
- Paxos分布式系统共识算法?我愿称其为点歌算法…
- 技术汇总:第十二章:技术总览
- 84岁学界泰斗,竟被学生群体投诉到开除?学生诉苦:平均分30+,我们太难了!
- 头显戴上就吐, 小扎长腿竟是「诈骗」!烧完100亿美元,元宇宙大翻车
- Cloud Studio 年度产品亮点回顾
- 开源程序员愤怒控诉!Github的「AI码农」Copilot就是寄生虫
- 赛博打工人会梦见996吗?年轻人的元宇宙入口,只要799
- 苹果发布新款iPad Pro!就换了个「芯」,转换器骚操作笑翻网友
- 斯坦福/谷歌大脑:两次蒸馏,引导扩散模型采样提速256倍!
- 「最牛AI艺术家」Stable Diffusion有多值钱?种子轮融资即晋升独角兽!
- 死磕操作系统!谷歌重磅发布开源KataOS,网友:「谷歌坟场」喜+1
- 王者荣耀开源环境上榜!九月AI研究GitHub排行来了,「star多」才叫好论文
- DeepFake从未如此真实!英伟达最新提出的「隐式扭曲」到底有多强?
- WonderPen for Mac(妙笔写作软件) v2.2.3免激活版
- Aiseesoft Mac FoneTrans for Mac(iOS文件传输和管理器软件) v9.1.60激活版
- MIT新任女校长震撼北美高校圈!61岁的她曾是杜克首位女教务长
- C语言如何实现面向对象