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
| def quickSort(alist): quickSortHelper(alist, 0, len(alist)-1)
def quickSortHelper(alist, first, last): if first<last: splitpoint = partition(alist, first, last) quickSortHelper(alist, first, splitpoint-1) quickSortHelper(alist, splitpoint + 1, last)
def partition(alist, first, last): pivot = alist[first] leftmark = first + 1 rightmark = last done = False while not done: while leftmark <= rightmark and alist[leftmark] <= pivot: leftmark += 1 while rightmark >= leftmark and alist[rightmark] >= pivot: rightmark -= 1 if rightmark < leftmark: done = True else: tmp = alist[leftmark] alist[leftmark] = alist[rightmark] alist[rightmark] = tmp tmp = alist[first] alist[first] = alist[rightmark] alist[rightmark] = tmp return rightmark
|