快速排序 c语言实现王道考研
时间: 2023-08-06 14:01:01 浏览: 90
快速排序是一种高效的排序算法,它采用分治的思想,通过将数组分为较小和较大的两部分,递归地对这两部分进行排序,最终使整个数组有序。下面是用 C 语言实现快速排序的一种算法。
快速排序的基本思路是选择一个基准元素,将数组划分为左右两个部分,左部分比基准元素小,右部分比基准元素大,然后对左右两个部分分别进行递归排序。
具体实现如下:
1. 定义一个函数 `quick_sort`,用于排序整个数组;
2. 在函数内部定义三个变量:`left`、`right`、`pivot`;
3. `left` 表示数组的左边界,`right` 表示数组的右边界;
4. `pivot` 用于存储基准元素;
5. 如果 `left` 大于等于 `right`,则返回;
6. 将 `pivot` 设置为数组的第一个元素;
7. 记录下 `pivot` 的位置 `index`;
8. 从 `left+1` 开始遍历数组,如果找到比 `pivot` 大的元素,则将其与 `pivot` 交换,并停止遍历;
9. 从 `right` 开始遍历数组,如果找到比 `pivot` 小的元素,则将其与 `pivot` 交换,并停止遍历;
10. 继续上述步骤,直到 `left` 和 `right` 相交;
11. 将 `pivot` 与 `index` 所在位置的元素交换;
12. 分别对左右两个部分递归调用 `quick_sort` 函数。
这样,通过不断地划分和排序,最终可以使整个数组有序。
以上就是用 C 语言实现快速排序的基本思路和步骤,希望对您理解快速排序算法有所帮助。
相关问题
快速排序 c语言实现及注释
快速排序是一种常用的排序算法,其时间复杂度为O(nlogn)。其基本思想是通过一趟排序将待排序列分成两部分,其中一部分的所有元素均比另一部分的所有元素小,然后再按此方法对这两部分分别进行快速排序,以达到整个序列有序的目的。
以下是C语言实现及注释:
```c
#include <stdio.h>
// 快速排序函数
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); // 递归排序右半部分
}
int main() {
int arr[] = {5, 3, 8, 4, 2, 7, 1, 6};
int len = sizeof(arr) / sizeof(arr[0]);
quick_sort(arr, 0, len - 1);
for (int i = 0; i < len; i++) {
printf("%d ", arr[i]);
}
return 0;
}
```
注释中已经解释了代码的实现过程,简单来说,就是通过左右指针和基准值将待排序列分成两部分,然后递归对这两部分进行排序,最终得到有序序列。
快速排序c语言递归实现
快速排序是一种常用的排序算法,它通过递归地将数组分成较小和较大的两个子数组来实现排序。下面是快速排序的C语言递归实现:
```c
#include <stdio.h>
// 交换两个元素的值
void swap(int* a, int* b) {
int temp = *a;
*a = *b;
*b = temp;
}
// 将数组分成两部分,并返回分割点的索引
int partition(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++;
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]); // 将基准值放到正确的位置上
return (i + 1); // 返回分割点的索引
}
// 快速排序递归函数
void quickSort(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);
}
}
// 打印数组
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
int main() {
int arr[] = {64, 25, 12, 22, 11};
int n = sizeof(arr) / sizeof(arr);
printf("原始数组:\n");
printArray(arr, n);
quickSort(arr, 0, n - 1);
printf("排序后的数组:\n");
printArray(arr, n);
return 0;
}
```
这段代码实现了快速排序算法的递归版本。首先定义了一个`swap`函数用于交换两个元素的值。然后定义了`partition`函数,它选择最后一个元素作为基准值,将数组分成两部分,并返回分割点的索引。接下来是`quickSort`函数,它通过递归调用自身来对分割点左右两个子数组进行排序。最后,在`main`函数中测试了快速排序算法。