文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

LeetCode初中级算法题解:排序算法介绍篇

2024-12-02 07:57

关注

  因为题目的描述很长,以及有各种案例提示,为了不占篇幅,所以没有展示出来,大家可以直接通过题号查询,或者通过搜索关键字去查看题目的描述。

文章的写作顺序是:

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
}
}
}
//将轴点元素放到最终的位置, 此时beginend是重合的。所以下面使用begin或者end都是可以的
nums[begin] = pivot
return begin
}
来源:今日头条内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