• 思路分析：快速排序采用双向查找的策略，每一趟选择当前所有子序列中的一个关键字作为枢纽轴，将子序列中比枢纽轴小的前移，比枢纽轴大的后移，当本趟所有子序列都被枢轴按上述规则划分完毕后将会得到新的一组更短的子序列，他们将成为下趟划分的初始序列集。
  • 算法分析：分裂是O(log n),移动是O(n),综合起来是O(nlog n).而且不需要额外的存储空间。
  • 但是，如果中值所在的分裂点过去偏离中部，造成左右两部分数量不平衡，极端情况下，有一部分始终没有数据，这样的时间复杂度就退化到O(n^2)
  • 如果需要排序的数据表是随机均匀分布，取第一个数字作为中值是可以的。否则，可以用三值采样。 
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):
    pivotvalue = alist[first]
    leftmark = first + 1
    rightmark = last
    done = False
    while not done:
        while leftmark <= rightmark and alist[leftmark] <= pivotvalue:
            leftmark += 1
        while alist[rightmark] >= pivotvalue and leftmark <= rightmark:
            rightmark -= 1
        if rightmark < leftmark:
            done = True
        else:
            alist[leftmark],alist[rightmark] = alist[rightmark],alist[leftmark]
    alist[first],alist[rightmark] = alist[rightmark],alist[first]
    return rightmark
  • 堆排序
    图片说明
  • 桶排序：时间复杂度为O(n)
    图片说明