python 快速排序

快速排序步骤为：

• 挑选基准值：从数列中挑出一个元素，称为“基准”(pivot):
• 分割：重新排序数列，所有比基准小的元素摆放在基准前面，所有比基准大的元素摆在基准后面（与基准值相等的数可以到任何一边）。在这个分割结束后，对基准值的排序就已经完成；
• 递归排序子序列：递归地将小于基准值元素的子序列和大于基准值元素的子序列排序。
• 递归到底部的判断条件是数列的大小是零或一，此时该数列显然已经有序。
• 选取基准值有数中方法，此选取方法对排序时间性能有决定性影响。

实例一：

def partition(arr,low,high):
    i = low -1 #最小元素索引
    pivot = arr[high]
    for j in range(low,high):
        # 当前元素最小或等于pivot
        if arr[j] <= pivot:
            i = i+1
            arr[i],arr[j] = arr[j],arr[i]
    arr[i+1],arr[high] = arr[high],arr[i+1]
    return i+1

# arr[] --> 排序数组
# low --> 起始数组
#high --> 结束数组

# 快速排序函数
def quickSort(arr,low,high):
    if low < high:
        pi = partition(arr,low,high)
        quickSort(arr, low, pi-1)
        quickSort(arr, pi+1, high)

arr = [11,99,33,69,77,88,55,11,33,36,39,66,44,22]
n = len(arr)
quickSort(arr,0,n-1)
print("排序后的数组：")
for i in range(n):
    print("%d" % arr[i])

输出结果

排序后的数组：
11
11
22
33
33
36
39
44
55
66
69
77
88
99

实例二：

def quick_sort(arr):
    """ 快速排序 """
    if len(arr) < 2:
        return arr
    #选取基准，随便哪一个都可以，选中间的便于理解
    mid = arr[len(arr)//2]
    #定义基准左右两个数列
    left, right = [], []
    #从原始数组中移除基准值
    arr.remove(mid)
    for item in arr:
        #大于基准值放右边
        if item >= mid:
            right.append(item)
        else:
            #小于基准值放左边
            left.append(item)
    #使用迭代进行比较
    return quick_sort(left) + [mid] + quick_sort(right)

l= [11,99,33,69,77,88,55,11,33,36,39,66,44,22]
quick_sort(l)

输出结果：

[11, 11, 22, 33, 33, 36, 39, 44, 55, 66, 69, 77, 88, 99]