C语言实现快速排序算法
时间: 2023-08-31 15:18:55 浏览: 172
### 回答1:
以下是使用 C 语言实现快速排序算法的示例代码:
```c
#include <stdio.h>
void quick_sort(int arr[], int left, int right) {
if (left >= right) {
return;
}
int pivot = arr[left]; // 选取第一个元素作为基准值
int i = left, j = right;
while (i < j) {
while (i < j && arr[j] >= pivot) { // 从右往左查找第一个小于基准值的元素
j--;
}
arr[i] = arr[j];
while (i < j && arr[i] <= pivot) { // 从左往右查找第一个大于基准值的元素
i++;
}
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, 9, 1, 7, 4, 6, 2, 8};
int n = sizeof(arr) / sizeof(arr[0]);
quick_sort(arr, 0, n - 1);
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
```
在这个示例代码中,我们选取第一个元素作为基准值,使用双指针法进行交换。在每次交换过程中,我们需要从左往右查找第一个大于基准值的元素,从右往左查找第一个小于基准值的元素,然后交换这两个元素的位置。最终,我们将基准值放到正确的位置上,然后递归处理基准值左侧和右侧的子序列。
### 回答2:
快速排序是一种常用的排序算法,它通过将数组划分为较小和较大两个部分,然后分别对这两个部分进行排序,在每次划分过程中,选择一个元素作为基准,将比基准小的元素放在基准的左边,比基准大的元素放在基准的右边。
下面是用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); // i为小于基准元素的最右边索引
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); // 对右侧子数组进行排序
}
}
int main() {
int arr[] = {10, 7, 8, 9, 1, 5};
int n = sizeof(arr) / sizeof(arr[0]);
quickSort(arr, 0, n - 1);
printf("排序后的数组:\n");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
```
以上代码首先定义了一个swap函数,用于交换两个元素的值。然后定义了partition函数,将数组划分为两部分,并返回基准元素的索引。最后定义了quickSort函数,通过递归调用自身对子数组进行排序。
在main函数中,通过对一个数组进行快速排序,并输出排序后的结果。
以上是用C语言实现快速排序算法的代码,运行后会输出排序后的数组。
### 回答3:
快速排序是一种常用的排序算法。它通过分治的思想将一个大问题分解为多个小问题,并通过递归的方式解决这些小问题。具体实现快速排序的C语言代码如下:
```C
#include <stdio.h>
// 函数原型声明
void quickSort(int arr[], int low, int high);
int partition(int arr[], int low, int high);
// 快速排序函数
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 partition(int arr[], int low, int high)
{
// 将第一个元素作为枢轴
int pivot = arr[low];
while (low < high)
{
// 从右向左找到比枢轴小的元素
while (low < high && arr[high] >= pivot)
high--;
arr[low] = arr[high];
// 从左向右找到比枢轴大的元素
while (low < high && arr[low] <= pivot)
low++;
arr[high] = arr[low];
}
// 将枢轴放到最终位置
arr[low] = pivot;
// 返回枢轴位置
return low;
}
int main()
{
int arr[] = {5, 3, 8, 4, 2, 7, 1, 6};
int n = sizeof(arr) / sizeof(arr[0]);
quickSort(arr, 0, n - 1);
printf("快速排序结果:");
for (int i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}
return 0;
}
```
以上演示了如何使用C语言实现快速排序算法。快速排序的核心思想是分治,通过选择一个枢轴,将数组划分为两部分,一部分小于枢轴,一部分大于等于枢轴。然后对划分后的两部分分别进行递归排序,以此达到整个数组有序的目的。最后,通过遍历输出排序后的数组,验证排序的结果。