Python实现快速排序

#encoding=utf-8

#QuickSort1是我按照定义写的，觉得比QuickSort2更好。因为前者每划分一次只要遍历列表一遍，而QuickSort2却要两遍。

def QuickSort1(list):

    if len(list)<=1:

        return list

    keyval=list[0]

    keydex=0

    low=0

    high=len(list)-1

    while low!=high:

        if keydex == low:

            if list[high] <= keyval:

                list[keydex] = list[high]

                keydex = high

                low = low+1

            else:

                high = high-1    

        elif keydex == high:

            if list[low] >= keyval:

                list[keydex] = list[low]

                keydex = low

                high = high-1

            else:

                low = low+1

    list[low] = keyval

    return QuickSort1(list[:keydex])+[keyval]+QuickSort1(list[keydex+1:])   

                          

            

def QuickSort2(list):

    if not list:

        return []

    return QuickSort2([x for x in list[1:] if x <= list[0]])+list[0:1]+QuickSort2([x for x in list[1:] if x > list[0]])

        

            

        

#测试

mylist = [5,2,3,9,0,8,6,2,3,1,8]

print '原列表：',mylist     

mylist = QuickSort2(mylist)

print '经过“快速排序”以后：',mylist