快速排序

0.快速排序.png

思想

以某个数为基准，将比它小的都移到它左边，比它大的都移动到它右边，然后分别再对其左右子数组进行同样的操作。
怎么移动？
从数组的第一位和最后一位同时进行遍历，如果从左到右遍历到数比基准数大，从右到左遍历到的数比基准数小，那么就将这两个数的位置进行交换，直到左右两边遍历的下标相遇，同时将相遇的下标位置上的数和基准数位置交换。

代码

// 快速排序
struct Quick {
    
    static func sort(array: inout [Int]) {
        sort(array: &array, min: 0, max: array.count - 1)
    }
    
    /// 对数组某个区间进行排序
    private static func sort(array: inout [Int], min: Int, max: Int) {
        if max <= min {
            return
        }
        
        let par = partition(array: &array, min: min, max: max)
        sort(array: &array, min: min, max: par - 1)
        sort(array: &array, min: par + 1, max: max)
    }
    
    /// 返回中间值下标
    private static func partition(array: inout [Int], min: Int, max: Int) -> Int {
        let key = array[min]
        var left = min + 1
        var right = max
        while true {
            
            while array[right] > key {
                right -= 1
                if right == min {
                    break
                }
            }
            
            while array[left] < key {
                left += 1
                if left == max {
                    break
                }
            }
            
            if left >= right {
                break
            } else {
                exchange(array: &array, aIndex: left, bIndex: right)
            }
        }
        exchange(array: &array, aIndex: min, bIndex: right)
        return right
    }
    
    /// 比较大小
    private static func less(a: Int, b: Int) -> Bool {
        if a < b {
            return true
        } else {
            return false
        }
    }
    
    /// 交换位置
    private static func exchange( array: inout [Int], aIndex: Int, bIndex: Int) {
        let temp = array[aIndex]
        array[aIndex] = array[bIndex]
        array[bIndex] = temp
    }
    
}

demo地址：https://github.com/yangguanghei/studyAlgorithm