快速排序

快速排序（英语：Quicksort），又称划分交换排序（partition-exchange sort），通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

步骤为：

• 从数列中挑出一个元素，称为"基准"（pivot），
• 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
• 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
• 递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递归下去，但是这个算法总会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。

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



# 原始数据
values = [80, 90, 83, 100, 96, 88, 89, 98, 85, 93]
print(values)
# 调用快速排序获取排序后结果
values = quick_sort(values)
print(values)

# 快速排序


def quick_sort(values):
    # 递归退出条件
    if len(values) < 2:
        return values

    # 设置关键数据
    key = values[0]
    # 取出所有比key小的数据
    smaller = [x for x in values if x < key]
    # 取出所有等于key的数据
    equal = [x for x in values if x == key]
    # 取出所有比key大的数据
    bigger = [x for x in values if x > key]
    # 从小到大排列,小的在前,大的在后
    return quick_sort(smaller) + equal + quick_sort(bigger)
# 原始数据
values = [80, 90, 83, 100, 96, 88, 89, 98, 85, 93]
print(values)
# 调用快速排序获取排序后结果
values = quick_sort(values)
print(values)