为什么算法容易忘记之快速排序

本文用来帮助大家理解记忆快速排序,方法和上篇文章一样,着重理解算法基本思想及其代码中的循环控制变量的意义。

基本思想

快速排序属于拿着元素找位置的算法。思路非常简单明了,首先给第一个元素找到它正确的位置并把它放置其中,此时该元素将原数组分为两半,左半边的元素都小于或等于它,右半边的元素都大于它,对这两个子数组重复刚才的操作,直到子数组中只有一个元素,此时排序完成。

由思想到代码

首先,我们用一个forInsert变量存储数组第一个位置上的元素的值。可以通俗理解为我们将第一个位置上的元素“挖”了出来,以便为它找到合适的位置,第一个位置此时已经是“空”的,位置是空的这一概念很关键,后面会用到。

如何为该元素找到合适的位置呢?答案是先确定该元素所在位置的范围,不断缩小该范围,直到该范围是一个确定的位置,查找结束,把forInsert的值放到该位置上,再对该位置左右两个子数组进行迭代,直到子数组大小为1时结束,排序完成。为表示该元素所在位置的范围,我们需要定义两个变量left,right,代表元素所在位置的范围的左端和右端,显然left的初始值应为0,right的初始值应为N-1。

下面开始缩小这一范围,将right位置上的元素与forInsert进行比较,如果大于forInsert,那么可以断定right这个位置肯定不是forInsert应当在的位置,因为如果将forInsert放置在right位置上,该位置上原来的元素将无处安放。所以我们可以将right减1(right--),这就缩小了位置的范围,然后我们继续将新的right位置上的元素与forInsert比较,如果还是大于forInsert,则可以继续将right减1后继续比较,直到right位置上的值小于forInsert的值时,就是magic发生的地方。

由于right位置上的元素比forInsert小,我们无法判断该位置是否是forInsert应当在的位置,BTW,我们可以判定left这个位置肯定不是forInsert应当在的位置,为什么?请参照上文叙述自行理解。

然后呢?我们可以将right位置上的值放置到left位置上,让left加1(left++),这进一步缩小了位置的范围。

此时right位置我们认为是“空的”了,看到没,刚才left是空的,现在right是空的了。

下步的思路肯定还是想办法继续缩小位置的范围。我们可以将left位置上的元素与forInsert比较,如果小于forInsert的值,我们可以断定,left这个位置肯定不是forInsert应当在的位置,为啥?因为将forInsert放置到该位置上,该位置上的元素只能往左边挪,而左边每个位置上都是比forInsert小的元素导致“无处可挪”,矛盾出现,反证结束。然后我们又可以放心地将left加1了,位置范围又缩小了,哦耶!

我们继续将left位置上的元素与forInsert比较,直到发现left位置上的元素大于forInsert时,又要有magic发生了,我们将left位置上的元素放置到right位置上(还记得right位置此时是空的吗?),现在,left位置变成空的了,由于此时right位置上的元素是大于forInsert的,right位置肯定不是forInsert应当在的位置,所以我们要将right减1,进一步缩小待确定位置的范围。

好了,让我们停一停,看看现在是什么状况,显然left增加了一些值,并且left位置此时是空的,right减少了一些值,整体上[left , right]包含的范围比初始时小了好多。如果left=right,我们知道,要找的位置就是现在left所指示的空位置,直接将forInsert放置到left位置上即可。然后开始左右两个子数组的迭代,如果left还是小于right,那我们只能继续进行缩小位置范围的工作,直到确定位置为止。

这是代码

void quick_sort(int s[], int l, int r)
{
if (l < r)
{
int i = l, j = r, x = s[l];
while (i < j)
{
while(i < j && s[j] >= x)
j--;
if(i < j)      s[i++] = s[j];
while(i < j && s[i] < x)
i++;
if(i < j)    s[j--] = s[i];
}
s[i] = x;
quick_sort(s, l, i - 1); // 递归调用
quick_sort(s, i + 1, r);
}

原文发布于微信公众号 - 人工智能LeadAI(atleadai)

原文发表时间:2018-02-20

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Python小屋

Python扩展库numpy中的布尔运算

首先解答上一篇文章Win10系统配置Python3.6+OpenGL环境详细步骤中的问题。该问题的答案为[2, 2],要点在于列表对象的方法index()默认是...

3069
来自专栏PHP实战技术

这10个问题你一定要会!你肯定忽略了!

1、问题一关于弱类型 $str1 = 'yabadabadoo'; $str2 = 'yaba'; if (strpos($str1,$str2)) { ec...

3106
来自专栏CRPER折腾记

JS数组去重!!!一篇不怎么靠谱的"深度"水文

数组去重,这是一个老梗了...今天我又拿出来说了... 我们在考虑全面一点的情况下,数组去重的实现,比如针对NaN,undefined,{}; 这其中涉及的知识...

854
来自专栏和蔼的张星的图像处理专栏

41. 最大子数组

给定一个整数数组,找到一个具有最大和的子数组,返回其最大和。 样例: 给出数组[−2,2,−3,4,−1,2,1,−5,3],符合要求的子数组为[4,−1,...

421
来自专栏Python爬虫与数据挖掘

浅谈Python内置对象类型——数字篇(附py2和py3的区别之一)

Python是一门面向对象的编程设计语言,程序中每一样东西都可以视为一个对象。Python内置对象可以分为简单类型和容器类型,简单类型主要是数值...

822
来自专栏阮一峰的网络日志

尾调用优化

尾调用(Tail Call)是函数式编程的一个重要概念,本文介绍它的含义和用法。 ? 一、什么是尾调用? 尾调用的概念非常简单,一句话就能说清楚,就是指某个函数...

3055
来自专栏磐创AI技术团队的专栏

2018 年最常见的 Python 面试题 & 答案

https://data-flair.training/blogs/python-tutorial/

431
来自专栏Celebi的专栏

C/C++ 学习笔记五(结构体、字符与字符串)

工作中经常使用到C/C++,为对C有个比较深刻的了解,重新拾起学习C的任务。在看书的同时,记录下思考的过程,也记录下重要的知识点。

2960
来自专栏程序猿DD

第五章 正则表达式的拆分

第五章 正则表达式的拆分 对于一门语言的掌握程度怎么样,可以有两个角度来衡量:读和写。 不仅要求自己能解决问题,还要看懂别人的解决方案。代码是这样,正则表达式也...

1957
来自专栏恰同学骚年

你必须知道的指针基础-2.指针的声明和使用及数组和指针的关系

  At first,计算机中绝大部分数据都放到内存中的,不同的数据放到不同的内存区域中。But,内存角度没有数据类型,只有二进制;数据以字节(8位二进制)为单...

281

扫描关注云+社区