1、冒泡排序

    /// 冒泡排序 从小到大
    func bubbleSort(_ arr : [Int]) -> [Int] {
        var arr = arr
        for i in 0 ..< arr.count{
            for j in 0 ..< arr.count - i - 1{
                if arr[j] > arr[j + 1]{
                    (arr[j] , arr[j + 1]) = (arr[j + 1] , arr[j])
                }
            }
        }
        return arr
    }

2、选择排序

    func selectSort(_ arr : [Int]) -> [Int] {
        var arr = arr
        for i in 0 ..< arr.count{
            var minIndex = i
            for j in i ..< arr.count{
                if arr[j] < arr[minIndex]{
                    minIndex = j
                }
            }
            (arr[i] , arr[minIndex]) = (arr[minIndex] , arr[i])
        }
        return arr
    }

3、插入排序

func sertSort(_ arr : [Int]) -> [Int]{
        var arr = arr
        for i in 1 ..< arr.count{
            var j = i
            while arr[j] < arr[j - 1]{
                (arr[j] , arr[j - 1]) = (arr[j - 1] , arr[j])
                j = j - 1
                if j == 0{
                    break
                }
            }
        }
        return arr
    }

4、希尔排序

    func shellSort(_ arr:  [Int]) -> [Int]{
        var arr = arr
        var gap = arr.count / 2
        while gap >= 1{
            for i in 0..<arr.count {
                var j = i
                while j >= 0 , j + gap < arr.count, arr[j] > arr[j + gap]{
                    (arr[j + gap] , arr[j]) = (arr[j] , arr[j + gap])
                    j -= gap
                }
            }
            gap /= 2
        }
        return arr
    }

5、快排

    func quickSort(_ list : inout [Int], low : Int , high : Int){
        if low >= high{
            return
        }
        var i = low,j = high
        let temp = list[low]
        while i < j{
            while i < j , list[j] >= temp{
                j -= 1
            }
            list[i] = list[j]
            while i < j , list[i] <= temp {
                i += 1
            }
            list[j] = list[i]
        }
        let position = i
        list[position] = temp
        quickSort(&list, low: low, high: position - 1)
        quickSort(&list, low: position + 1, high: high)
    }

6、归并排序

    func mergeSort(_ arr : inout [Int],low:Int,high : Int) {
        guard low < high else {
            return
        }
        let mid = (low + high) / 2
        mergeSort(&arr , low: low,high: mid)
        mergeSort(&arr, low: mid + 1, high: high)
        mergeSort(&arr,low: low,high: high,mid: mid)
    }
    func mergeSort(_ arr : inout [Int],low:Int,high : Int,mid : Int) {
        print("low = \(low) ; high = \(high)")
        var helper = Array(repeating: 0, count: arr.count)
        for i in 0 ..< arr.count {
            helper[i] = arr[i]
        }
        var left = low
        var right = mid + 1
        var current = low
        while left <= mid , right <= high {
            if(helper[left] < helper[right]){
                arr[current] = helper[left]
                left += 1
            }else{
                arr[current] = helper[right]
                right += 1
            }
            current += 1
        }
        //处理左边剩下的元素
        let leftLast = mid - left
        if( leftLast >= 0){
            for i in left ... mid{
                arr[current] = helper[i]
                current += 1
            }
        }
    }
    var array = [24,22,21,37,35,34,2, 5, 8, 9, 10, 4, 3, 16, 1, 7, 8,12,11,65,34,67,68,69,41];
    mergeSort(&array,low: 0,high: array.count - 1)
    print(array)