β

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

乡村运维 115 阅读
#!/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 randint
from pprint import pprint

arr = [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]
作者:乡村运维
运维,开发那些事
原文地址:【算法&数据结构】再次学算法之快速排序, 感谢原作者分享。

发表评论