sort

import UIKit

var str = "Hello, sort"

func selectionSort(_ arr: inout [Int]){
    for i in 0..<arr.count{
        var minIndex = i
        for j in i+1..<arr.count{
            if arr[j]<arr[minIndex]{
                minIndex = j
            }
        }
        (arr[minIndex],arr[i]) = (arr[i],arr[minIndex])
    }
}

var arr :[Int] = [3,44,38,5,47,15,36,26,27,2,44,4,19,50,48]
selectionSort(&arr)
print(arr)

func bubbleSort(_ arr:inout [Int]){
    for i in 0..<arr.count{
        for j in i+1..<arr.count{
            if arr[j]<arr[i] {
                (arr[j],arr[i]) = (arr[i],arr[j])
            }
        }
    }
}
var bubblearr :[Int] = [3,44,38,5,47,15,36,26,27,2,44,4,19,50,48]
bubbleSort(&bubblearr)
print(bubblearr)

func insertionSort(_ arr: inout [Int]){
    for i in 0..<arr.count-1{
    let current = arr[i+1]
    var preIndex = i
        while preIndex>=0 && current<arr[preIndex] {
            print(i)
            print("arr[preIndex]:\(arr[preIndex])")
            print("current:\(current)")

            arr[preIndex+1] = arr[preIndex]
           preIndex = preIndex - 1
        }
        arr[preIndex+1] = current
        
    }
}
var insertionSortarr :[Int] = [3,1,38,5,47,15,36,26,27,2,44,4,19,50,48]
insertionSort(&insertionSortarr)
print(insertionSortarr)

//var numbersArray = [1, 4, 6, 5, 8, 2]
//
//func quicksort(left: Int, right : Int) -> Void {
//
//    var i, j, pivot : Int
//
//    if left > right {
//        return
//    }
//
//    pivot = numbersArray[left]
//
//    i = left
//    j = right
//
//    while i != j {
//
//        while numbersArray[j] >= pivot && i < j {
//            j -= 1
//        }
//
//        while numbersArray[i] <= pivot && i < j {
//            i += 1
//        }
//
//        if i < j {
//            numbersArray.swapAt(i, j)
//        }
//    }
//
//    numbersArray[left] = numbersArray[i]
//    numbersArray[i] = pivot
//
//    //二分
//    quicksort(left: left, right: i - 1)
//    quicksort(left: i + 1, right: right)
//}
//
//quicksort(left: 0, right: 5)
//
//print(numbersArray)


func quickSort (_ arr:[Int]) -> [Int]{
    guard arr.count > 0 else{
        return arr
        
    }
    
    let pivot = arr[arr.count/2]
    let left = arr.filter { (temp) -> Bool in
       return temp < pivot
    }
    let right = arr.filter { (temp) -> Bool in
       return temp > pivot
    }
    let mid = arr.filter { (temp) -> Bool in
       return temp == pivot
    }
//    var left = [Int]()
//    var right = [Int]()
//    var mid = [Int]()
//    for i in 0..<arr.count{
//        if arr[i]<pivot{
//            left.append(arr[i])
//        }else if arr[i] == pivot{
//            mid.append(arr[i])
//        }else{
//            right.append(arr[i])
//        }
//    }
    return quickSort(left) + mid + quickSort(right)
}
//var insertionSortarr :[Int] = [3,1,38,5,47,15,36,26,27,2,44,4,19,50,48]


var quickArr = quickSort([3,1,38,5,47,15,36,26,27,2,44,4,19,50,48])
print(quickArr)


func MergeSort(_ arr:[Int]) ->[Int]{
    print("MergeSortarr:\(arr)")
    if (arr.count < 2){
        return arr
    }
    let mid = arr.count / 2
    var left = [Int]()
    var right = [Int]()

    for i in 0..<mid{
        left.append(arr[i])
    }
    for i in mid..<arr.count{
        right.append(arr[i])
    }
 
    return merge(MergeSort(left) , MergeSort(right) )
}

func merge(_ left:[Int],_ right:[Int]) ->[Int]{
    print("left:\(left)")
    print("right:\(right)")
    var result = Array(repeating: 0, count: left.count+right.count)
    var i = 0
    var j = 0
    for index in 0..<result.count{
        if i>=left.count{
            result[index] = right[j]
            j = j+1
        }else if j >= right.count{
            result[index] = left[i]
            i = i+1
        }else if left[i] > right[j]{
            result[index] = right[j]
            j = j+1
        }else{
            result[index] = left[i]
            i = i+1
        }
    }
    print("result:\(result)")

    return result
}

var MergeSortArr = MergeSort([3,1,38,5,47,15,36,26,27,2,44,4,19,50,48])
print(MergeSortArr)



func bucketSort(originArray: [Int]) -> [Int] {
    
    let maxNum = originArray.max()
    //桶的数目
    var bucket:[Int] = Array.init(repeatElement(0, count: maxNum! + 1))
    var newNum:[Int] = Array.init()
    
    //给桶加标记
    for index in originArray {
        let numId = index
        bucket[numId] += 1
    }
    
    for index in bucket.indices {
        
        while bucket[index] > 0 {
            newNum.append(index)
            bucket[index] -= 1
        }
    }
    
    return newNum
        
}

let originNum :[Int] = [3,1,38,5,47,15,36,26,27,2,44,4,19,50,48]
let newNum = bucketSort(originArray: originNum)
print(newNum)