快速排序算法

快速排序（Quick Sort）是一种常用的排序算法，它的基本思想是选择一个元素作为基准（通常选择数组的第一个元素），然后将数组中小于基准的元素放在基准的左边，大于基准的元素放在基准的右边，最后递归的对基准左边和右边的子数组进行排序。

具体步骤如下：

1. 选择一个基准元素（通常选择数组的第一个元素）。
2. 将数组中小于基准的元素放在基准的左边，大于基准的元素放在基准的右边。
3. 递归的对基准左边的子数组和基准右边的子数组进行排序。

代码示例（使用Python）：

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[0]
    left = [x for x in arr[1:] if x <= pivot]
    right = [x for x in arr[1:] if x > pivot]
    return quick_sort(left) + [pivot] + quick_sort(right)

# 测试
arr = [5, 3, 8, 4, 2]
sorted_arr = quick_sort(arr)
print(sorted_arr)

快速排序的时间复杂度平均为O(nlogn)，最坏情况下为O(n^2)，空间复杂度为O(logn)。它是一种原地排序算法，不需要额外的空间。快速排序是一种非稳定的排序算法，即相同元素的相对位置可能会发生变化