笔者是一名初学编程的小白,很早就了解过快速排序,但是对于原理总是“一知半解”。最近开始看《啊哈!算法》,在读完快速排序这一章节后,我觉得自己理解了原理,决定合上书本,亲自敲一遍。
不敲不知道,一敲吓一跳!我写了三四遍才能写出来书本上
我发现,其实我并没有理解什么是快速排序,因为我根本不能清晰地写出代码……
沮丧之余,我开始在想,为什么我写不出快速排序?
#include <stdio.h>
int a[101], n; // 定义全局变量,这两个变量需要在子函数中使用
void quicksort(int left, int right) {
int i, j, t, temp;
if(left > right)
return;
temp = a[left]; // temp中存的就是基准数
i = left;
j = right;
while(i != j) {
// 顺序很重要,要先从右往左找
while(a[j] >= temp && i < j)
j--;
// 再从左往右找
while(a[i] <= temp && i < j)
i++;
// 交换两个数在数组中的位置
if(i < j) { // 当哨兵i和哨兵j没有相遇时
t = a[i];
a[i] = a[j];
a[j] = t;
}
}
// 最终将基准数归位
a[left] = a[i];
a[i] = temp;
quicksort(left, i-1); // 继续处理左边的,这里是一个递归的过程
quicksort(i+1, right); // 继续处理右边的,这里是一个递归的过程
}
int main() {
int i, j, t;
// 读入数据
scanf("%d", &n);
for(i = 1; i <= n; i++)
scanf("%d", &a[i]);
quicksort(1, n); // 快速排序调用
// 输出排序后的结果
for(i = 1; i <= n; i++)
printf("%d ", a[i]);
getchar(); getchar();
return 0;
} # include <stdio.h>
void quicksort(int left; int right) {
int left, right;
left = 0;
right = n -1;
int i = left;
int j = right;
while( i!= j) {
while(arr[j] > arr[left] && j > i) j--;
while(arr[k] < arr[left] && i < j) i++;
if (arr[i] > arr[j]) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
j--;
i++;
}
}
int temp = arr[i];
arr[i] = arr[left];
arr[left] = arr[i];
}
int main () {
int n;
scanf("%d", n);
int arr[100] = {0};
for (int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
}我写的时候就感觉有点不对劲:
left和right了为什么还要i和j?temp,不然怎么交换啊?越写越不对劲,最终我放弃了,复制好以写完的部分交给Deepseek批改,结果真得是惨不忍睹!
void quicksort(int left, int right) 而不是 int left; int rightif(left >= right) return;pivot 变量存储基准值while(i < j) 而不是 while(i != j)scanf的取地址符,添加了排序后的输出暂且不追究是否“针对性”的分析了我的代码,但是,确实槽点颇多。
笔误暂且不说,我对于一些细节看的时候压根没注意到啊!带着这样的想法,我又重新开始写,你猜怎么着?我写了整整四遍
int a[101], n; // 定义全局变量,这两个变量需要在子函数中使用这就解释了为什么方法形参里面没有出现数组。
i和ja[j] >= temp:当右指针指向的元素大于或等于基准值时,继续向左移动a[i] <= temp:当左指针指向的元素小于或等于基准值时,继续向右移动i < j:确保指针不会交叉先从左向右和先从右向左的区别第二次写的时候调换了顺序,看的时候觉得啊哈注释里的“顺序很重要,要先从右往左找”很奇怪,果然,注释不是白写的!
啊哈的代码是选择最左边元素作为基准值:
错误顺序的后果:
left >= right的原因left == right:子数组只有一个元素,无需排序left > right:子数组为空,无需排序看代码发现基准值已经安全保存在临时变量中
int temp = a[left]; // 基准值已经备份a[left] 已经被保存到 temp 变量中a[left] 的位置,因为它的值已经在 temp 中while 循环会自动移动指针,直到找到需要交换的元素记得之前有看到博主说过,“敲代码的时间要比看书长”。这次是深有体会,如果不是今天自己亲自敲一遍,可能还沉浸在“我懂了”的幻想中吧。看书的时候,其实还是有很多很多细节要注意的。
所以,我敲了这篇文章来,“纪念”一下这次的教训,时刻提醒自己。
那么现在我完全理解”快速排序"了吗?显然还没有,啊哈磊老师给的代码只是最基础的版本,还有很多优化的版本,我的学习显然还没有结束,那么就留到下一次分享吧~
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。