专栏首页用户7614879的专栏Java 快速排序 关于起始方向的选择问题 为什么一定要从右边开始

Java 快速排序 关于起始方向的选择问题 为什么一定要从右边开始

这是因为快速排序从右边开始的原因是因为选择的基准值key一般都是最左边的元素。

假设左哨兵为i 右哨兵为j 选择的key为最左边的元素

也就是说

当首先从右边开始先执行时,循环的条件是:

while (i < j && array[j] >= key) j--;

最后i、j 停留的位置的值肯定是要 小于 key 的 此时交换索引 j 和最左边元素key 符合将小于key的值放到key左边这一条件

当首先从左边开始执行时

while (i < j && array[i] <= key) i++;

循环结束后的 i j 碰面的时的值肯定是要 大于 key的 此时再交换key与索引位置 相当于把比key大的值放到了key左边 也就违背了快排的条件

所以如果想先从左往右查找,只需把key设置在右侧即可。


同理 假如想排降序的也要从相反方向开始, 改变这两个循环条件的>= <= 为相反的即可

while (i < j && array[j] <= key) j--;
while (i < j && array[i] >= key) i++;

假如key在左,先从右边开始 最后停留的值肯定是大于key的值 也就是交换后大于key的放在key左边 小于key的放在key右边。

先从左边开始的话 也就是先从 i 的 while 循环开始 停留的值肯定是 小于key 的 交换后小于key的被放在了key左边 不符合降序

没想到一个小小的语句顺序,是被我忽略了许久的一个重点 下面是转载的一个例子


一个数组为:6 1 2 7 9 3 4 5 10 8

图片摘至啊哈算法:

先从右往左:

前面几轮查找不贴了,到i==j时与基准数进行交换,交换之后保证左边的数都小于基准值右边的数都大于基准值

从左往右:

从有问题开始:i继续前行当i==j时此时值为9,但是条件限制j不能继续前行找到比基准值小的,只能被迫停下

此时进行交换:

交换完成并不能保证所有左边的值都小于基准数,因此当key设置在左侧时应当从右开始向左查找

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 使用puppeteer 进行批量网页截图

    配置里的'--proxy-server=socks5://127.0.0.1:1080' 是用来走本地小飞机代理的

    heasy3
  • 深入分析Volatile的实现原理

    在多线程并发编程中synchronized和Volatile都扮演着重要的角色,Volatile是轻量级的synchronized,它在多处理器开发中保证了共享...

    heasy3
  • Java selenuim用执行js模拟鼠标滚动的方式

    我使用的方法是利用如下js代码来完成页面的滚动,每次滚动多少可以根据不同情况自行调整。

    heasy3
  • redis

    1)Redis:REmote DIctionary Server(远程字典服务器)

    用户2337871
  • Redis-Nosql数据库入门

    简介 Redis是Nosql数据库的一种,可基于内存亦可持久化的日志型、是一个Key-Value数据库,多用在缓存方面 安装 Windows 下载地址, 最...

    李家酒馆酒保
  • Redis快速入门

    Redis是一个开源(BSD许可)的,内存中的数据结构存储系统,它可以用作数据库、缓存和消息中间件。

    刘文正
  • 如何处理redis集群的hot key和big key

    redis 集群部署方式大部分采用类 Twemproxy 的方式进行部署。即通过 Twemproxy 对 redis key 进行分片计算,将 redis ke...

    akayzhang
  • Redis的各种数据类型到底能玩出什么花儿?

    Redis作为一款NoSQL内存数据库,其丰富的数据类型、简单易用的命令、单机可达10万的高并发(官方数据),从面世以来就深受广大用户的喜爱。Redis的五种数...

    编程大道
  • Redis学习一(基础入门).

    一、前言     Redis是一个开源的使用ANSI C语言编写、遵守BSD协议、支持网络、可基于内存亦可持久化的日志型、key-Value 的数据库、并提供多...

    JMCui
  • 认识redis数据类型

    Redis hash 是一个string类型的field和value的映射表,hash特别适合用于存储对象。

    老雷PHP全栈开发

扫码关注云+社区

领取腾讯云代金券