一、理念
什么是快速排序？
首先确立pivot，比如下图位于末尾
然后i遍历3到6
在3的时候，j指向i前面一位
如果3<=5(pivot)，那么j++，同时将i与j指向的交换，第一次交换是原地不动
一直到遇见9，此时j不动，然后i指向2，j++，j指向9，此时2与9交换，也就是将小的与大的交换。快速排序所要达到的目的是，每轮大循环，确定pivot的位置，以及保证pivot左边都是小于等于他，右边都是大于他
可以看到这里i走到了头，出了循环，此时将pivot与j+1指向的交换，确定了pivot的位置
然后5的左右两边分别再次进行快排
二、手写代码
import random
'''1 首先start不能小于last，退出边界
2 选择pivot放在last位置上
3 遍历start到last-1位置上的数a
如果a<=pivot，则与j指向的值原地交换
如果a>pivot，则j不变，等到下次a>pivot，则a与这个j指向的大值交换
4 循环结束，j+1指向的与pivot交换，将pivot放在合适的位置上，
左边都是小于等于的，右边都是大于他的
5 继续执行快排，分别执行j左边和右边部分 '''
def quick_sort(nums, start, last):
if start >= last:
return
first = start
'''# 1 pivot随机选择
pivot_index = random.randint(start, last)
nums[pivot_index], nums[last] = nums[last], nums[pivot_index]
pivot = nums[last]
# 2 选第一个
nums[first], nums[last] = nums[last], nums[first]
pivot = nums[first]'''
#3 选最后一个
pivot = nums[last]
j = start - 1
for i in range(start, last):
if nums[i] <= pivot:
j += 1
nums[j], nums[i] = nums[i], nums[j]
nums[j + 1], nums[last] = nums[last], nums[j + 1]
print(nums)
print('j:', j, 'pivot:', pivot)
quick_sort(nums, first, j)
quick_sort(nums, j + 2, last)
if __name__ == '__main__':
nums = arr = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
quick_sort(nums, 0, len(nums) - 1)
print("Sorted array is:", nums)三、时间复杂度
O(NlogN)
