Skip to content

Instantly share code, notes, and snippets.

@sunsongxp

sunsongxp/quicksort.py

Created April 9, 2021 17:46
Show Gist options
  • Save sunsongxp/9e48bedca6862472f4a8cfedd5bd99b6 to your computer and use it in GitHub Desktop.
Save sunsongxp/9e48bedca6862472f4a8cfedd5bd99b6 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
quicksort.py
#!/usr/bin/python3
# Quick Sort 快速排序
# 基于《算法导论》第七章
import random
A = []
for i in range(1000000):
A.append(random.randint(0, 999999))
def parition(A, p, r):
pivot = A[r]
i = p - 1
for q in range(p, r):
if A[q] < pivot:
i += 1
tmp = A[i]
A[i] = A[q]
A[q] = tmp
tmp = A[i+1]
A[i+1] = A[r]
A[r] = tmp
return i+1
def quicksort(A, p, r):
if p < r:
q = parition(A, p, r)
quicksort(A, p, q-1)
quicksort(A, q+1, r)
quicksort(A, 0, len(A)-1)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment