1. 基本思想
通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据比另一部分的所有数据要小，再按这种方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，使整个数据变成有序序列。
2. 原理
举例说明: 数组
1.两个游标 i 和 j, i在数组左边最前一位向前移动, j在数组最后一位向后移动.
开始移动
2.以数组第一位3为基准, j开始移动,遇到比3小的值 2 停止移动,i开始移动,遇到比3大的值 7 停止移动.
i遇到比3大的停止移动,j遇到比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);//递归的处理当前两个游标位置的左边无序数组
}
