8大排序算法之Swift

App 开发是对计算机语言的使用，当然也需要设计算法的使用。虽然作为iOS开发,似乎接触的更多是界面和数据的处理， 但是，在实际开发中， 算法的使用能更高效的处理数据，同时算法能帮助我们更好的了解底层语言。

• 冒泡排序
• 选择排序
• 插入排序
• 快速排序
• 希尔排序
• 归并排序
• 堆排序
• 基数排序

1. 冒泡排序代码如下：

   // 冒泡排序 O（n^2）
    func bubbleSort(arr: inout[Int]) -> [Int] {
        for i in 0..<arr.count {
            for j in i + 1..<arr.count {
                if arr[i] > arr[j] {
                    let temp = arr[i]
                    arr[i] = arr[j]
                    arr[j] = temp
                }
            }
            print(arr)
        }
        print("--------最终结果: \(arr)")
        return arr
    }
        return arr
    }

2 . 选择排序算法代码如下：

   // 选择排序 时间复杂度 O（n^2）
    func selectSort(arr: inout[Int]) -> [Int] {
        for i in 0..<arr.count {
            var minIndex = i
            for j in i + 1..<arr.count {
                if arr[minIndex] > arr[j] {
                    minIndex = j
                }
            }
            if i !=  minIndex{
                let temp  = arr[i]
                arr[i] = arr[minIndex]
                arr[minIndex] = temp
            }
            print(arr)
        }
        print("--------最终结果: \(arr)")
        return arr
    }

3. 插入排序算法如下：

// 插入排序
    func insertSort(arr: inout[Int]) -> [Int] {
        for i in 1..<arr.count {
            let temp = arr[i]
            var  j  = i
            while j > 0, temp < arr[j - 1]{
                arr[j] = arr[j - 1]
                j -= 1
            }
            arr[j] = temp
            print(arr)
        }
        return arr
    }

4. 快速排序算法如下：

// 快速排序
    func partition(arr: inout[Int], left: Int, right: Int) -> Int {
        var left = left
        var right = right
        let pivot = arr[left]
        
        while left < right {
            while left < right, arr[right] >= pivot{
                right -= 1
            }
            arr[left] = arr[right]
            while left < right, arr[left] <= pivot{
                left += 1
            }
            arr[right] = arr[left]
        }
        arr[left] = pivot
        
        print(arr)
        return left
    }
    
    func quickSort(arr: inout[Int], left: Int, right: Int){
        guard left <= right else {
            return
        }
        let prvotIndex = partition(arr: &arr, left: left, right: right)
        quickSort(arr: &arr, left: left, right: prvotIndex - 1)
        quickSort(arr: &arr, left: prvotIndex + 1, right: right)
    }