快速排序 Swift 一个萝卜一个坑解法

原理:

快速排序使用分治法（Divide and conquer）策略来把一个序列（list）分为两个子序列（sub-lists）。

步骤：

• 从数列中挑出一个元素，称为"基准"（pivot）

• 重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任一边）

• 递归地（recursively）把小于基准值元素的子数列和大于基准值元素的子数列排序。

标准理解版实现：

var array = [5, 8, 5, 7, 41, 2, 43, 6, 601, 61, 52, 33, 6, 7, 61, 1, 3, 6, 31, 2, 30, 6]

func quickSort(start: Int, end: Int) {
    if start >= end {
        return
    }
    else if end - start == 1 {
        if array[start] > array [end] {
            let tmp = array[start]
            array[start] = array [end]
            array[end] = tmp
        }
        return
    }
    else {
        var tmpIndex = start
        let povit = array[start]
        var left = start + 1
        var right = end
        var moveRight = true
        
        while left <= right {
            if moveRight {
                while (array [right] > povit && left <= right) {
                    right -= 1
                }
                array[tmpIndex] = array [right]
                tmpIndex = right
                right -= 1
                moveRight = false
                continue
            } else {
                while (array [left] <= povit && left <= right) {
                    left += 1
                }
                array[tmpIndex] = array [left]
                tmpIndex = left
                left += 1
                moveRight = true
                continue
            }
        }
        array[tmpIndex] = povit
        quickSort(start: start, end: tmpIndex - 1)
        quickSort(start: tmpIndex + 1, end: end)
    }
}

let _ = quickSort(start: 0, end: array.count - 1)
print(array)

优化精简版实现:

func quickSort(start: Int, end: Int) {
    if start >= end { return }
    var left = start
    var right = end
    let povit = array[start]
    while left < right {
        while (array [right] > povit && left < right) {
            right -= 1
        }
        if left < right {
            array[left] = array [right]
        }
        while (array [left] <= povit && left < right) {
            left += 1
        }
         if left < right {
            array[right] = array [left]
        }
    }
    array[left] = povit
    quickSort(start: start, end: left - 1)
    quickSort(start: left + 1, end: end)
}

快速排序 Swift之Array.filter(高阶函数)实现

走过、路过： 请多指教！