快速排序思想和基础代码
时间: 2023-07-07 12:46:15 浏览: 48
快速排序是一种常用的排序算法,基于分治的思想,其基本思路是将一个数组分成两个子数组,然后递归地对这两个子数组进行排序,最终将整个数组排序完成。具体实现时,通过选择一个基准值(pivot),将数组中小于等于基准值的元素放在左侧,大于基准值的元素放在右侧,然后对左右两个子数组递归执行这个过程。
下面是快速排序的基础代码(使用C++实现):
```cpp
void quickSort(vector<int>& nums, int left, int right) {
if (left >= right) return; // 递归边界条件
int i = left, j = right, pivot = nums[left]; // 选择第一个元素为基准值
while (i < j) {
while (i < j && nums[j] > pivot) j--; // 从右边开始找到第一个小于等于基准值的元素
if (i < j) nums[i++] = nums[j]; // 将该元素移动到左边
while (i < j && nums[i] <= pivot) i++; // 从左边开始找到第一个大于基准值的元素
if (i < j) nums[j--] = nums[i]; // 将该元素移动到右边
}
nums[i] = pivot; // 将基准值归位
quickSort(nums, left, i - 1); // 对左侧子数组递归执行快速排序
quickSort(nums, i + 1, right); // 对右侧子数组递归执行快速排序
}
```
在实际应用中,可以对快速排序进行一些优化,例如随机选择基准值、使用三数取中法选择基准值、对小数组使用插入排序等等。