首页
学习
活动
专区
圈层
工具
发布
社区首页 >专栏 >为什么我写不出“快速排序”

为什么我写不出“快速排序”

原创
作者头像
GreyFox
发布2025-10-25 00:43:41
发布2025-10-25 00:43:41
1070
举报
文章被收录于专栏:代码人生代码人生

为什么我写不出“快速排序”

前言

笔者是一名初学编程的小白,很早就了解过快速排序,但是对于原理总是“一知半解”。最近开始看《啊哈!算法》,在读完快速排序这一章节后,我觉得自己理解了原理,决定合上书本,亲自敲一遍。

不敲不知道,一敲吓一跳!我写了三四遍才能写出来书本上

我发现,其实我并没有理解什么是快速排序,因为我根本不能清晰地写出代码……

沮丧之余,我开始在想,为什么我写不出快速排序?

没有对比就没有伤害

啊哈磊老师的代码

代码语言:javascript
复制
  #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;
}

我写的第一版代码

代码语言:javascript
复制
  # 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]);
    }    
}

我的困惑

我写的时候就感觉有点不对劲:

  1. 1. 我记得啊哈累老师的代码里形参没有数组啊,那怎么在方法体里出现数组的?
  2. 2. 有leftright了为什么还要ij
  3. 3. 最后的基准值交换要不要再来一个temp,不然怎么交换啊?
  4. 4. ……

越写越不对劲,最终我放弃了,复制好以写完的部分交给Deepseek批改,结果真得是惨不忍睹!

Deepseek的分析

主要修正内容
  1. 1. 函数声明void quicksort(int left, int right) 而不是 int left; int right
  2. 2. 递归终止条件:添加了 if(left >= right) return;
  3. 3. 变量声明:移除重复的变量声明
  4. 4. 基准值:明确使用 pivot 变量存储基准值
  5. 5. 循环条件:修正为 while(i < j) 而不是 while(i != j)
  6. 6. 交换逻辑:修正了交换条件
  7. 7. 基准归位:修正了基准值归位的逻辑
  8. 8. 递归调用:添加了对左右子数组的递归调用
  9. 9. main函数:修正了scanf的取地址符,添加了排序后的输出

暂且不追究是否“针对性”的分析了我的代码,但是,确实槽点颇多。

我的反思

笔误暂且不说,我对于一些细节看的时候压根没注意到啊!带着这样的想法,我又重新开始写,你猜怎么着?我写了整整四遍

啊哈代码中快速排序的“细节”

全局变量
代码语言:javascript
复制
  int a[101], n; // 定义全局变量,这两个变量需要在子函数中使用

这就解释了为什么方法形参里面没有出现数组。

ij
  • a[j] >= temp:当右指针指向的元素大于或等于基准值时,继续向左移动
  • a[i] <= temp:当左指针指向的元素小于或等于基准值时,继续向右移动
  • i < j:确保指针不会交叉
先从左向右先从右向左的区别

第二次写的时候调换了顺序,看的时候觉得啊哈注释里的“顺序很重要,要先从右往左找”很奇怪,果然,注释不是白写的!

啊哈的代码是选择最左边元素作为基准值

错误顺序的后果

  • • 如果先移动左指针,可能导致相遇点的元素大于基准值
  • • 将基准值与大于它的元素交换,会破坏分区性质
判断left >= right的原因
  1. 1. 递归终止条件
    • • 当 left == right:子数组只有一个元素,无需排序
    • • 当 left > right:子数组为空,无需排序
  2. 2. 防止无限递归
    • • 如果没有这个条件,递归会无限进行下去
    • • 当子数组大小为0或1时,递归应该终止
  3. 3. 提高效率
    • • 避免对已经有序的小数组进行不必要的递归调用
最后的基准值“交换”不用新建中间量的原因

看代码发现基准值已经安全保存在临时变量中

代码语言:javascript
复制
  int temp = a[left];  // 基准值已经备份
  • • 在分区过程开始时,基准值 a[left] 已经被保存到 temp 变量中
  • • 因此我们可以安全地覆盖 a[left] 的位置,因为它的值已经在 temp
快速排序中交换后是不需要移动指针的原因
  • 循环自动控制:内层的 while 循环会自动移动指针,直到找到需要交换的元素
  • 交换后的位置已经检查过:交换后,当前位置的元素已经符合条件,不需要再次检查
  • 自然进入下一轮循环:交换完成后,程序会自动进入下一轮外层循环,继续移动指针

一点小小的启示

记得之前有看到博主说过,“敲代码的时间要比看书长”。这次是深有体会,如果不是今天自己亲自敲一遍,可能还沉浸在“我懂了”的幻想中吧。看书的时候,其实还是有很多很多细节要注意的。

所以,我敲了这篇文章来,“纪念”一下这次的教训,时刻提醒自己。

尾声

那么现在我完全理解”快速排序"了吗?显然还没有,啊哈磊老师给的代码只是最基础的版本,还有很多优化的版本,我的学习显然还没有结束,那么就留到下一次分享吧~

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 为什么我写不出“快速排序”
    • 前言
    • 没有对比就没有伤害
      • 啊哈磊老师的代码
      • 我写的第一版代码
      • 我的困惑
      • Deepseek的分析
      • 啊哈代码中快速排序的“细节”
    • 一点小小的启示
    • 尾声
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档