Algorithem_Sort

2022-04-13

Algorithem_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之前的数字，如果前面的数字大于后面的数字，则交换位置;

比如：


[ 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，然后比较最后拆分的最小数组，排序后返回，再排序拼接拼接拼接。

示意图如下：

merge sort demo

代码如下：


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)
    }
}

Algorithem_Sort

QuickSort

Selection Sort

Bubble Sort

merge sort

参考