根据袁厨的算法小屋排序部分做的总结笔记

冒泡排序

两两比较相邻记录的关键字，如果反序则交换，直到没有反序为止。

冒泡一次会让至少一个元素移动到它应该在的位置，那么如果数组有n个元素，重复n次后则能完成排序。根据定义可知冒泡排序是比较类排序

 //冒泡
    func bubbleSort(nums: inout [Int]) {
        
      //增加标记防止无意义的遍历
        var flag = true
        
        var i = 0
        
        while i < nums.count && flag == true {
            
            flag = false
            for j in 0..<nums.count - i - 1 { //注意边界
                if nums[j] > nums[j+1] {
                    swap(nums: &nums, i: j, j: j+1)
                    flag = true
                }
            }
            
            i += 1
        }
    }

算法名称	最好时间复杂度	最坏时间复杂度	平均时间复杂度	空间复杂度	是否稳定
冒泡排序	O(n)	O(n^2)	O(n^2)	O(1)	稳定

冒泡排序

简单选择排序

主要思路是通过在n-i+1个记录中选取关键字最小的记录作为有序序列的第i个记录，

//简单选择排序
    func selectSort(nums: inout [Int]) {
        guard nums.count > 0 else {
            return
        }
        
        var min = 0
        
        for i in 0 ..< nums.count {
            min = i
            for j in (i+1)..<nums.count {
                if nums[min] > nums[j] {
                    min = j
                }
            }
            if min != i {
                swap(nums: &nums, i: i, j: min)
            }
        }
        
    }

算法名称	最好时间复杂度	最坏时间复杂度	平均时间复杂度	空间复杂度	是否稳定
简单选择排序	O(n^2)	O(n^2)	O(n^2)	O(1)	不稳定

简单选择排序

直接插入排序

将一个记录插入到已经排好序的有序表中，从而得到一个新的有序表。通俗地讲，我们首先将序列分为两个区间，有序区间和无序区间，我们每次在无序区间内取一个值，在已排序区间中找到合适的位置插入，并保证有序区间一直有序

    //直接插入排序
    func straightInsertionSort(nums: inout [Int]) {
        guard nums.count > 0 else {
            return
        }
        
        for i in 0..<nums.count {
            let temp = nums[i]//待排序的值
            var j = i-1 //有序数组的最后一个值，就是gif中的数字5
            
            while j >= 0 {
                if temp < nums[j] {
                    nums[j+1] = nums[j] //把大的往后挪
                    j -= 1
                    continue
                }
                break
            }
            //插入到合适位置，这也就是我们没有在 for 循环内定义变量的原因
            nums[j+1] = temp
            
        }
    }

直接插入排序

希尔排序

是插入排序的一种，又称“缩小增量排序”，是一个有跨度的插入排序，这个跨度会逐渐变小，变为 1 时记录也就基本有序，这时用到的也就是我们之前讲的直接插入排序了。

 //希尔排序
    func shellSort(nums: inout [Int]) {
        
        //增量
        var increment = nums.count
        
        while increment > 1 {
            increment = increment / 2
            for i in 0..<increment {
                //插入排序
                for j in stride(from: i+increment, to: nums.count, by: increment) {
                    let temp = nums[j]
                    var k = j - increment
                    while k >= 0 {
                        if temp < nums[k] {
                            nums[k + increment] = nums[k]
                            k -= increment
                            continue
                        }
                        break
                    }
                    nums[k+increment] = temp
                }
            }
        }
        
    }

希尔排序

归并排序

