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
}
}