快速排序算法

每一轮选择一个基准元素，并让其他比它大的元素移动到数列一边，比它小的元素移动到数列的另一边，从而把数列拆解成两个部分，即分治法。

基准元素的选择
在分治过程中，以基准元素为中心，把其他元素移动到基准元素的左右两边，一般可选开始元素为基准元素或者随机选择

元素的交换
选定了基准元素，要把其他小于基准元素的交换到基准元素的一边，其他大于基准元素的交换到基准元素的另一边，以下有两种办法，单边循环（单指针）和双边循环（双指针）

快速排序算法的时间复杂度?
快速排序算法的时间复杂度是O(nlogn)

单边循环法

要点!
首先选定基准元素
设置一个mark指针指向数列起始位置（mark指针代表小于基准元素的区域边界）
从基准元素的下一个位置遍历数组，大于基准元素则继续遍历
小于基准元素，则把基准元素右移一位（因为小于基准元素区域变大了），交换当前遍历元素和mark指针所在元素位置
注意！！！，每遍历一轮的最后都需要将mark指针所在元素和pivot指针所在元素交换，因为mark指针所在元素也属于小于基准元素的区域

  1. """快速排序"""
  2. def quick_sort(start_index, end_index, array):
  3.     if start_index >= end_index:    # 开始指针大于等于结束指针，则一轮递归结束
  4.         return
  5.     pivot_index = partition_v1(start_index, end_index, array)   # 定义基准元素位置
  6.     quick_sort(start_index, pivot_index-1, array)   # 递归排序小于基准位置区域
  7.     quick_sort(pivot_index + 1, end_index, array)   # 递归排序大于基准位置区域
  8.     return array
  11. def partition_v1(start_index, end_index, array):
  12.     pivot = array[start_index]  # 定义基准元素
  13.     mark = start_index  # mark指针代表小于基准元素的边界
  14.     for i in range(start_index + 1, end_index + 1):
  15.         if array[i] < pivot:
  16.             mark += 1   # 如果元素小于基准元素，则mark右移，小于基准位置的区域变大
  17.             array[mark], array[i] = array[i], array[mark]   # 交换当前元素和mark指针元素
  18.     array[mark], array[start_index] = pivot, array[mark]    # 当前最新mark指针元素和基准指针元素，因为mark指针元素也在小于基准指针范围内
  19.     return mark
  21. print(quick_sort(0, len([9, 6, 4, 2, 1, 4, 5])-1, [9, 6, 4, 2, 1, 4, 5]))

双边循环法

非递归实现