数据结构快速排序实现
时间: 2023-11-29 14:45:55 浏览: 38
以下是C语言实现快速排序的代码和步骤:
```c
#include <stdio.h>
void quick_sort(int arr[], int low, int high) {
if (low < high) {
int i = low, j = high, pivot = arr[low];
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, low, i - 1);
quick_sort(arr, i + 1, high);
}
}
int main() {
int arr[] = {5, 3, 8, 4, 2, 7, 1, 10};
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;
}
```
步骤:
1. 选取一个基准元素pivot,一般选择第一个元素。
2. 从数组的两端开始向中间扫描,设两个指针i和j,i从左边开始扫描,j从右边开始扫描。
3. 如果i所指向的元素大于等于pivot,就一直向右移动i,直到找到一个小于pivot的元素为止。
4. 如果j所指向的元素小于pivot,就一直向左移动j,直到找到一个大于等于pivot的元素为止。
5. 交换i和j所指向的元素。
6. 重复3、4、5步,直到i和j相遇。
7. 将基准元素与i所指向的元素交换。
8. 对基准元素左边的子数组进行快速排序。
9. 对基准元素右边的子数组进行快速排序。
相关推荐
![](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)
![](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)