经典排序之快速排序

快速排序(quick sort)是一种分治排序算法，该算法首先选取一个划分元素，(partition element)，也称为pivot；然后重新排列，将其划分为3部分。即left（小于划分元素pivot的部分），pivot（划分元素）、right（大于划分元素pivot的部分），此时划分元素pivot已经在列表的最终位置上；最后分别对left和right两部分进行递归排序。

其中，划分元素的选取直接影响快速排序算法的效率，通常选择排序列表的第一个元素，中间元素或最后一个元素作为划分元素，当然也有更复杂的选择方式。划分过程根据划分元素重排列表，是快速排序算法的关键所在。

快速排序算法的优点是原位排序（只用很小的辅助栈），平均时间复杂度为O（n log n），快速排序算法的缺点是不稳定，最坏的情况下时间复杂度为O（n^2）。

代码实现如下：

#!/usr/bin/python3
#-*- coding: utf-8 -*-

def quicksort(L):
  qsort(L,0,len(L)-1)

def qsort(L,first,last):
  if first<last:
    split=partition(L,first,last)
    qsort(L,first,split-1)
    qsort(L,split+1,last)

def partition(L,first,last):
  #选取列表中的第一个元素作为划分元素
  pivot==L[first]
  leftmark=first+1
  rightmark=last
  while True:
    while L[leftmark]<=pivot
    #如果列表中存在与划分元素相等的元素，让他位于left部分
    #以下检测用于划分元素pivot是列表中的最大元素时
    #防止leftmark越界
      if leftmark==rightmark
        break
      leftmark+=1
    while L[rightmark]:
      #这里不需要检测，划分元素pivot是列表中的最小元素时
      #rightmark自动停在first处
      rightmark-=1
    if leftmark < rightmark:
      #此时，leftmark处的元素大于pivot
      #rightmark处的元素小于pivot，两者交换
      L[leftmark],L[rightmark]=L[rightmark],L[leftmark]
    else:
      break
  #交换first处的划分元素与rightmark处的元素
  L[first],L[rightmark]=L[rightmark],L[first]
  #返回划分元素pivot的最终位置
  return rightmark

函数调用示例：

num_list=[5,-4,6,3,7,11,1,2]
print('排序之前：'+str(num_list))
quicksort(num_list)
print('排序之后：'+str(num_list))

执行结果如下：
排序之前：[5,-4,6,3,7,11,1,2]
排序之后: [-4,1,2,3,5,6,7,11]

---

❤️

---