C语言快速排序交换法
时间: 2023-10-29 13:54:32 浏览: 49
快速排序是一种常用的排序算法,它的基本思想是通过一趟排序将待排序的数据分割成独立的两部分,其中一部分的所有数据都比另一部分的所有数据小。然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
在使用交换法实现快速排序时,我们需要选择一个基准元素(通常是待排序序列的第一个元素),然后将比基准元素小的元素放在它的左边,比基准元素大的元素放在它的右边。这个过程称为一趟快速排序。之后,对基准元素左右两个子序列分别进行快速排序,直到整个序列有序。
下面是使用交换法实现快速排序的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[low]; // 选择第一个元素作为基准元素
int i = low, j = high;
while (i < j) {
// 从右往左找到比基准元素小的元素
while (i < j && arr[j] >= pivot)
j--;
if (i < j)
swap(&arr[i], &arr[j]);
// 从左往右找到比基准元素大的元素
while (i < j && arr[i] <= pivot)
i++;
if (i < j)
swap(&arr[i], &arr[j]);
}
return i; // 返回基准元素的位置
}
// 快速排序递归函数
void quickSort(int arr[], int low, int high) {
if (low < high) {
int pivotPos = partition(arr, low, high); // 一趟快速排序,获取基准元素位置
quickSort(arr, low, pivotPos - 1); // 对左子序列进行快速排序
quickSort(arr, pivotPos + 1, high); // 对右子序列进行快速排序
}
}
// 测试
int main() {
int arr[] = {9, 5, 2, 7, 1, 8, 6};
int n = sizeof(arr) / sizeof(arr[0]);
printf("原数组:");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
quickSort(arr, 0, n - 1);
printf("排序后:");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
```
这段代码中使用了交换法来实现快速排序,其中`swap`函数用于交换两个元素的值,`partition`函数用于一趟快速排序,`quickSort`函数是递归调用的快速排序函数。通过运行测试代码,你可以看到原始数组经过快速排序后变成有序的数组。