アルゴリズム導論第三版思考問題8-4
1297 ワード
QUICK-SORT-8-4(C,key,l,r)
j = l-1
for i = l to r
if COMPARE(C[i],key) =< 0
j = j+1
swap(C[i], C[j])
if COMPARE(C[i],key) == 0
k = j
swap(C[j], C[k])
return j
SORT-PROBLEM-8-4(A,B,l,r)
if l < r
p = QUICK-SORT-8-4(A,B[r],l,r)
p = QUICK-SORT-8-4(B,A[p],l,r)
SORT-PROBLEM-8-4(A, B, l, p-1)
SORT-PROBLEM-8-4(A, B, p+1, r)
import random
def COMPARE(a, b):
return (a - b)
def QUICK_SORT_8_4(C, key, l, r):
j = l-1
k = l
for i in range(l, r + 1):
if COMPARE(C[i], key) <= 0:
j = j + 1
temp = C[i]
C[i] = C[j]
C[j] = temp
if COMPARE(temp, key) == 0:
k = j
temp = C[j]
C[j] = C[k]
C[k] = temp
return j
def SORT_PROBLEM_8_4(A, B, l, r):
if l < r:
p = QUICK_SORT_8_4(A, B[r], l, r)
p = QUICK_SORT_8_4(B, A[p], l, r)
SORT_PROBLEM_8_4(A, B, l, p - 1)
SORT_PROBLEM_8_4(A, B, p+1, r)
return
list1 = [i+1 for i in range(30)]
random.shuffle(list1)
list2 = list1.copy()
random.shuffle(list2)
print(list1)
print(list2)
SORT_PROBLEM_8_4(list1, list2, 0, len(list1)-1)
print(list1)
print(list2)
転載先:https://www.cnblogs.com/MrWrong/p/7130510.html