快速排序用双指针实现

快速排序可以使用双指针法来实现。双指针法是通过两个指针i和j分别从数组的两端开始搜索，直到找到需要交换的元素。当i和j相遇时，表示搜索结束。

具体实现步骤如下：
1. 选择一个基准元素，可以是数组的第一个元素或者随机选取一个元素作为基准元素。
2. 初始化两个指针i和j，分别指向数组的起始位置和末尾位置。
3. 从右向左移动指针j，直到找到一个小于等于基准元素的元素。
4. 从左向右移动指针i，直到找到一个大于等于基准元素的元素。
5. 如果i小于等于j，则交换指针i和指针j所指向的元素。
6. 继续执行步骤3到步骤5，直到i大于j。
7. 将基准元素与指针j所指向的元素交换位置，此时基准元素的位置已经确定。
8. 对基准元素左边的子数组和右边的子数组分别进行递归排序，直到子数组的长度为1或者0。

下面是一个使用双指针法实现快速排序的示例代码：

def quick_sort(arr, low, high):
    if low < high:
        pivot_index = partition(arr, low, high)
        quick_sort(arr, low, pivot_index - 1)
        quick_sort(arr, pivot_index + 1, high)

def partition(arr, low, high):
    pivot = arr[low]
    i = low + 1
    j = high

    while True:
        while i <= j and arr[i] < pivot:
            i += 1
        while i <= j and arr[j] > pivot:
            j -= 1
        if i <= j:
            arr[i], arr[j] = arr[j], arr[i]
        else:
            break

    arr[low], arr[j] = arr[j], arr[low]
    return j

# 示例用法
arr = [5, 2, 8, 9, 1, 3]
quick_sort(arr, 0, len(arr) - 1)
print(arr)  # 输出：[1, 2, 3, 5, 8, 9]