写一个快排
时间: 2023-12-13 16:03:05 浏览: 39
快速排序是一种常见的排序算法。它的基本思想是:
1. 从数列中选择一个元素,作为"基准"(pivot)。
2. 把所有小于"基准"的元素放在"基准"的左边,所有大于"基准"的元素放在"基准"的右边。这个过程称为分区(partition)。
3. 对"基准"左边和右边的两个子集,不断重复第一步和第二步,直到所有子集只剩下一个元素为止。
以下是一个递归实现的例子(C++语言):
```
void quick_sort(int arr[], int left, int right) {
if (left >= right) return; // 如果数列长度为0或1,直接返回。
int pivot = arr[right]; // 选择最后一个元素作为"基准"。
int i = left;
int j = right;
while (i < j) {
// 从左向右找到第一个大于"基准"的元素。
while (i < j && arr[i] <= pivot) i++;
// 从右向左找到第一个小于"基准"的元素。
while (i < j && arr[j] >= pivot) j--;
// 交换两个元素。
if (i < j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// 最后将"基准"放到合适的位置。
arr[right] = arr[i];
arr[i] = pivot;
// 对"基准"左边和右边的两个子集,不断重复第一步和第二步,直到