快速排序

"""
主要思路:
首先任意选取一个（一般都是选取需要排序的部分的第一个数据）作为key值，然后将将所有比它小的数放到它前面，
所有比它大的数都放到它后面
复杂度:
O(nlgn)
快速排序的算法:
设置两个变量，一个是开始的位置，设置为0(start)，一个是结束的位置，设置为len(alist)-1(end)
将要排序的部分的第一个数据设置为key，key=alist[start]
下面两个步骤的顺序不能发生变化，必须是先从尾部调整，再从头部调整
1.从尾部开始向前搜索，同时索引-1(end -= 1)，直到找到一个数小于key值，那么就将值赋给start位置
   alist[start] = alist[end]
2.从头部开始向后搜索，同时索引+1(start += 1)，直到找到一个大于key值，将值赋给end位置
   alist[end] = alist[start]
重复上面两步，直到start >= end
"""


def quick_sort(alist, start, end):
   # 判断是否还需要排序
   if start < end:
      low = start
      high = end
      # 保存key值
      key = alist[start]

      while low < high:
         # 从尾部开始，如果值大于等于key值，那么将索引前移
         while low < high and alist[high] >= key:
            high -= 1
         # 将尾部索引的值赋值给头部索引处
         alist[low] = alist[high]

         # 从头部开始，如果值小于等于key值，那么就把索引往后移
         while low < high and alist[low] <= key:
            low += 1
         # 将索引值赋值给尾部索引处的值
         alist[high] = alist[low]

      # 做完一轮比价后，列表被分成了两个半区，并且low==high，需要将此处的值设置为key
      alist[low] = key
      # 递归前后两个半区
      quick_sort(alist, start, low - 1)
      quick_sort(alist, high + 1, end)


if __name__ == '__main__':
   import random

   # 随机得到10个数
   alist = [random.randint(0, 100) for _ in range(10)]
   print(alist)
   quick_sort(alist, 0, len(alist) - 1)
   print(alist)