归并排序的核心：分治法
将数组分割成两部分（左边可能比右边多一个）
继续将数组分割，直到所有部分的元素个数为1，
从最底层开始逐步合并两个排好序的数列。
知乎上这片文章讲的通俗易懂

    //归并排序
    func mergeSort(nums: inout [Int]) {
        guard nums.count > 0 else {
            return
        }
        
        var temp = Array(repeating: 0, count: nums.count)
        mergeSort(nums: &nums, left: 0, right: nums.count-1, temp: &temp)
        
    }
    
    func mergeSort(nums: inout [Int], left: Int, right: Int, temp: inout [Int]) {
        if left < right {
            let mid = left + ((right - left) >> 1)
            mergeSort(nums: &nums, left: left, right: mid, temp: &temp) //归并左半部分
            mergeSort(nums: &nums, left: mid+1, right: right, temp: &temp) //归并右半部分
            merge(nums: &nums, left: left, mid: mid, right: right, temp: &temp) //最后归并左右部分
        }
    }
    
    /**
     合并两个有序数列
     nums[left]~nums[mid]为第一组
     nums[mid+1]~nums[right]为第二组
     temp是存放两组比较结果的临时数组
     */
    func merge(nums: inout [Int], left: Int, mid: Int, right: Int, temp: inout [Int]) {
        var i = left, j = mid + 1 //i 为第一组的起点，j为第二组的起点
        let m = mid, n = right    //m 为第一组的终点，n为第二组的终点
        var k = 0                 //k是temp数组当前的位置
        
        while i <= m && j <= n {
            if nums[i] <= nums[j] { //两组进行比较
                temp[k] = nums[i]   //如果第一组的数据小，把nums[i]放入temp，同时移动k和i的指针
                k += 1
                i += 1
            } else {
                temp[k] = nums[j]   //如果第二组的数据小，把nums[j]放入temp，同时移动k和j的指针
                k += 1
                j += 1
            }
        }
        
        while i <= m { //如果比较完成后第一个数组还有剩余的部分，全部填入temp
            temp[k] = nums[i]
            k += 1
            i += 1
        }
        
        while j <= n { //如果比较完成后第二个数组还有剩余的部分，全部填入temp
            temp[k] = nums[j]
            k += 1
            j += 1
        }
        
        for s in 0..<k { //将临时数组数据回填到原始数组
            nums[left+s] = temp[s]
        }
        
    }

算法名称	最好时间复杂度	最坏时间复杂度	平均时间复杂度	空间复杂度	是否稳定
归并排序	O(nlogn)	O(nlogn)	O(nlogn)	O(n)	稳定

归并排序.png

快速排序

基本思路

1.找一个数组中的基准数
（1).一般数组的第一个
（2).为了防止出现最大数出现在头部的情况，采用三数取中的方式
2.让其他比它大的元素移动到数列一边，比他小的元素移动到数列另一边，从而把数组拆解成两个部分
3.再对左右部分，分别重复第二步，直到每部分元素个数为1

快排分类

值得注意的是，根据使用的指针数量，将排序的分为三种
1.单路快排：使用一个指针，移动指针并且判断当前元素和pivot的大小，进行交换
2.双路快排：使用两个指针，找到右指针小于pivot的元素，找到左指针大于pivot的元素，将右指针和左指针的元素交换，最后再将基准数pivot归位
3.三路快排：使用三个指针，分别是左指针left，右指针right和探路指针i；移动i，并且和pivot判断:
(1)<pivot，交换i和left的值，并且left++，i++
(2)>pivot，交换i和right的值，并且right--
(3)=pivot，i++

挖坑法

1.将基准数pivot从数组中取出；(挖出pivot)
2.判断nums[high] < pivot ，如果条件不成立使high--，直到nums[high] < pivot，将nums[high]填入到之前的位置；(挖出high，填入之前的坑位)
3.判断nums[low] > pviot，如果条件不成立使low++，直到nums[low] > pivot，将nums[low]填入到之前high的位置；(挖出low，填入之前high的坑位)
4.最后将pviot填入到之前low的位置。（回填）

func quickSort(nums: inout [Int], low: Int, high: Int) {
        if low < high {
            let index = partition1(nums: &nums, low: low, high: high)
            quickSort(nums: &nums, low: low, high: index)
            quickSort(nums: &nums, low: index + 1, high: high)
        }
    }
    
    //挖坑法
    func partition1(nums: inout [Int], low: Int, high: Int) -> Int {
        
        //三数取中
        let mid = low + ((high - low) >> 1)
        if nums[low] > nums[high] {swap(nums: &nums, i: low, j: high)}
        if nums[mid] > nums[high] {swap(nums: &nums, i: mid, j: high)}
        if nums[mid] > nums[low] {swap(nums: &nums, i: mid, j: low)}
        
        let pivot = nums[low] //取出pivot
        var low = low
        var high = high
        
        
        while low < high {
            
            //比较high
            while low < high && nums[high] >= pivot  {
                high -= 1
            }
            
            //填坑
            if low < high {nums[low] = nums[high]}
            
            //比较low
            while low < high && nums[low] <= pivot {
                low += 1
            }
            //填坑
            if low < high {nums[high] = nums[low]}
            
        }
       //将pivot填坑
        nums[low] = pivot
        return low
    }

