快速排序

基本概念
快速排序(QuickSort)是C. A. R. Hoare在1962年提出对冒泡排序的一种改进.

基本思想

• 先从数列中取出一个数作为基准数
• 从右向左将比这个数大的放右边,小的放左边
• 对左右区间重复上一步直到每个区间只有一个数

为什么说是对冒泡排序的一种改进?

• 每次交换是跳跃式的
• 最差时间复杂度和冒泡排序一样,平均复杂度O(NlogN)

理念动效图

image.png

实现

• 需要辅助空间的快速排序
  性能略差一些

func quickSort(_ data:[Int]) -> [Int]{
        
        /// 如果数列数列小于等于1
        if data.count<=1 {
            return data
        }
        
        // 提供左右空间
        var left:[Int] = []
        var right:[Int] = []
        
        // 以数列最后一个值为基准
        let pivot:Int = data[data.count-1]
        
        for index in 0..<data.count-1 {
            if data[index] < pivot {
                left.append(data[index])
            }else{
                right.append(data[index])
            }
        }
        
        /// 获取基准左边新数列
        var result = quickSort(left)
        
        /// 添加基准
        result.append(pivot)
        
        /// 添加基准右边的新数列
        let rightResult = quickSort(right)
        result.append(contentsOf: rightResult)
        
        return result
    }

• 经典快速排序

func quickSort(_ array: [Int]) -> [Int] {
        var newArray = array
        quickSort(&newArray, low: 0, high: newArray.count - 1)
        return newArray
    }
    
    
    func partition(_ array:inout [Int],low:Int,high:Int) -> Int {
        /// 通过位置交换达到分区的效果,不需要占用额外得空间
        let root = array[high]
        var index = low
        
        for i in low...high {
            if array[i] < root {
                if i != index {
                    array.swapAt(i, index)
                }
                index = index+1
            }
        }
        
        if high != index {
            array.swapAt(high, index)
        }
        
        return index
    }
    
    func quickSort(_ array:inout [Int], low:Int, high:Int){
        if low > high {
            return
        }
        /// 进行分区
        let sortIndex = partition(&array, low: low, high: high)
        /// 低位排列
        quickSort(&array, low: low, high: sortIndex-1)
        /// 高位排列
        quickSort(&array, low: sortIndex+1, high: high)
    }