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

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,3,-3,-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,-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,high: point-1)

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

 

}

//找临界点的位置

func partition(arr:inout [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,-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,-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,7,3]

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

inters.dropLast()

 

let a1 = [2,2]

let a2 = [2,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

 

    }

    

}