快速排序算法 - 原理、代码示例及时间复杂度分析

快速排序（Quick Sort）是一种常用的排序算法，它的基本思想是选择一个元素作为基准（通常选择数组的第一个元素），然后将数组中小于基准的元素放在基准的左边，大于基准的元素放在基准的右边，最后递归的对基准左边和右边的子数组进行排序。\n\n具体步骤如下：\n1. 选择一个基准元素（通常选择数组的第一个元素）。\n2. 将数组中小于基准的元素放在基准的左边，大于基准的元素放在基准的右边。\n3. 递归的对基准左边的子数组和基准右边的子数组进行排序。\n\n代码示例（使用Python）：\npython\ndef quick_sort(arr):\n if len(arr) <= 1:\n return arr\n pivot = arr[0]\n left = [x for x in arr[1:] if x <= pivot]\n right = [x for x in arr[1:] if x > pivot]\n return quick_sort(left) + [pivot] + quick_sort(right)\n\n# 测试\narr = [5, 3, 8, 4, 2]\nsorted_arr = quick_sort(arr)\nprint(sorted_arr)\n\n\n快速排序的时间复杂度平均为O(nlogn)，最坏情况下为O(n^2)，空间复杂度为O(logn)。它是一种原地排序算法，不需要额外的空间。快速排序是一种非稳定的排序算法，即相同元素的相对位置可能会发生变化。