sunsongxp · April 9, 2021 17:46 · Apr 9, 2021
diff --git a/quicksort.py b/quicksort.py
@@ -0,0 +1,35 @@
+#!/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)