排序算法——快速排序

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

快速排序是不稳定的排序方法，最差时间复杂度和冒泡排序是一样的都是O(n^2)，它的平均时间复杂度为O(n*log2n)，空间复杂度为O(log2n)~O(n)

步骤拆解：
(1)先选择一个基数（比如我们这里选择第一个数5作为基数），先从右往左找一个小于5的数，再从左往右找一个大于5的数，然后交换他们。
（这里我们将两个变量分别称为i和j ,注意，j先开始走），j从数据的最右端开始找比5小的一个数据，找到了4，然后i再从左往右找一个大于5的数，找到了8，两者交换

屏幕快照 2019-03-04 下午4.11.01.png

(2)第一次交换结束，i停留在了4，j停留在了8，然后开始第二次的交换，j继续往左边找比5小的一个数据，找到了3，然后i再从左往右找一个大于5的数，没有找到，遇到了j，i和j相遇，第一轮排序结束。然后将基数5和3进行交换

屏幕快照 2019-03-04 下午4.45.47.png

(3)现在基数5已经归位，它处在序列的第6位。此时我们已经将原来的序列以5为分界点拆分成了两个序列，左边的序列是“3 3 4 0 1”，右边的序列是“6 8 9 6”。接下来还需要分别处理这两个序列。因为5左边和右边的序列目前都还是很混乱的。

屏幕快照 2019-03-04 下午4.51.35.png

(4) 这里首先处理左边的序列，将这个序列以3为基数进行调整，使得3左边的数都小于等于3，3右边的数都大于等于3

屏幕快照 2019-03-04 下午4.55.50.png

(5)一直重复上述操作，直到不可拆分出新的子序列为止

func quickSort(list:Array<Int> , startIndex:Int, lastIndex:Int) -> Array<Int>
{
    var arr = list
    let temp = arr[startIndex]
    var i = startIndex
    var j = lastIndex
    while i < j {
        while (i<j && arr[j] >= temp) {
            j = j - 1
        }
        while (i<j && arr[i] <= temp) {
            i = i + 1
        }
        if (i != j)
        {
            let t = arr[i]
            arr[i] = arr[j]
            arr[j] = t
        }
    }
    arr[startIndex] = arr[i]
    arr[i] = temp
    if (i-startIndex > 1)
    {
        arr = quickSort(list: arr, startIndex: startIndex,lastIndex:i-1)
    }
    if (lastIndex - i  > 1)
    {
        arr = quickSort(list: arr, startIndex: i+1,lastIndex:lastIndex)
    }
    return arr
}

let list = [5,3,8,0,1,3,6,4,9,6]
print(quickSort(list:list , startIndex: 0,lastIndex:list.count-1))