Swift经典算法回顾

1、比较类排序算法

1.1 冒泡排序：

• 核心思想：依次比较相邻元素，然后按条件进行元素交换。直到所有元素排好为止
• 代码实现：

    // 升序排列
    var nums = [8, 7, 6, 1, 2, 3, 4, 5]
    let length = nums.count - 1
    for i in 0..<length {
        for j in 0..<length - i {
            if nums[j] > nums[j+1] {
                let tmp = nums[j]
                nums[j] = nums[j+1]
                nums[j+1] = tmp
            }
        }
    }

1.2 选择排序

• 核心思想：如果是升序排序，首先从未排序序列中找出最小值放在第一位，然后继续在剩下未排序的序列中找出最小值放在第二位，依次类推直到排序完成
• 代码实现

    var min = Int.max
    var minIndex = 0
    var nums = [3,5,3,11]
    
    for i in 0..<nums.count - 1 {
        let k = i
        for j in k..<nums.count {
            if nums[j] < min {
                min = nums[j]
                minIndex = j
            }
        }
        
        print("循环次数 === i = \(i)")
        print("最小数值的索引值 minIndex= \(minIndex)")
        
        //在这里进行替换
        let tmp = nums[i]
        nums[i] = min
        nums[minIndex] = tmp
        
        // 交换完成记得修改min
        min = Int.max
        
    }

1.3 插入排序

• 核心思想：构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到响应的位置插入，直到排序完成
• 代码实现

    var nums = [5,4,3,2]

    let count = nums.count
    //外层循环需要多少次才能排好
    for i in 1..<count {
        
        var preIndex = i - 1
        let currentEle = nums[i]
        while preIndex >= 0, nums[preIndex] > currentEle {
            //向后移一位
            nums[preIndex + 1] = nums[preIndex]
            preIndex -= 1
        }
        // 将新元素插入
        print(preIndex)
        nums[preIndex + 1] = currentEle
    }
    
    print(nums)

1.4 希尔排序

• 核心思想：希尔排序是插入排序的改进版本，将整个待排序列分割成功若干个子序列，分别对子序列进行排序
• 代码实现

    var nums = [5,7,8,3,1,2,4,6]
    let length = nums.count
    var grap = length/2
    
    while grap > 0 {
      
        //对各个分组进行进行插入排序
        for i in grap ..< length {
            
            print("i====\(i)")
            var preIndex = i - grap
            let currentElement = nums[i]
            while preIndex >= 0, nums[preIndex] > currentElement {
                nums[preIndex + grap] = nums[preIndex]
                preIndex -= grap
            }
            nums[preIndex + grap] = currentElement
            
        }
        
        grap = grap / 2
    }
    
    print(nums)

1.5 归并排序

核心思想：分而治之，先序列拆分子序列，保证子序列有序，然后再将各个子序列进行合并。
代码实现

// 归并排序
func sort(arr: [Int]) -> [Int]{
    if arr.count <= 1 {   //1.如果传入数组为空或者只有一个元素，我们就不需要继续拆分，直接返回
        return arr
    }
    let midIndex = arr.count / 2  //2.找到数组个数的中间值
  
    // 左边拆分
    let leftArray = sort(arr: Array(arr[0..<midIndex]))
    // 右边拆分
    let rightArray = sort(arr: Array(arr[midIndex..<arr.count]))
    print("leftArray = \(leftArray)")
    print("rightArray = \(rightArray)")
    return merge(leftArr: leftArray, rightArr: rightArray)
    
}

func merge(leftArr: [Int], rightArr: [Int]) -> [Int] {
    //1.定义左右两个索引
    var leftIndex = 0
    var rightIndex = 0
    
    //2.定义一个临时数组
    var tmpArr = [Int]()
    
    //3.开始合并
    while leftIndex < leftArr.count , rightIndex < rightArr.count {
        if leftArr[leftIndex] < rightArr[rightIndex] {
            //左边元素小于右边的
            tmpArr.append(leftArr[leftIndex])
            leftIndex += 1
        }else if leftArr[leftIndex] > rightArr[rightIndex] {
            //左边元素大于右边、
            tmpArr.append(rightArr[rightIndex])
            rightIndex += 1
        }else {
            tmpArr.append(leftArr[leftIndex])
            leftIndex += 1
            
            tmpArr.append(rightArr[rightIndex])
            rightIndex += 1
        }
    }
    
    //4.添加未添加完的
    while leftIndex < leftArr.count {
        tmpArr.append(leftArr[leftIndex])
        leftIndex += 1
    }
    
    while rightIndex < rightArr.count {
        tmpArr.append(rightArr[rightIndex])
        rightIndex += 1
    }
    return tmpArr
}

1.6 快速排序

