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

?

? ? }

?? ?

}