'''
快速排序原理：对于给定的一组序列，选择一个基准数，通过一论排序后，将原序列分为两部分，
使得前面的比后面的小，然后再依次对前后进行拆分并排序，递归该过程，直到序列中所有数据均有序为止。
算法过程如下：
1.拆分：将序列拆分成2个非空子序列2.递归求解：通过递归调用快速分别对2个子序列进行排序3.合并：把排序好的2个子序列进行合并
例如数组：
{49,38,65,97,76,13,27,49}，具体排序过程如下：
第一次排序过程：
初始化：
[49,38,65,97,76,13,27,49]
第1次交换：[27,38,65,97,76,13,49,49]
第2次交换：[27,38,49,97,76,13,65,49]
第3次交换：[27,38,13,97,76,49,65,49]
第4次交换：[27,38,13,49,76,97,65,49]
整个排序过程：
初始化：
[49,38,65,97,76,13,27,49]
第1次排序后：[27 38 13] 49 [76 97 65 49]
第2次排序后：[13] 27 [38] 49 [49 65] 76 [97]
第3次排序后：13 27 38 49 49 [65] 76 97
最后排序结果：13 27 38 49 49 65 76 97
'''
时间复杂度：
最坏的情况下，每次划分将问题分解后，基准元素的一侧没有元素，其中一侧为规模为n-1的子问题，
递归求解该子问题，所需时间为递归求解该子问题，所需时间为T(n-1),合并：因为是原地排序，
合并不需要时间复杂度，所以时间复杂度为 O(n²)
理想的情况下，每次划分将问题分解为两个规模为n/2的子问题，递归求解两个规模的子问题，
所需时间为
2T(n/2)合并：因为是原地排序，合并不需要时间复杂度，所以时间复杂度为O(nlogn)
空间复杂度：O(logn)
