1.快速排序 思想
也主要利用了分治法的思想，先将待排序序列分为两部分。 如下图所示，若以4为划分的标准，划分为两部分之后，左边部分要比4小，右边部分要比4大。
2. 快速排序具体过程
设置两个游标 l跟r(l代表left，r代表right)；设置基准值pivot，有教程说随机设置基准值效率更高，这里设置数组最右的那个元素为基准值；left游标 从左向右移动，当游标指向元素大于基准值时，则跳出while循环，交换r游标指向的元素；同理 right右标向左移动，当游标指向元素小于基准值时，则跳出while循环，交换l游标指向的元素；当左右游标相等时停止循环，赋值基准值给左游标指向的元素,就得到了分治法划分的两部分；对基准值左边的元素递归，重复以上步骤；注意：要设置条件退出递归。
3. python 代码实现：
class Solution:
def quickSort(self,arr,l,r):
#设置两游标
i = l
j = r
while(i > j):#定义跳出递归的条件
return arr
pivot = arr[r] #将待排序的最后一个数定义为基准
while(i < j):#将待排序数组分为两部分，左边部分比pivot小，右边部分比pivot大
#两游标从两端往中间移动
while(i < j and arr[i] <= pivot):
i = i + 1
arr[j] = arr[i]
while(i < j and arr[j] > pivot):
j = j - 1
arr[i] = arr[j]
arr[j] = pivot
self.quickSort(arr, l, j - 1)
self.quickSort(arr, j + 1, r)
return arr
s = Solution()
arrayA = [4,6,2,3,1,5,7,8]
result = s.quickSort(arrayA,0,len(arrayA)-1)
print(result)
代码运行结果：
[1, 2, 3, 4, 5, 6, 7, 8]
4. 快速排序时间复杂度
O(nlogn)
