hoare版本
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>// 交换函数
void Swap(int* p1, int* p2) {int tmp = *p1;*p1 = *p2;*p2 = tmp;
}// 打印数组
void _printf(int* a, int n) {for (int i = 0; i < n; i++) {printf("%d ", a[i]);}printf("\n"); // 添加换行，方便查看结果
}// 快速排序
void QuickSort(int* a, int left, int right) {if (left >= right) { // 递归边界条件：区间只有一个元素或无元素return;}int begin = left, end = right; // 记录当前区间int keyi = left; // 基准值初始为第一个元素的下标while (left < right) {// 从右向左寻找比基准值小的元素while (a[right] >= a[keyi] && left < right) {right--;}// 从左向右寻找比基准值大的元素while (a[left] <= a[keyi] && left < right) {left++;}// 交换左右指针指向的值Swap(&a[left], &a[right]);}// 基准值归位Swap(&a[left], &a[keyi]);keyi = left; // 更新基准值位置// 对左右两部分递归排序QuickSort(a, begin, keyi - 1); // 左部分QuickSort(a, keyi + 1, end); // 右部分
}int main() {int a[] = { 1, 2, 3, 7, 8, 9, 4, 5, 6 }; // 测试数组int n = sizeof(a) / sizeof(a[0]); // 数组元素个数printf("Before sorting:\n");_printf(a, n); // 输出排序前的数组QuickSort(a, 0, n - 1); // 快速排序printf("After sorting:\n");_printf(a, n); // 输出排序后的数组return 0;
}
测试结果
挖坑法
#include <stdio.h>// 交换函数
void Swap(int* p1, int* p2) {int tmp = *p1;*p1 = *p2;*p2 = tmp;
}// 打印数组
void _printf(int* a, int n) {for (int i = 0; i < n; i++) {printf("%d ", a[i]);}
}// 快速排序（挖坑法）
void QuickSort(int* a, int left, int right) {if (left >= right) {return; // 当区间为空或只有一个元素时，递归结束}int begin = left;int end = right;int keyi = a[left]; // 基准值while (left < right) {// 从右向左寻找比基准值小的数while (a[right] >= keyi && left < right) {right--;}if (left < right) {a[left] = a[right]; // 填坑}// 从左向右寻找比基准值大的数while (a[left] <= keyi && left < right) {left++;}if (left < right) {a[right] = a[left]; // 填坑}}// 最后将基准值填入当前坑位a[left] = keyi;// 对左右区间递归排序QuickSort(a, begin, left - 1); // 左区间QuickSort(a, left + 1, end); // 右区间
}int main() {int a[] = {7, 5, 6, 4, 8, 9, 2, 1, 3, 0};int n = sizeof(a) / sizeof(a[0]);printf("Before sorting:\n");_printf(a, n);printf("\n");QuickSort(a, 0, n - 1);printf("After sorting:\n");_printf(a, n);printf("\n");return 0;
}
测试结果
