Algotithem_Sort
Given an integer array nums sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order.
QuickSort
实现逻辑：
取指定位置的 index 的值key，比较index和 index之前的数字，如果前面的数字大于后面的数字，则交换位置;
比如：
代码语言：Swift复制[ 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，停止；代码如下：
代码语言：Swift复制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的位置；
...
代码如下：
代码语言：Swift复制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
逻辑如下：
依次遍历相邻两个元素，如果前面元素大，则交互位置；然后继续向后比较；
重复上面步骤
再重复上面步骤
...
直到没有可交换位置的元素为止
举例如下：
代码语言：Swift复制[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, 不需要交换位置
本次遍历没有交换位置，遍历结束代码如下：
代码语言：Swift复制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，然后比较最后拆分的最小数组，排序后返回，再排序拼接拼接拼接。
示意图如下：
merge sort demo代码如下：
代码语言：Swift复制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)
}
}参考
- squares-of-a-sorted-array
- Sorting Algorithms Explained with Examples in JavaScript, Python, Java, and C
