※ 引述《oin1104 (是oin的说)》之铭言：
: 我要吐了
: 明明我写的丢去执行都没问题
: 可是就是时间太久 不接受
: qsort怎么用阿
: 机掰 我吐了
请用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);
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);
for(int i=0; i < n; i++)
printf("%d ", arr[i]);
return 0;
}
这里主要逻辑是:
选择一个基准值pivot,通常选择数组的最后一个元素
定义两个指标i和j,i初始化为low-1,j初始化为low。
j从low到high-1遍历数组,如果arr[j]小于等于pivot,交换arr[++i]和arr[j]的位置,这样
可以保证左边的值都小于pivot。
最后交换pivot和arr[i+1]的位置,这样可以保证pivot的左边值都小于pivot,右边值都大
于pivot。
递归对pivot左边和右边的子数组进行快速排序。
这样就可以实现快速排序了。