斯坦福算法专项课程Course1 week3算法实现

这次回顾第三周的算法。

课程地址:https://www.coursera.org/specializations/algorithms

Quick Sort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
import numpy as np

def Exchange(A, i, j):
#交换元素的值
p = A[i]
A[i] = A[j]
A[j] = p

def Partion(A, l, r):
p = A[l]
i = l + 1
for j in range(l + 1, r + 1):
if (A[j] < p):
Exchange(A, i, j)
i += 1
Exchange(A, l, i - 1)

return i - 1

def Quick_Sort(A, l, r):
n = r - l + 1
if (n <= 1):
return
#返回pivot的位置
i = Partion(A, l, r)
Quick_Sort(A, l, i - 1)
Quick_Sort(A, i + 1, r)

def QuickSort(A):
n = len(A)
Quick_Sort(A, 0, n - 1)

#测试
N = 1000
Max = 1e5
data = np.random.randint(0, Max, size=N)
data_sort = np.sort(data)
#排序
QuickSort(data)
#测试结果
print(np.sum(data != data_sort))