SortinSwift

var unnumber = [23,76,42,9,7,0,1,37,4,2,89,23,45,56,87,65,20,15,23,15,17]
var number = [19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1,0]
var number2 = [19,18]
var number1 = [19]

//to swap two number
func swapValue(inout left:Int, inout _ right:Int) {
    let temp = left
    left = right
    right = temp
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//Insert Sort
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

//Straight Insertion Sort
func insertSort(input:[Int]) -> [Int] {
    var output = input
    var temp = 0
    
    for i in 1..<output.count {
        if output[i] 1] {
            temp = output[i]
            output[i] = output[i - 1]
            var j = i - 1
            //记录后移,并且j>=0一定要放在&&前面,否则会出现数组越界的情况
            for ; j >= 0 && temp 1] = output[j] }
            //output[j + 1]是由于,循环完了之后,j指向的不是要插入的位置,而是之前的位置:j--
            output[j + 1] = temp
        }
    }
    return output
}
unnumber.sort()
insertSort(unnumber)
insertSort(number)
insertSort(number1)
insertSort(number2)

//Binary Insertion Sort
func insertSortWithBinarySearch(input:[Int]) -> [Int] {
    var output = input
    var temp = 0
    for i in 1..<output.count {
        if output[i] 1] {
            temp = output[i]
            output[i] = output[i - 1]
            //由于之前的数组已经是一个有序的数组,可以用折半查找来减少时间
            var low = 0, high = i - 1, min = 0
            
            while low <= high {
                min = (low + high) / 2
                if output[min] 1 }
                else if output[min] > temp { high = min - 1 }
                else {//用来判断相等的情况下,重复的数越多,越能减少比较的次数
                    low = min + 1
                    break
                }
            }
            var j = i - 1
            //一次查找之后low总指向比temp大的一个数,所以包括low在内的数据全部后移,将temp插入到low的前面
            for ; j >= low; j-- { output[j + 1] = output[j] }
            output[j + 1] = temp
        }
    }
    return output
}
unnumber.sort()
insertSortWithBinarySearch(unnumber)
insertSortWithBinarySearch(number)
insertSortWithBinarySearch(number1)
insertSortWithBinarySearch(number2)

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//Quick Sort
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

//Bubble Sort
func bubbleSort(input:[Int]) -> [Int] {
    var output = input
    
    for var i = 0; i  {
        for var j = 0; j 1; j++ {
            if output[j] > output[j + 1] {
                swapValue(&output[j], &output[j + 1])
            }
        }
    }
    return output
}
unnumber.sort()
bubbleSort(unnumber)
bubbleSort(number)
bubbleSort(number1)
bubbleSort(number2)

//Quick Sort
func quickSort(input:[Int]) -> [Int] {
    var output = input
    //递归,其实可以用闭包来实现,这里为了方便理解,使用嵌套函数来表示
    func quicksort(inout input:[Int], _ low:Int, _ high:Int) {
        guard low else { return }//递归完成
        
        let pivotkey = input[low]
        var left = low
        var righ = high
        
        while left < righ {
            while left = pivotkey { --righ }
            input[left] = input[righ]
            while left left }
            input[righ] = input[left]
        }
        //移动轴的位置,使得轴左边的数总比右边的数小
        input[left] = pivotkey
        
        quicksort(&input, low, left - 1)
        quicksort(&input, left + 1, high)
        
    }
    quicksort(&output, 0, output.count - 1)
    return output
}
unnumber.sort()
quickSort(unnumber)
quickSort(number)
quickSort(number1)
quickSort(number2)

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//Select Sort
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

//Select Sort
func selectSort(input:[Int]) -> [Int] {
    var output = input
    
    for var i = 0; i  {
        for var j = i + 1; j  {
            if output[i] > output[j] {
                swapValue(&output[i], &output[j])
            }
        }
    }
    return output
}
unnumber.sort()
selectSort(unnumber)
selectSort(number)
selectSort(number1)
selectSort(number2)

//Select Sort Improve
func selectSortImprove(input:[Int]) -> [Int] {
    var output = input
    //递归调用,每次都选出最大最小放到数组的两端
    func selectsortimprove(inout input:[Int], _ low:Int, _ high:Int) {
        guard low else { return }
        
        for var i = low; i <= high; i++ {
            if input[i] > input[high] { swapValue(&input[high], &input[i]) }
            if input[i] input[i]) }
        }
        selectsortimprove(&input, low + 1, high - 1)
    }
    selectsortimprove(&output, 0, output.count - 1)
    
    return output
}
unnumber.sort()
selectSortImprove(unnumber)
selectSortImprove(number)
selectSortImprove(number1)
selectSortImprove(number2)