• 核心思想：选择一个基数（一般序列中间元素），将大于基数的数放在右边，小于该基数的数放在左边，然后对象左右两个数组重复前面的步骤直到排序好为止
• 代码实现

    func quickSort(nums: [Int]) -> [Int] {
        guard nums.count > 1 else { return nums }
        
        let pivot = nums[nums.count/2]
        var less = [Int]()
        var equal = [Int]()
        var greater = [Int]()
        
        for num in nums {
            if num > pivot {
                greater.append(num)
            }else if num < pivot {
                less.append(num)
            }else {
                equal.append(num)
            }
        }
        
        return quickSort(nums: less) + equal + quickSort(nums: greater)
    }

2、非比较类排序

2.1 计数排序

• 核心思想：找到序列A中的max和min，创建一个max-min+1大小的数组B，数组B中记录A中某元素出现的次数，然后按B中次数依次输出元素，得到有序数组。
• 代码实现

    func countSort(nums: [Int]) -> [Int] {
        var max = Int.min
        var min = Int.max
        // 1.找到最大值
        for num in nums {
            if num > max {
                max = num
            }else if num < min{
                min = num
            }
        }
        // 2.创建一个长度为max-min + 1 的数组
        let length = max - min + 1
        var tmpArr = Array.init(repeating: 0, count: length)
        
        for num in nums {
            let tmpIndex = num - min
            // 统计元素出现的次数
            tmpArr[tmpIndex] = tmpArr[tmpIndex] + 1
        }
        var resultArr = [Int]()
        for (index,var num) in tmpArr.enumerated() {
            let value = index + min
            while num > 0 {
                resultArr.append(value)
                num -= 1
            }
        }
        return resultArr
    }

2.2 桶排序

• 核心思想：将有序序列拆分到若干桶中，然后再对每个非空桶进行排序，然后整合输出得到有序序列
• 代码实现

/*
     1.首先找出数组中max和min
     2.确定grap，确定桶的个数
     3.将数据填充到桶中
     4.对非空桶进行排序
     5.合并所以桶
     */
    
    func bucketSort(arr: [Int],grap: Int) -> [Int] {
        //1
        var min = Int.max
        var max = Int.min
        for num in arr {
            if num < min {
                min = num
            }else if num > max {
                max = num
            }
        }
        //2.确定桶数量
        let bucketCount = (max - min)/grap + 1
        var bucketArr = [[Int]]()
        for _ in 0..<bucketCount {
            bucketArr.append([Int]())
        }
        //3.叫数据填入桶中
        for num in arr {
            let index = (num - min) / grap
            bucketArr[index].append(num)
        }
        //4.对非空桶进行排序
        for (index,var subArr )in bucketArr.enumerated() {
            if subArr.count > 0 {
                //进行排序(可以选择冒泡排序，选择排序，插入排序，希尔排序，归并排序，计数排序都可以)
                let length = subArr.count - 1
                for i in 0..<length {
                    let k = length - i
                    for j in 0..<k {
                        if subArr[j] > subArr[j+1] {
                            let tmp = subArr[j]
                            subArr[j] = subArr[j+1]
                            subArr[j+1] = tmp
                        }
                    }
                }
                bucketArr[index] = subArr
            }
        }
        print(bucketArr)
        
        //5.输出
        var results = [Int]()
        for subArr in bucketArr {
            if subArr.count > 0 {
                results.append(contentsOf: subArr)
            }
        }
        
        return results
    }

2.3 基数排序

• 核心思想：将整数按位分割，然后按位数用桶排序
• 代码实现

 func radixSort(arr: [Int]) -> [Int] {
        
        //1.分配0-9个桶数组
        var bucketList = [[Int]]()
        for _ in 0..<10 {
            bucketList.append([Int]())
        }
        print(bucketList.count)
        //2.找出数组中最大的整数
        var max = 0
        for num in arr {
            if num > max {
                max = num
            }
        }
        //3计算出最大位数
        var maxCount = 1
        var tmp = max / 10
        while tmp != 0 {
            maxCount += 1
            tmp = tmp / 10
        }
        print(maxCount)
        
        var orignArr = arr
        
        //4.按位数排序
        for i in 1...maxCount {
            print("开始处理位数 === \(i)")
            //4.1 先排序
            for j in orignArr {
                //4.2获取数字所在的索引
                var digitNum = i
                var index = 0
                if digitNum == 1 {
                    index = j % 10
                }else {
                    var divisor = 1
                    while digitNum > 1 {
                        divisor = divisor * 10
                        digitNum -= 1
                    }
                    index = j / divisor
                }
                print(index)
                bucketList[index].append(j)
            }
            print(bucketList)
            
            //4.3 替换
            var totalIndex = 0
            for arr in bucketList {
                for ele in arr {
                    orignArr[totalIndex] = ele
                    totalIndex += 1
                }
            }
            bucketList = [[Int]]()
            for _ in 0..<10 {
                bucketList.append([Int]())
            }
            print(bucketList)
            print(orignArr)
//            break
        }
        
        print(orignArr)
        
        
        return orignArr