请用C++写一个快速排序代码
时间: 2024-05-07 22:15:27 浏览: 11
以下是使用C语言实现的快速排序代码:
```
#include <stdio.h>
void quick_sort(int arr[], int left, int right) {
int i, j, pivot, temp;
if (left < right) {
pivot = left;
i = left;
j = right;
while (i < j) {
while (arr[i] <= arr[pivot] && i < right)
i++;
while (arr[j] > arr[pivot])
j--;
if (i < j) {
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
temp = arr[pivot];
arr[pivot] = arr[j];
arr[j] = temp;
quick_sort(arr, left, j - 1);
quick_sort(arr, j + 1, right);
}
}
int main() {
int arr[] = { 5, 3, 8, 4, 2 };
int n = sizeof(arr) / sizeof(arr[0]);
int i;
printf("Before sorting:\n");
for (i = 0; i < n; i++)
printf("%d ", arr[i]);
quick_sort(arr, 0, n - 1);
printf("\nAfter sorting:\n");
for (i = 0; i < n; i++)
printf("%d ", arr[i]);
return 0;
}
```
快速排序的基本思路是选择一个基准元素,将小于基准元素的放在左边,大于基准元素的放在右边,然后递归地对左右两部分进行排序。在上面的代码中,我们选择了第一个元素作为基准元素,然后使用两个指针i和j分别从左右两边扫描数组,如果i指向的元素小于等于基准元素且i小于右边界,那么就将i向右移动;如果j指向的元素大于基准元素,那么就将j向左移动;如果此时i小于j,就将i和j指向的元素交换。当i>=j时,说明扫描完成,这时将基准元素和j指向的元素交换,这样基准元素就被放在了正确的位置。接着,对左右两部分分别进行递归排序,直到所有元素都被排序完毕。