快速排序c语言代码以及解释
时间: 2023-09-23 14:05:07 浏览: 46
Sure, here's an example of the Quick Sort algorithm implemented in C:
```c
#include<stdio.h>
// Function to swap two elements
void swap(int* a, int* b) {
int temp = *a;
*a = *b;
*b = temp;
}
// Partition the array on the basis of pivot
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);
}
// Function to implement Quick Sort
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);
}
}
// Function to print the array
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
// Driver program to test above functions
int main() {
int arr[] = {10, 7, 8, 9, 1, 5};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Original array:\n");
printArray(arr, n);
quickSort(arr, 0, n - 1);
printf("Sorted array:\n");
printArray(arr, n);
return 0;
}
```
Explanation:
1. The `swap` function swaps the values of two elements in the array.
2. The `partition` function chooses a pivot element (in this implementation, the last element) and rearranges the array such that all elements smaller than the pivot are on its left and all elements greater than the pivot are on its right. It returns the index of the pivot element.
3. The `quickSort` function recursively calls itself to sort the subarrays before and after the partition.
4. The `printArray` function is used to print the elements of the array.
5. In the `main` function, an array is defined, its original state is printed, and then `quickSort` is called to sort the array. Finally, the sorted array is printed.
This implementation of Quick Sort has a time complexity of O(n log n) in average and best cases, and O(n^2) in the worst case.
相关推荐
![h](https://img-home.csdnimg.cn/images/20210720083646.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)