热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

排序算法之三:快速排序

 算法分析:选择一个关键值作为基准值。比基准值小的都在左边序列(一般是无序的),比基准值大的都在右边(一般是无序的)。一般选择序列的第一个元素。一次循环:从后往前比较,用

 算法分析:选择一个关键值作为基准值。比基准值小的都在左边序列(一般是无序的),比基准值大的都在右边(一般是无序的)。一般选择序列的第一个元素。

一次循环:从后往前比较,用基准值和最后一个值比较,如果比基准值小的交换位置,如果没有继续比较下一个,直到找到第一个比基准值小的值才交换。找到这个值之后,又从前往后开始比较,如果有比基准值大的,交换位置,如果没有继续比较下一个,直到找到第一个比基准值大的值才交换。直到从前往后的比较索引>从后往前比较的索引,结束第一次循环,此时,对于基准值来说,左右两边就是有序的了。接着分别比较左右两边的序列,重复上述的循环。

复杂度:理想为O(nlogn),最差为O(n^2)

public void quicksort(int[] arr,int start,int end){

        if(start>=end){

            return;

        }

        //把数组中的第0个数作为基数

        int stard=arr[start];

        int low=start;

        int high=end;

        while(low
            //右边的数比标准数大

            while(low
                high--;

                

            }

            //右边的数替换左边

            arr[low]=arr[high];

            while(low=arr[low]){

                low++;

            }

            arr[high]=arr[low];

        }

        arr[low]=stard;

        //处理所有小的数

        quicksort(arr,start,low);

        //处理所有大的数

        quicksort(arr,low+1,end);

    }


推荐阅读
  • 函子(Functor)是函数式编程中的一个重要概念,它不仅是一个特殊的容器,还提供了一种优雅的方式来处理值和函数。本文将详细介绍函子的基本概念及其在函数式编程中的应用,包括如何通过函子控制副作用、处理异常以及进行异步操作。 ... [详细]
  • H5技术实现经典游戏《贪吃蛇》
    本文将分享一个使用HTML5技术实现的经典小游戏——《贪吃蛇》。通过H5技术,我们将探讨如何构建这款游戏的两种主要玩法:积分闯关和无尽模式。 ... [详细]
  • TCP协议中的可靠传输机制分析
    本文深入探讨了TCP协议如何通过滑动窗口和超时重传来确保数据传输的可靠性,同时介绍了流量控制和拥塞控制的基本原理及其在实际网络通信中的应用。 ... [详细]
  • HBase 数据复制与灾备同步策略
    本文探讨了HBase在企业级应用中的数据复制与灾备同步解决方案,包括存量数据迁移及增量数据实时同步的方法。 ... [详细]
  • 本文探讨了程序员这一职业的本质,认为他们是专注于问题解决的专业人士。文章深入分析了他们的日常工作状态、个人品质以及面对挑战时的态度,强调了编程不仅是一项技术活动,更是个人成长和精神修炼的过程。 ... [详细]
  • 在1995年,Simon Plouffe 发现了一种特殊的求和方法来表示某些常数。两年后,Bailey 和 Borwein 在他们的论文中发表了这一发现,这种方法被命名为 Bailey-Borwein-Plouffe (BBP) 公式。该问题要求计算圆周率 π 的第 n 个十六进制数字。 ... [详细]
  • 本文详细介绍了如何在Oracle VM VirtualBox中实现主机与虚拟机之间的数据交换,包括安装Guest Additions增强功能,以及如何利用这些功能进行文件传输、屏幕调整等操作。 ... [详细]
  • CSS Border 属性:solid 边框的使用详解
    本文详细介绍了如何在CSS中使用solid边框属性,包括其基本语法、应用场景及高级技巧,适合初学者和进阶用户参考。 ... [详细]
  • 2023年,Android开发前景如何?25岁还能转行吗?
    近期,关于Android开发行业的讨论在多个平台上热度不减,许多人担忧其未来发展。本文将探讨当前Android开发市场的现状、薪资水平及职业选择建议。 ... [详细]
  • 二维码的实现与应用
    本文介绍了二维码的基本概念、分类及其优缺点,并详细描述了如何使用Java编程语言结合第三方库(如ZXing和qrcode.jar)来实现二维码的生成与解析。 ... [详细]
  • 在日常生活中,支付宝已成为不可或缺的支付工具之一。本文将详细介绍如何通过支付宝实现免费提现,帮助用户更好地管理个人财务,避免不必要的手续费支出。 ... [详细]
  • 如何在PyCharm中配置Python脚本的默认模板
    本文介绍如何在PyCharm中设置Python脚本的默认模板,以便每次创建新的.py文件时自动填充预设内容,提高开发效率。 ... [详细]
  • JUnit下的测试和suite
    nsitionalENhttp:www.w3.orgTRxhtml1DTDxhtml1-transitional.dtd ... [详细]
  • 当需要确保对象的状态在创建后不可更改时,使用记录(Record)类型是一个理想的选择。本文探讨了如何通过记录类型实现对象的不可变性,并提供了一个简单的示例来说明其用法。 ... [详细]
  • 机器学习实践:逻辑回归与过拟合控制
    本文深入探讨了逻辑回归在机器学习中的应用,并详细解释了如何通过正则化等方法来有效避免模型的过拟合问题。 ... [详细]
author-avatar
总是生活在记忆中_873
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有