【算法&数据结构】再次学算法之快速排序

#!/usr/bin/env python# *-* coding:utf-8  *-*"""    快速排序算法"""def quickSort(start,end,arr):    # 始终要保证，两边的哨兵不要越位，最多是相遇    if start > end :        return    #第一步: 找到一个基准数，并把两边"哨兵"的位置赋值给两个临时变量    firstItem = arr[start]    print  "".join(str(arr))    left ,right = start ,end    while(left != right):        #第二步，从右边，记住是从右边找到一个比基准数大的数，然后停下来，记下现在的位置        while(arr[right] >= firstItem and left < right ):            right -= 1        #第三步，从左边，找到一个比基准数小的数，然后停下来，记下现在的位置        while(arr[left] <= firstItem and left < right):            left += 1        #第四步，交换左边和右边找到的这俩满足条件的值,并且两位"哨兵"没有相遇        if(left < right):            arr[left] ,arr[right] = arr[right] ,arr[left]            print  "".join(str(arr))    #第五步: 把基准数和哨兵相遇的位置交换一下    if left == right : #其实这一步判断可以省略        arr[start] = arr[left]        arr[left]  = firstItem    #第六步：重复把基准数左边的排一下    quickSort(start,left - 1, arr)    #第七步：重复把基准数右边边的排一下    quickSort(right + 1 ,end, arr)from random import randintfrom pprint import pprintarr = [randint(0,100) for i in range(10)]quickSort(0,len(arr) -1   ,arr)print arr

output

$ python quickSort.py[53, 95, 79, 16, 90, 30, 56, 22, 55, 18][53, 18, 79, 16, 90, 30, 56, 22, 55, 95][53, 18, 22, 16, 90, 30, 56, 79, 55, 95][53, 18, 22, 16, 30, 90, 56, 79, 55, 95][30, 18, 22, 16, 53, 90, 56, 79, 55, 95][16, 18, 22, 30, 53, 90, 56, 79, 55, 95][16, 18, 22, 30, 53, 90, 56, 79, 55, 95][16, 18, 22, 30, 53, 90, 56, 79, 55, 95][16, 18, 22, 30, 53, 90, 56, 79, 55, 95][16, 18, 22, 30, 53, 55, 56, 79, 90, 95][16, 18, 22, 30, 53, 55, 56, 79, 90, 95][16, 18, 22, 30, 53, 55, 56, 79, 90, 95][16, 18, 22, 30, 53, 55, 56, 79, 90, 95][16, 18, 22, 30, 53, 55, 56, 79, 90, 95]