交换法

1.对上面方法的挖坑填坑步骤进行合并，
2.low 指针找到大于 pivot 的元素，hight 指针找到小于 pivot 的元素，然后两个元素交换位置
3.最后再将基准数归位

 //交换法
    func partition2(nums: inout [Int], low: Int, high: Int) -> Int {
        
        //三数取中
        let mid = low + ((high - low) >> 1)
        if nums[low] > nums[high] {swap(nums: &nums, i: low, j: high)}
        if nums[mid] > nums[high] {swap(nums: &nums, i: mid, j: high)}
        if nums[mid] > nums[low] {swap(nums: &nums, i: mid, j: low)}
        
        let pivot = nums[low]
        let lowLet = low //保存low原始值
        var low = low
        var high = high
    
        
        while low < high {
            while low < high && nums[high] >= pivot {
                high -= 1
            }
            
            while low < high && nums[low] <= pivot {
                low += 1
            }
            if low >= high {//退出条件
                break
            }
            swap(nums: &nums, i: low, j: high) //交换low和high
        }
        swap(nums: &nums, i: lowLet, j: low) //基准数归位
        return low
    }

    func swap(nums: inout [Int], i: Int, j: Int) {
        if i == j {
            //应当注意，由于这里直接操作的是对象类型，不是值类型，所以如果i=j时进行异或操作会导致i为0
            //所以这里需要进行判断
            return
        }
        
        nums[i] ^= nums[j]
        nums[j] ^= nums[i]
        nums[i] ^= nums[j]
    }

三向切分（三路快排）

作用：当数组重复元素比较多时，减小递归调用时的区间大小
1.定义探路指针i = low+1，
2.当nums[i] < pivot时，交换i和low的值，移动low +1 ,移动 i +1
3.当nums[i] > pivot时，交换i和high的值，移动high -1，
4.当nums[i] == pivot时，只移动i +1

 //三向切分
    func partition3(nums: inout [Int], low: Int, high: Int) -> Int {
        
        //三数取中
        let mid = low + ((high - low) >> 1)
        if nums[low] > nums[high] {swap(nums: &nums, i: low, j: high)}
        if nums[mid] > nums[high] {swap(nums: &nums, i: mid, j: high)}
        if nums[mid] > nums[low] {swap(nums: &nums, i: mid, j: low)}
        
        let pivot = nums[low]
        var low = low
        var high = high
        var i = low + 1
    
        
        while i <= high {
            
            if nums[i] < pivot { //如果nums[i] < pivot，交换i和low的值，并且移动low和i
                swap(nums: &nums, i: i, j: low)
                low += 1
                i += 1
            } else if nums[i] > pivot { //如果nums[i] > pivot，交换i和high的值，并且移动high
                swap(nums: &nums, i: i, j: high)
                high -= 1
            } else { //如果nums[i] == pivot，只移动i
                i += 1
            }
           
        }
        return low
    }
    
    
    func swap(nums: inout [Int], i: Int, j: Int) {
        if i == j {
            //应当注意，由于这里直接操作的是对象类型，不是值类型，所以如果i=j时进行异或操作会导致i为0
            //所以这里需要进行判断
            return
        }
        
        nums[i] ^= nums[j]
        nums[j] ^= nums[i]
        nums[i] ^= nums[j]
    }

图示

挖坑法.png
交换法
三向切分.png

堆排序

在堆中计算二叉树节点的左右节点以及父子节点

某节点下标为i（非叶子节点）
左子节点：2*i
右子节点：2*i+1
父节点：i/2

堆排序步骤

1.建堆
（1）.大顶堆，小顶堆
（2）.上浮法，下沉法（性能较好）
2.排序

建堆

上浮法

以小顶堆为例
给定一个节点，与父节点判断大小，如果小于父节点，交换两个节点的位置，不断进行操作，直到上浮到合适位置

//上浮法建小顶堆
    func swim(nums: inout [Int], index: Int) {
        var index = index
        while index > 1 && nums[index/2] > nums[index] {
            swap(nums: &nums, i: index/2, j: nums[index])
            index /= 2
        }
    }

下沉法

以大顶堆为例
找到最后一个非叶子节点(len/2)，首先获取左子节点（index*2)，判断和右子节点（index*2+1），找到最大的那个，然后和当前节点进行判断，如果当前节点较小，则交换

