排序算法之快排

快速排序（Quicksort）是对冒泡排序的一种改进。

原理：

1. 通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小。
2. 然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列

Swift代码

func quickSort(numbers: inout [Int], left:Int, right:Int) {
    
    //递归条件结束
    if left >= right {
        return;
    }
    var i = left;
    var j = right;
    let key = numbers[i];
    while i < j {
        //从右边开始比较，比key大的数位置不变
        while i < j && numbers[j] >= key {
            j -= 1;
        }
        //只要出现一个比key小的数，则将这个数放入左边i的位置
        numbers[i] = numbers[j];
        
        //从左边开始比较，比key小的数位置不变
        while i < j && numbers[i] <= key {
            i += 1;
        }
        //只要出现比key大的数，则将这个数放入右边j的位置
        numbers[j] = numbers[i];
    }
    //将key放入i的位置，则左侧数都比key小，右侧数都比key大
    numbers[i] = key;
    //左递归
    quickSort(numbers: &numbers, left: left, right: right - 1);
    //右递归
    quickSort(numbers: &numbers, left: left + 1, right: right);
}

示例：

var nums = [9,8,2,1,3,5,4];
quickSort(numbers: &nums, left: 0, right: nums.count-1);
//打印nums为：[1, 2, 3, 4, 5, 8, 9]