LeetCode初中級(jí)算法題解：排序算法介紹篇
作者：Candy.W
搜集題目的難度是在簡(jiǎn)單級(jí)別和中級(jí)級(jí)別，也是面試常考的題目。題目的題解，使用的開發(fā)語(yǔ)言是 Swift。
引言：
??搜集題目的難度是在簡(jiǎn)單級(jí)別和中級(jí)級(jí)別，也是面試常考的題目。題目的題解，使用的開發(fā)語(yǔ)言是 Swift。
??因?yàn)轭}目的描述很長(zhǎng)，以及有各種案例提示，為了不占篇幅，所以沒(méi)有展示出來(lái)，大家可以直接通過(guò)題號(hào)查詢，或者通過(guò)搜索關(guān)鍵字去查看題目的描述。
文章的寫作順序是：
1. 展示題號(hào)和以及題目的鏈接
2. 核心思想的講述
3. 代碼實(shí)現(xiàn)
最后本文提供的代碼都是在LeetCode上提交通過(guò)的。
??Author: JefferyYu
1. Sort Algorithm Implementation Questions(排序算法)
1. 冒泡排序
2. 選擇排序
3. 插入排序
4. 快速排序
1.冒泡排序O( n2 )
1.1 核心思想：
每次選擇最小的往上冒，發(fā)現(xiàn)比我小，就換位置
1.2 代碼實(shí)現(xiàn)：
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 核心思想：
選擇排序的意思就是：選好了，再換位置
具體的實(shí)現(xiàn)就是每次保存最小的那個(gè)下標(biāo)，然后到最后再換一次即可
2.2 代碼實(shí)現(xiàn)：
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 算法思想
將第一待排序序列第一個(gè)元素看做一個(gè)有序序列，把第二個(gè)元素到最后一個(gè)元素當(dāng)成是未排序序列。
從頭到尾依次掃描未排序序列，將掃描到的每個(gè)元素插入有序序列的適當(dāng)位置。
3.2 代碼實(shí)現(xiàn)
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 算法思想
快排的思想還是很有用的，就是把大于我的部分放在我的右邊，小于我的部分放在我的左邊。
具體的大家想看實(shí)現(xiàn)的詳細(xì)的情況，可以看我寫的這篇文章：一文讀懂快速排序
4.2 代碼實(shí)現(xiàn)
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個(gè)大數(shù)組被分割成了左邊和右邊2個(gè)數(shù)組】
// 將pivot的位置拋出來(lái)，作為遞歸的時(shí)候的左邊數(shù)組的end和右邊數(shù)組的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
}
}
}
//將軸點(diǎn)元素放到最終的位置, 此時(shí)begin和end是重合的。所以下面使用begin或者end都是可以的
nums[begin] = pivot
return begin
}
責(zé)任編輯：姜華
來(lái)源：
今日頭條
