python快排算法学习分享

cztanghao

# Version : 1.0
# Author  : 汤灏
# File    : quick_sort.py
# Time    : 2024/1/30 19:06
def quick(data, start, end):
    if start >= end:  # 如果区间不合法，则直接返回
        return
    i, j = start, end
    pivot = data[start]  # 选择基准值
    while i < j:  # 循环直到 i 与 j 相遇
        while i < j and data[i] <= pivot:  # 从左向右找大于基准的元素
            i += 1
        while i < j and data[j] >= pivot:  # 从右向左找小于基准的元素
            j -= 1

        if i < j:  # 交换左右两侧的元素
            data[i], data[j] = data[j], data[i]
    # 将基准值交换到中间位置
    data[start], data[j] = data[j], data[start]
    # data[start], data = data, data[start]
    # 递归排序基准值左侧和右侧的子序列
    quick(data, start, j - 1)
    quick(data, j + 1, end)

# 测试代码
data = [6, 1, 2, 7, 9, 3, 4, 5, 10, 8]
print("原始数据为：")
print(data)
print("--------------------------------")
quick(data, 0, (len(data) - 1))
print("排序之后的数据为：")
print(data)
print("--------------------------------")    这个是升序的情况，快排，就是假设第一个数字是中间值，然后其他之外的左边半部分都小于他，右边的半部分都大于他，然后开始双向向实际的中间位置走，当左边出现大于基准值，右边出现小于基准值的时候，再看看左边的那个是不是在右边的那个的左边，此时只需要兑换这两个，继续比较直到发现左边的那个跑到右边的那个右边去了，此时跑右边去了的那个左边的，因为在右边本来就应该大于基准值，所以不动，而右边的那个跑到左边的左边去了的本应该大于基准值，但是现在小于基准值， 那他就应该跟基准值对换，此时，假设的中间值就真的到了中间值的位置上。概况：

• 选取基准值：快速排序首先选择一个基准值（pivot），通常可以选择区间的第一个元素。
• 分区操作：算法的目标是要将小于基准值的元素移动到基准值的左侧，将大于基准值的元素移动到基准值的右侧。这一步骤称为分区（partitioning）。
• 双向遍历：使用两个指针，一个从左侧开始向右移动，直到找到一个大于基准值的元素；另一个从右侧开始向左移动，直到找到一个小于基准值的元素。
• 元素交换：当左侧指针指向的元素大于基准值且右侧指针指向的元素小于基准值时，如果左侧指针在右侧指针的左侧，则交换这两个元素的位置，然后继续遍历。
• 递归过程：当两个指针相遇时，通常会有两种策略。如果是先移动左指针，相遇时将基准值与左指针指向的元素交换；如果是先移动右指针，相遇时将基准值与右指针指向的元素交换。在您的描述中，是后一种情况。
• 完成分区：在指针相遇且右指针指向的元素小于基准值时，将右指针指向的元素与基准值交换，此时基准值被放置在其最终位置。
• 递归排序：一旦基准值被放置在正确的位置，算法会递归地对基准值左侧和右侧的子序列进行快速排序，重复以上步骤直到整个序列有序。