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

引言：

  搜集题目的初中难度是在简单级别和中级级别，也是算解排面试常考的题目。题目的法题法介题解，使用的序算开发语言是 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..

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..

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..

for j in (0..

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

}

云服务器提供商

很赞哦!（36737）