1. 基本思想

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据比另一部分的所有数据要小，再按这种方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，使整个数据变成有序序列。

2. 原理

举例说明: 数组
1.两个游标 i 和 j, i在数组左边最前一位向前移动, j在数组最后一位向后移动.

开始移动

2.以数组第一位3为基准, j开始移动,遇到比3小的值 2 停止移动,i开始移动,遇到比3大的值 7 停止移动.

i遇到比3大的停止移动,j遇到比3小的,停止移动

3. i和j对应的值交换 变成 3 2 6 9 7 8

交换之后

4.继续移动j,j一直移动到2那里,发现2比3基准值小,停止移动.此时i和j相等.

image.png

5.基准值3 与2 互换,此时发现大于基准值3的都在后面,小于基准值3的都在前面

image.png

6.我们在对数组2 和数组6 9 7 8 在进行同样排序,原理同1,2,3,4,5步骤.

7.排到后面只剩下数组只有一个数字时.i和j都是0,排序结束.

3. 快速排序Swift代码实现

    //快速排序
    func quickSort(arr:inout[Int], left:Int, right:Int) {
        /*终止条件，如果左边界下标等于有边界下标，或者大于右边界下标的时候，说明当前数组的长度已经是1乃至该数组物理上不存在了，
         因此就直接返回，终止递归，这里是递归出口。
        */
        if(left >= right) {return}
        var i = left
        var j = right
        let base = arr[i];//根据传入的左右边界声明出两个游标，同时指定好基准数，我们命名为base
        while(i != j) {//只要左右游标不相等，说明二者没有相遇，循环就会继续执行
            /*j游标先行，只要j游标指向的数值大于基准数，j游标就开始游移，
             需要注意的是在j游标游移的过程中也会时刻注意到i和j游标是否相遇了，只要相遇就停止
             */
            while(i<j && arr[j] >= base) {
                j = j - 1 //j游标是往前走
            }
            /*
             i游标后走，只要是i游标指向的数值小于基准数，i游标就开始游移，需要注意的是i游标在游移的过程中也会时刻注意到i和j游标是否相遇了，只要相遇就停止
             */
            while(i<j && arr[i] <= base) {
                i = i + 1
            }
            /*
             在退出上边的外循环之后，说明二者均指向了需要被交换的元素，也就是说i指向了一个大于基准数的元素，
             j指向了一个小于基准数的元素，因此二者发生交换。如果此时两数不是因为这种指向情况而导致的交换，
             是由于相遇导致的交换，那么这个交换将没有意义
             */
            arr.swapAt(i, j)
            
        }
        arr.swapAt(left, i)//与基准数交换，此时我们已经找到了基准数的准确位置，我们将基准数与当前位置上的元素进行一次交换
        
        quickSort(arr: &arr, left: left, right: i-1);//递归的处理当前两个游标位置的右边无序数组
        quickSort(arr: &arr, left: i+1,right: right);//递归的处理当前两个游标位置的左边无序数组
    }