当前位置: 首页 > 工具软件 > GiFHUD-Swift > 使用案例 >

swift冒泡排序,swift快速排序,swift归并排序,swift插入排序,swift基数排序

任宾鸿
2023-12-01

import UIKit

/// 冒泡

///

///时O(n2),空O(1) 稳定排序

func Mysort(arr:[Int]) -> [Int]{

    var transArr = arr

    for i in 0..<transArr.count {

        for j in 0..<transArr.count-i-1{

            if transArr[j] > transArr[j+1]{

                transArr.swapAt(j, j+1)          //交换需要三条语句

            }

        }

    }

    return transArr

}

let arr = Mysort(arr: [2,4,1,5,6,8,3])

//插入排序

//时O(n2),空O(1) 稳定排序

func insertSort(arr:[Int]) -> [Int]{

    var newArr = arr

    for i in 0..<newArr.count{

        var j = i - 1

        let value = newArr[i]

        while j>=0 && newArr[j] > value{

            newArr[j+1] = newArr[j] //比value的的都往后移动一位移动数据

            j -= 1

        }

        newArr[j+1] = value//j+1的位置就是要插入的位置

    }

    return newArr

}

let arr1 = insertSort(arr: [2,4,1,5,6,8,3,-3,4,-1])

func optionSort(arr:[Int]) -> [Int]{

    var newArr = arr

    for i in 0..<newArr.count {

        var minValue = newArr[i]

        var minIndex = i

        for j in i+1 ..< newArr.count {

            if minValue > newArr[j] {

                minValue = newArr[j]

                minIndex = j

            }

        }

        newArr.swapAt(minIndex, i)

    }

    return newArr

}

//let arr2 = optionSort(arr: [2,4,1,5,6,8,3,-3,4,-1])

//快速排序 O(nlogn) 原地 稳定排序

func quickSort(arr:inout [Int],low:Int,high:Int){

    if low >= high {

        return

    }

    let point = partition(arr: &arr,low: low,high: high)

    quickSort(arr: &arr, low: low, high: point-1)

    quickSort(arr: &arr, low: point+1, high: high)

}

//找临界点的位置

func partition(arr:inout [Int],low:Int,high:Int)->Int{

    let pointV = arr[high]

    var i = low

    for j in low...high-1 {

        if arr[j] < pointV {

            arr.swapAt(i, j)

            i+=1

        }

    }

    arr.swapAt(i, high)

    return i

}

func quickSort(arr:[Int]) ->[Int]{

    var newArr = arr

    quickSort(arr: &newArr, low: 0, high: arr.count - 1)

    return newArr

}

//let arr2 = quickSort(arr: [2,4,1,5,6,8,3,-3,4,-1])

//归并 O(nlogn) 非原地排序O(n) 非稳定排序

func mergeSort(arr:[Int]) -> [Int]{

    var tempArr : [[Int]] = []

    for item in arr {

        var subArr : [Int] = []

        subArr.append(item)

        tempArr.append(subArr)

    }

    while tempArr.count != 1 {

        var i = 0

        while i < tempArr.count - 1{

            tempArr[i] = merge(arr1: tempArr[i], arr2: tempArr[i+1])

            tempArr.remove(at: i+1)

            i += 1

        }

    }

    return tempArr.first!

}

//合并两个有序数组,合并之后仍是有序数组

func merge(arr1:[Int],arr2:[Int]) -> [Int]{

    var newArr = [Int]()

    var i = 0

    var j = 0

    while i<arr1.count && j<arr2.count {

        if arr1[i] < arr2[j]{

            newArr.append(arr1[i])

            i+=1

        }else{

            newArr.append(arr2[j])

            j+=1

        }

    }

    while i < arr1.count {

        newArr.append(arr1[i])

        i += 1

    }

    while j < arr2.count {

        newArr.append(arr2[j])

        j += 1

    }

    return newArr

}

//let arr2 = mergeSort(arr: [2,4,1,5,6,8,3,-3,4,-1])

//基数排序

func BaseSort(arr:inout [Int]) {

    if arr.count == 0 {

        return

    }

    var list:[[Int]] = []

    for _ in 0..<10 {

        let temp:[Int] = []

        list.append(temp)

    }

    let maxDigit:Int = maxlength(arr: arr)//最大的位数

    var tempArr:[Int] = arr

    for i in 0..<maxDigit {

        for j in 0..<arr.count {

            let index:Int = highDigit(num: tempArr[j], index: i)

            list[index].append(tempArr[j]) //放入相应的桶中

        }

        saveBucketData(bucketlist: &list, arr: &tempArr)

    }

    arr = tempArr

}

// 桶的数据插入数组

private func saveBucketData(bucketlist:inout [[Int]],arr:inout [Int]) {

    var index:Int = 0

    for i in 0..<bucketlist.count {

        var bucket:[Int] = bucketlist[i]

        if bucket.count > 0 {

            for j in 0..<bucket.count {

                arr[index] = bucket[j]

                index += 1

            }

        }

        bucketlist[i].removeAll() // 注意清空桶数据

    }

}

//取出某位上的数字

private func highDigit(num:Int,index:Int)->Int {

    let base:Double = pow(10, Double(index))

    let high:Int = (num / Int(base)) % 10

    return high

}

// 最大数字的位数

private func maxlength(arr:[Int])->Int {

    var max:Int = 0

    for i in 0..<arr.count {

        let count:Int = positionOfNum(number: arr[i])

        if count > max {

            max = count

        }

    }

    return max

}

// 统计数字的位数

private func positionOfNum(number:Int)->Int {

    var count:Int = 0

    var num:Int = number

    while num%10 > 0  {

        count += 1

        num = num / 10

    }

    return count

}

var inters = [2,4,5,7,1,6,3]

inters.replaceSubrange(0..<3, with: [2,6,7])

inters.dropLast()

let a1 = [2,4,3,2]

let a2 = [2,4,4,3]

//n2 + n2 + n

//n2

var a22 = a2

//for num1 in a1 {

//    for index in 0..<a22.count{

        if index < a22.count{    //加上这个条件判断就没错了

//        if num1 == a22[index]{

//            a22.remove(at: index)   //经典的l遍历删除错误

//        }

//

        }

//    }

//}

class Person :Equatable{

    var age:Int

    var name:String

    init(age:Int,name:String) {

        self.age = age

        self.name = name

    }

    static func == (lhs: Person, rhs: Person) -> Bool{

        let point = Unmanaged<AnyObject>.passUnretained(lhs as AnyObject).toOpaque()

        let point1 = Unmanaged<AnyObject>.passUnretained(rhs as AnyObject).toOpaque()

        return point.hashValue == point1.hashValue

    }

}

 类似资料: