快速排序算法的實現及相關測試算法的原理與實現
快速排序簡介
快速排序是一種分治的排序算法，是實踐中最快的排序算法，理論上的時間復雜度為O(N*lgN)，最差情況的時間復雜度為O(N^2)，但稍加努力就可避免這種情況。
理論時間復雜度為O(N*lgN)還有堆排序、插入排序等，但這些算法因為需要動態的分配內存或合并內存，在實踐中的性能不如快速排序。
快速排序的步驟
- 如果列表中的元素為0或1個，則返回
- 選取標記值p
- 將列表分為兩部分s1、s2，需滿足條件：s1中的元素均小于或等于p，s2中的元素均大于等于p，得到s1+p+s2
- 對s1、s2重復2、3步驟，最終得到排序結果
從上面的步驟可以看出，快速排序需要遞歸運算。
Python實現
采用三值取中間值的方法選取標記值，從而避免最差情況。
def median3(L,a,b,c):
if L[a] >= L[b] and L[b] >= L[c]:
mid = L[b]
i = b
elif L[a] <= L[b] and L[b] <= L[c]:
mid = L[b]
i = b
elif L[b] >= L[a] and L[a] >= L[c]:
mid = L[a]
i = a
elif L[b] <= L[a] and L[a] <= L[c]:
mid = L[a]
i = a
else:
mid = L[c]
i = c
return [mid,i]
def swap(L, i, j):
tmp = L[i]
L[i] = L[j]
L[j] = tmp
def quickSort(L, low, high):
if low < high:
i = low
j = high
meta = median3(L, i, (i+j)/2, j)
pivot = meta[0]
pivotPos = meta[1]
# move pivot to the right end
swap(L, pivotPos, high)
while i < j:
# pivot on the right end, starting from left
while i < j and L[i] <= pivot:
i = i+1
while j > i and L[j] >= pivot:
j = j-1
swap(L, i, j)
# move pivot to right position
swap(L, i, high)
quickSort(L, low, i-1)
quickSort(L, i+1, high)</code></pre>
測試算法
測試排序結果是否正確，需滿足條件
- 列表除元素順序變化外，沒有別的變化
- 列表中的元素是有序的
條件2容易實現，重點關注條件1
如何確保列表除元素順序變化外，沒有別的變化？
列表L1、L2滿足以下三個條件即可
- L1、L2中的元素數量相同
- L1、L2的元素組成的集合相同（L1中的元素都在L2中，反之也成立）
- L1、L2中元素的和相同
例如，列表L1=[2,3,2,2,3]，順序打亂后得到L2=[2,2,3,3,2]，此時L1、L2滿足以上三個條件。如果對L2進行以下操作，均會使其中的一個或多個條件不成立。
- 添加/刪除元素
- 修改元素值
測試算法實現
import sys
import random
import copy
condition 2
def diff2List(l1,l2):
diff = [val for val in l1 if val not in l2]
for v in [val for val in l2 if val not in l1]:
diff.append(v)
return diff
def isListSorted(L):
i = 0
while i < len(L) - 2:
if L[i] <= L[i+1]:
i = i+1
else:
return [i, L[i], L[i+1]]
return True
condition 3
def sumList(L):
sum = 0
for i in L:
sum = sum + i
return sum
def randomList(length, maximum):
l = []
i = 0
while i < length:
l.append(random.randint(0, maximum))
i = i+1
return l
#
Test usage: python <script_path> <test_times> <min_list_length> <max_list_length> <max_list_element_value>
#
testTimes = int(sys.argv[1])
minLength = int(sys.argv[2])
maxLength = int(sys.argv[3])
maxValue = int(sys.argv[4])
for i in range(testTimes):
L = randomList(random.randint(minLength, maxLength), maxValue)
print 'Test round #' + str(i)
# original
print L
# deep copy for test
tmpList = copy.deepcopy(L)
quickSort(L, 0, len(L) - 1)
if len(L) != len(tmpList) or diff2List(L, tmpList) != [] or sumList(L) != sumList(tmpList):
print 'Bad #not coherent'
break
else:
sorted = isListSorted(L)
if sorted != True:
print 'Bad #not sorted'
print sorted
# after sort
print L</code></pre>
來自：http://www.jianshu.com/p/0aef1e132b9b