c语言要求对一个长度为n的数组进行从小到大排序,并提供一个算法实现快速排序的方法。
时间: 2024-09-19 09:12:43 浏览: 61
在C语言中,快速排序是一种常用的、高效的排序算法,其基本思想是通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,然后分别对这两部分继续进行排序,直到整个序列有序。
以下是快速排序的基本步骤和一个简单的递归实现:
1. **选择基准元素**:通常选择第一个元素作为基准值(pivot)。
2. **分区操作**:将数组划分为两个区域,所有小于基准的元素放在左边,大于等于基准的元素放在右边。这一步通常通过一趟从左到右的扫描完成。
3. **递归排序**:对左右两个子数组递归地应用快速排序,直到子数组只剩下一个元素或为空。
**快速排序函数实现(递归版)**:
```c
#include <stdio.h>
void swap(int* a, int* b) {
int t = *a;
*a = *b;
*b = t;
}
int partition (int arr[], int low, int high) {
int pivot = arr[high]; // 选择最后一个元素作为基准
int i = (low - 1); // Index of smaller element
for (int j = low; j <= high - 1; j++) {
if (arr[j] < pivot) {
i++; // Increment index of smaller element
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]); // Swap pivot with the correct position
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); // Sort elements before pivot
quickSort(arr, pi + 1, high); // Sort elements after pivot
}
}
// 测试函数
void printArray(int arr[], int size) {
int i;
for (i = 0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}
int main() {
int data[] = {9, 7, 5, 11, 12, 2, 14, 3};
int n = sizeof(data) / sizeof(data[0]);
quickSort(data, 0, n - 1);
printf("Sorted array: \n");
printArray(data, n);
return 0;
}
```
当你运行这个程序,它会对给定的整数数组进行快速排序并打印出结果。
阅读全文