Algorithem_Sort#
給定一個按非遞減順序排序的整數數組 nums，返回每個數的平方後按非遞減順序排序的數組。
QuickSort#
實現邏輯：
取指定位置的 index 的值 key，比較 index 和 index 之前的數字，如果前面的數字大於後面的數字，則交換位置；
比如：
[ 8 3 5 1 4 2 ]
從 index 為 1 開始，當前元素 3，前面元素 8，8 > 3，故而交換位置，數組還為[ 3 8 5 1 4 2 ]
然後 index 為 2，當前元素為 5，前面元素為 8，8 > 5，故而交換位置，數組為[ 3 5 8 1 4 2 ]
然後 index 為 3，當前元素為 1，前面元素為 8，8 > 1，故而交換位置，數組為[ 3 5 1 8 4 2 ]；5 > 1，故而交換位置，數組為[ 3 1 5 8 4 2 ]；3 > 1，故而交換位置，數組為[ 1 3 5 8 4 2 ]
然後 index 為 4，當前元素 4，前面元素為 8，8 > 4，故而交換位置，數組為[ 1 3 5 4 8 2 ]；5 > 4，故而交換位置，數組為[ 1 3 4 5 8 2 ]
然後 index 為 5，當前元素 2，前面元素為 8，8 > 2，故而交換位置，數組為[ 1 3 4 5 2 8 ]；5 > 2，故而交換位置，數組為[ 1 3 4 2 5 8 ]；4 > 2，故而交換位置，數組為[ 1 3 2 4 5 8 ]；3 > 2，故而交換位置，數組為[ 1 2 3 4 5 8 ]；1 < 2，停止；
代碼如下：
class Solution {
func sortedSquares(_ nums: [Int]) -> [Int] {
// first, get the squareList
var squareNums = nums.map({ $0 * $0 })
for j in 0..<squareNums.count {
let key = squareNums[j]
var i = j - 1
while (i >= 0 && squareNums[i] > key) {
squareNums[i+1] = squareNums[i]
i = i - 1
}
squareNums[i+1] = key
}
return squareNums
}
}
Selection Sort#
實現邏輯：
遍歷數組找到最小的值，放到結果數組 index 為 0 的位置；
遍歷數組找到第二小的值，放到結果數組 index 為 1 的位置；
...
代碼如下：
class Solution {
func sortedSquares(_ nums: [Int]) -> [Int] {
// first, get the squareList
var squareNums = nums.map({ $0 * $0 })
// selectionSort
let count = squareNums.count
for i in 0..<(count-1) {
var j_min = i
var j = i+1
// 遍歷找出從 i 開始後，最小的元素的 index
while (j < count) {
if squareNums[j] < squareNums[j_min] {
j_min = j
}
j = j + 1
}
// 如果 i 和最小的 index 不相等，交換兩個位置的元素
if i != j_min {
squareNums.swapAt(i, j_min)
}
}
return squareNums
}
}
Bubble Sort#
邏輯如下：
依次遍歷相鄰兩個元素，如果前面元素大，則交互位置；然後繼續向後比較；
重複上面步驟
再重複上面步驟
...
直到沒有可交換位置的元素為止
舉例如下：
[2, 1, 6, 4, 7, 5]
第一次遍歷：
index = 1; 當前元素為 2, 前面元素為 1, 2 < 1, 交換位置, [1, 2, 6, 4, 7, 5]
index = 2; 當前元素為 6, 前面元素為 2, 6 > 2, 不需要交換位置
index = 3; 當前元素為 4, 前面元素為 6, 4 < 6, 交換位置, [1, 2, 4, 6, 7, 5]
index = 4; 當前元素為 7, 前面元素為 6, 7 > 6, 不需要交換位置
index = 5; 當前元素為 5, 前面元素為 7, 5 < 7, 交換位置, [1, 2, 4, 6, 5, 7]
中間有交換位置
第二次遍歷：
index = 1; 當前元素為 2, 前面元素為 1, 2 > 1, 不需要交換位置, [1, 2, 4, 6, 5, 7]
index = 2; 當前元素為 4, 前面元素為 2, 4 > 2, 不需要交換位置
index = 3; 當前元素為 6, 前面元素為 4, 6 > 4, 不需要交換位置
index = 4; 當前元素為 5, 前面元素為 6, 5 < 6, 交換位置, [1, 2, 4, 5, 6, 7]
index = 5; 當前元素為 7, 前面元素為 6, 7 > 6, 不需要交換位置
中間有交換位置
第三次遍歷
index = 1; 當前元素為 2, 前面元素為 1, 2 > 1, 不需要交換位置, [1, 2, 4, 5, 6, 7]
index = 2; 當前元素為 4, 前面元素為 2, 4 > 2, 不需要交換位置
index = 3; 當前元素為 6, 前面元素為 4, 6 > 4, 不需要交換位置
index = 4; 當前元素為 6, 前面元素為 5, 6 > 5, 不需要交換位置
index = 5; 當前元素為 7, 前面元素為 6, 7 > 6, 不需要交換位置
本次遍歷沒有交換位置，遍歷結束
代碼如下：
class Solution {
func sortedSquares(_ nums: [Int]) -> [Int] {
// first, get the squareList
var squareNums = nums.map({ $0 * $0 })
// bubble sort
var sorted = false;
while (!sorted) {
sorted = true
for i in 1..<(squareNums.count) {
if (squareNums[i] < squareNums[i-1]) {
squareNums.swapAt(i, i-1)
sorted = false
}
}
}
return squareNums
}
}
merge sort#
實現邏輯：
把數組拆分為兩半，然後對兩半的數組繼續拆分，直到數組元素個數為 1，然後比較最後拆分的最小數組，排序後返回，再排序拼接拼接拼接。
示意圖如下：
代碼如下：
class Solution {
func merge(_ left: [Int], _ right: [Int]) -> [Int] {
// 定義新的數組，用於存儲排序後的結果
var result: [Int] = []
// 把傳入參數變為可變
var mutLeft = left
var mutRight = right
// 遍歷排序
while mutLeft.count > 0 && mutRight.count > 0 {
// 排序
// 如果左邊的小，則把左邊第一個元素彈出，放入結果數組中；否則把右邊的第一個元素彈出，放入結果數組中。
result.append(mutLeft[0] < mutRight[0] ? mutLeft.removeFirst() : mutRight.removeFirst())
}
// 拼接不為空的數組
result += (mutLeft.count > 0 ? mutLeft : mutRight)
// 返回
return result
}
func mergeSort(_ nums: [Int]) -> [Int] {
// 數組元素個數小於 2，不需要再拆分，返回數組
if nums.count < 2 {
return nums
}
// 從中間拆分數組
let middle = nums.count / 2
// 取 0 到 middle，不含 middle 的一半數組
let leftSlice = nums[0..<middle]
// 然後繼續拆分
let subLeft = mergeSort(Array(leftSlice))
// 取 middle 右邊的一半數組
let rightSlice = nums[middle..<nums.count]
// 繼續拆分
let subRight = mergeSort(Array(rightSlice))
// 拆分到不能拆分後，排序、合併後返回
return merge(subLeft, subRight)
}
func sortedSquares(_ nums: [Int]) -> [Int] {
// first, get the squareList
var squareNums = nums.map({ $0 * $0 })
// merge sort
return mergeSort(squareNums)
}
}