快速排序.md

快速排序的实现原理（思想）

快慢指针和递归思想。 慢指针在快指针动完以后才动。 指定列表中的尾元素作为参考值P，将满指针i指向列表首元素前一位的位置，将快指针j指向列表首元素。 比较j与P的大小，如果j<P，交换i和j位置对应的元素值，并把i+1，j+1； 如果j>=P，j+1 ！！！！！！！！！注意！！！！！！！！！！！

这个不完整，而且有问题，等纠正完错误以后再删除这个注意 ！！！！！！！！！！！！！！！！！！！！！！ 精髓在于确定当前慢指针的索引。

图解

快速排序

python实现

# 快速排序

def locate_index(target, start_position, end_position):
    povit = target[end_position]
    i = start_position - 1
    for j in range(start_position, end_position):
        if target[j] < povit:
            i += 1
            target[i], target[j] = target[j], target[i]
        j += 1

    print("慢指针索引为：", i + 1)
    target[i + 1], target[end_position] = target[end_position], target[i + 1]
    return i + 1


def quick_sort(target, start_position, end_position):
    if start_position < end_position:
        povit_index = locate_index(target, start_position, end_position)
        quick_sort(target, start_position, povit_index - 1)
        quick_sort(target, povit_index + 1, end_position)


a = [3, 5, 1, 2, 7, 6, 4]

quick_sort(a, 0, len(a) - 1)

print(a)