怎么实现对一个数组的快速排序

快速排序是一种高效的排序算法，其基本思想是通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，然后分别对这两部分记录继续进行排序，以达到整个序列有序的目的。以下是快速排序的基本步骤：

1. **选择基准**：通常选择数组的第一个元素作为基准值（pivot）。

2. **划分**：遍历数组，将所有小于基准的元素放在基准左边，大于基准的元素放在右边。这一步骤通常使用两个指针（一个从左向右扫描，一个小于基准值的右边移动）完成。

3. **递归**：对基准两侧的子数组分别进行同样的快速排序操作。如果子数组只剩下一个元素或者为空，则排序结束。

4. **合并**：递归完成后，原数组就被分割成了几个已排序的小片段。

下面是一个简单的Python实现：

def quicksort(arr):
    if len(arr) <= 1:
        return arr   # 基线条件：长度为1或0的数组已经是“有序”的

    pivot = arr[0]   # 选取第一个元素作为基准
    left = []   # 存放小于基准的元素
    right = []  # 存放大于等于基准的元素

    for num in arr[1:]:
        if num < pivot:
            left.append(num)
        else:
            right.append(num)

    return quicksort(left) + [pivot] + quicksort(right)

# 示例
arr = [3,6,8,10,1,2,1]
sorted_arr = quicksort(arr)
print("Sorted array:", sorted_arr)