C++中快速排序算法的实现基本思想
时间: 2024-05-13 08:17:40 浏览: 10
快速排序是一种常用的排序算法,其基本思想是通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小,然后再按此方法对这两部分记录分别进行快速排序,以达到整个序列有序的目的。
具体实现步骤如下:
1. 选取一个基准元素Pivot,一般可以选择第一个或最后一个元素。
2. 将序列中所有小于Pivot的元素移到Pivot的左边,大于Pivot的元素移到Pivot的右边。
3. 分别对Pivot左边的序列和右边的序列递归地进行步骤1和步骤2,直到每个子序列只剩下一个元素为止。
C++代码实现如下:
```
void quick_sort(int arr[], int left, int right) {
if (left >= right) return; // 递归终止条件
int i = left, j = right, pivot = arr[left]; // 选取最左边的元素作为基准元素
while (i < j) {
while (i < j && arr[j] >= pivot) j--; // 从右往左找到第一个小于基准元素的元素
if (i < j) arr[i++] = arr[j]; // 将该元素移到左边
while (i < j && arr[i] < pivot) i++; // 从左往右找到第一个大于等于基准元素的元素
if (i < j) arr[j--] = arr[i]; // 将该元素移到右边
}
arr[i] = pivot; // 将基准元素放回正确的位置
quick_sort(arr, left, i - 1); // 递归地对基准元素左边的序列进行快速排序
quick_sort(arr, i + 1, right); // 递归地对基准元素右边的序列进行快速排序
}
```