1. def Partition(arr, low, high):
  2.     pivot = arr[low]  # 将第一个元素设置为枢纽
  3.     while low < high:
  4.         while low < high and arr[high] >= pivot:
  5.             high -= 1
  6.         arr[low] = arr[high]
  7.         while low < high and arr[low] <= pivot:
  8.             low += 1
  9.         arr[high] = arr[low]
  10.     arr[low] = pivot
  11.     return low # 返回枢纽最终的存放位置
  14. def quickSort(arr, low, high):
  15.     if low < high:
  16.         pivotpos = Partition(arr, low, high) # 划分
  17.         # 对左右两个子数组递归进行划分
  18.         quickSort(arr, low, pivotpos-1)
  19.         quickSort(arr, pivotpos+1, high)
  22. if __name__ == '__main__':
  23.     array = [1,2,3,5,2,5,7,4,21,6]
  24.     quickSort(array, 0, len(array)-1)
  25.     print(array)

三路快排

  1. import random
  4. def swap(arr, i, j):
  5.     arr[i], arr[j] = arr[j], arr[i]
  8. def Partition(arr, low, high):
  9.     swap(arr, low, random.randint(low, high))  
  10.     pivot = arr[low]  # 将第一个元素设置为枢纽
  11.     # 设置小于pivot元素的区间的右端点p1,大于pivot元素的集合区间的左端点p2
  12.     # 当前元素cur
  13.     p1, p2, cur = low, high, low
  14.     while cur <= p2:
  15.         if arr[cur] < pivot:
  16.             swap(arr, p1, cur)
  17.             p1 += 1
  18.             cur += 1 
  19.         elif arr[cur] > pivot:
  20.             swap(arr, cur, p2)
  21.             p2 -= 1
  22.         else:
  23.             cur += 1
  24.     print(p1, p2)
  25.     print(arr)
  26.     return p1, p2  # 返回的是pivot元素的集合的区间左端点和右端点
  29. def quickSort(arr, low, high):
  30.     if low < high:
  31.         pivotposl, pivotposr = Partition(arr, low, high) # 划分
  32.         # 对左右两个子数组递归进行划分
  33.         quickSort(arr, low, pivotposl-1)
  34.         quickSort(arr, pivotposr+1, high)
  37. if __name__ == '__main__':
  38.     array = [5,2,3,1,2,5,7,4,21,6]
  39.     size = len(array)
  40.     if size >= 2:
  41.         quickSort(array, 0, size-1)
  42.     print(array)