快速排序原理和步骤
快速排序是一种高效的排序算法,基于分治法(Divide and Conquer)来实现。其基本思想是通过一次排序将数组分成两部分,其中一部分的所有元素都小于另一部分,然后递归地对这两部分进行排序。以下是快速排序的详细步骤:
1. 选择基准元素
首先,从数组中选择一个基准元素(pivot)。基准元素的选择方法有多种,例如选择第一个元素、最后一个元素、中间元素或随机选择一个元素。基准元素用于将数组分成两部分。
2. 分区
通过遍历数组,将所有小于基准元素的元素放到基准元素的左边,所有大于基准元素的元素放到基准元素的右边。这个过程称为分区(partitioning)。分区后,基准元素的位置是其在最终排序数组中的正确位置。
3. 递归排序
对基准元素左边的子数组和右边的子数组分别递归地应用快速排序。这个过程将不断分割和排序子数组,直到所有子数组的长度为1,表示数组已经有序。
4. 合并
由于快速排序是原地排序(in-place sorting),不需要额外的合并步骤。递归过程结束后,整个数组已经有序。
快速排序的完整步骤
- 选择基准: 选择一个基准元素。
- 分区: 将数组分成两部分,一部分小于基准元素,另一部分大于基准元素。
- 递归排序: 递归地对基准元素左边和右边的子数组进行排序。
- 完成: 递归结束后,数组有序。
快速排序的伪代码
void quickSort(vector<int>& arr, int low, int high) {
if (low < high) {
// 获取分区点
int pi = partition(arr, low, high);
// 对分区点左边的子数组进行递归排序
quickSort(arr, low, pi - 1);
// 对分区点右边的子数组进行递归排序
quickSort(arr, pi + 1, high);
}
}
int partition(vector<int>& arr, int low, int high) {
// 选择最后一个元素作为基准
int pivot = arr[high];
int i = (low - 1);
for (int j = low; j <= high - 1; j++) {
// 如果当前元素小于或等于基准
if (arr[j] <= pivot) {
i++;
// 交换 arr[i] 和 arr[j]
swap(arr[i], arr[j]);
}
}
// 交换 arr[i + 1] 和 arr[high] (或基准)
swap(arr[i + 1], arr[high]);
return (i + 1);
}
Python实现:
def quick_sort(arr):
"""
对数组进行快速排序
:param arr: 待排序的数组
:return: 已排序的数组
"""
# 如果数组的长度为0或1,直接返回数组
if len(arr) <= 1:
return arr
# 选择数组的最后一个元素作为基准
pivot = arr[-1]
# 定义两个空列表,分别存放小于和大于基准的元素
left = []
right = []
# 遍历数组(不包括最后一个元素,即基准)
for element in arr[:-1]:
if element < pivot:
left.append(element)
else:
right.append(element)
# 递归地对左右两个子数组进行快速排序,并合并
return quick_sort(left) + [pivot] + quick_sort(right)