为什么是找最大的那个呢？

因为大顶堆是每个节点的子节点必须小于父节点，如果和最小的交换，是无法保证的（如果是小顶堆应该和最小的交换）

    //下沉法建大顶堆
    func sink(nums: inout [Int], index: Int, len: Int) {
        
        var index = index
        
        while 2 * index <= len {
            var j = 2 * index //左子节点
            if j+1 <= len && nums[j+1] > nums[j] { //与右子节点判断，如果右子节点大，切换到右子节点
                j += 1
            }
            
            //判断与子节点大小，如果子节点大于当前节点，则交换，否则退出
            if nums[j] > nums[index] {
                swap(nums: &nums, i: j, j: index)
            } else {
                break
            }
            
            index = j//如果还有子节点，继续下沉
            
        }
    }

排序

排序的思路：
1.将堆顶的元素（最大的元素）和最后一个元素交换
2.堆新的堆顶元素进行下沉
3.遍历执行，直到k>1

//堆排序
    func heapSort(nums: inout [Int]) {
        let len = nums.count
        var a = Array(repeating: -1, count: len + 1)
        
        //集体移动一位，数组创建堆时第一位要空出
        for i in 0..<len {
            a[i+1] = nums[i]
        }
        
        //下沉法建大顶堆
        for i in (1...(len/2)).reversed() {
            sink(nums: &a, index: i, len: len)
        }
        
        
        //排序
        var k = len
        
        while k>1 {
            swap(nums: &a, i: 1, j: k) //堆顶元素（最大元素）与最后一个交换
            k-=1
            sink(nums: &a, index: 1, len: k) //新的堆顶元素进行下沉
        }
        
        //重整数组
        for i in 1..<a.count {
            nums[i-1] = a[i]
        }
        
    }

总结

1.建堆，通过下沉操作建堆效率更高，具体过程是，找到最后一个非叶子节点，然后从后往前遍历执行下沉操作。

2.排序，将堆顶元素（代表最大元素）与最后一个元素交换，然后新的堆顶元素进行下沉操作，遍历执行上诉操作，则可以完成排序。

计数排序

1.求统计计数数组
2.根据统计计数数组求前缀和数组
3.反序遍历原数组，根据原数组的元素查询presum，查询到的presum的元素-1就是需要放入临时数组的位置，完成后presum相应位置的元素-1
4.应当注意数组空间的问题，比如[91,92,93,94]，还应当注意负数问题[-3,-1,-1,-2,0]，解决思路是遍历时元素下标减去最小值，

先不考虑数组空间和负数问题，代码⬇️

    //计数排序
    func countSort(nums: inout [Int]) {
        
        //前缀和数组
        var presum = Array(repeating: 0, count: nums.count)
        //临时数组
        var temps = Array(repeating: 0, count: nums.count)
        
        
        //1.求统计次数数组
        for num in nums {
            presum[num] += 1
        }
        
        //2.求前缀和数组
        for i in 1..<nums.count {
            presum[i] = presum[i-1] + presum[i]
        }
        
        //3.开始排序
        for num in nums.reversed() {
            temps[presum[num]-1] = num
            presum[num] -= 1
        }
        
        nums = temps
    }

增加解决数组空间和负数问题的代码⬇️

    //计数排序
    func countSort(nums: inout [Int]) {
        
        guard nums.count > 0 else {
            return
        }
        
        var max = nums[0]
        var min = nums[0]
        
        //求出最大最小值
        for num in nums {
            if max < num {max = num}
            if min > num {min = num}
        }
        
        let count = max - min + 1
        
        //前缀和数组
        var presum = Array(repeating: 0, count: count)
        //临时数组
        var temps = Array(repeating: 0, count: nums.count)
        
        
        //1.求统计次数组
        for num in nums {
            presum[num-min] += 1
        }

        //2.求前缀和数组
        for i in 1..<nums.count {
            presum[i] = presum[i-1] + presum[i]
        }
        
        //3.开始排序
        for num in nums.reversed() {
            //查找presum，将其放入临时数组
            temps[presum[num-min]-1] = num
            //presum相应位置-1
            presum[num-min] -= 1
        }
        nums = temps
    }

计数排序.png

时间复杂度：O(N+K)
空间复杂度：O(n)