文档章节

另一种快速排序

兔之
 兔之
发布于 2016/04/18 16:02
字数 217
阅读 31
收藏 1
点赞 1
评论 0

之前 http://my.oschina.net/lvyi/blog/324551 写过一种快速排序,下面是另外一种稍微不同的方法。它分别寻找比中心值 k 小和 k 大的两个元素再进行交换,逻辑更加清晰。

public class QuickSort
{
    private static void swap(int[] arr, int i, int j)
    {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    private static int partition(int[] a, int lo, int hi)
    {
        int i = lo, j = hi + 1;
        while(true)
        {
            while (a[++i] < a[lo])
                if (i == hi) break;

            while (a[lo] < a[--j])
                if (j == lo) break;

            if (i >= j) break;
            swap(a, i, j);
        }

        swap(a, lo, j);
        return j;
    }

    public static void sort(int[] a)
    {
        // StdRandom.shuffle(a);
        sort(a, 0, a.length - 1);
    }

    private static void sort(int[] a, int lo, int hi)
    {
        if (hi <= lo) return;
        int j = partition(a, lo, hi);
        sort(a, lo, j-1);
        sort(a, j+1, hi);
    }

    public static void main(String[] argv)
    {
        int[] arr = {6, 7, 9, 0, 5, 1, 8, 12};
        sort(arr, 0, 7);

        for(int i: arr)
            System.out.println(i);
    }
}

参考

https://class.coursera.org/algs4partI-010/lecture/35

© 著作权归作者所有

共有 人打赏支持
兔之
粉丝 66
博文 244
码字总数 95573
作品 7
深圳
程序员
分治思想之排序算法

分而治之是设计高效算法的一个重要思想。本文主要总结一下分治思想在排序算法中的运用。 排序在商业数据处理和现代科学计算中有着重要的地位,它能够应用于事物处理、组合优化、天体物理学、...

丶legend ⋅ 2017/10/02 ⋅ 0

被忽视的 partition 算法

如果你学习过算法,那么肯定听说过快速排序的大名,但是对于快速排序中用到的 partition 算法,你了解的够多吗?或许是快速排序太过于光芒四射,使得我们往往会忽视掉同样重要的 partition ...

selfboot ⋅ 2016/08/31 ⋅ 0

接触并理解 快速排序【基础+优化+三向切分】

要点 算法思想与实现,优化思路,性能分析,三向切分,空间,优势 前言 快速排序之所以被称作“快速”,是因为快速排序是我们接触到的最快的通用排序算法,至于原因我们会在后面予以解释。鉴...

LWADE ⋅ 2017/12/07 ⋅ 0

快速排序及其优化

算法简介 是一种分治的排序算法,特点就是快,而且效率高。 基本思路 通过一趟排序将待排元素分隔成独立的两部分,其中一部分元素的关键字均比另一部分的关键字小,然后分别对这两部分元素继...

TinyDolphin ⋅ 2017/11/15 ⋅ 0

常用的简单排序算法集合(更新中)

/** 冒泡排序 /public static void Bubble_Sort(int[] a) {for (int i = 0; i < a.length - 1; i++) {for (int j = 0; j < a.length - i - 1; j++) {if (a[j] > a[j + 1]) {a[i] = a[i] + a[......

维特的烦恼 ⋅ 2014/04/26 ⋅ 1

每天学习一点儿算法--快速排序

快速排序是一种常用的优雅的排序算法,它使用分而治之的策略。 那么分而治之(D&C)是一种怎样的策略呢? 分而治之 分而治之(D&C)的要点只有两个: 找出简单的基线问题 确定如何缩小问题的...

爱吃西瓜的番茄酱 ⋅ 01/11 ⋅ 0

快速排序详解 Java实现

一、快速排序的优缺点 对一个东西,首先要讲他的利与弊,才知道怎么使用它。快速排序适用于各种不同的输入数据且在一般应用中比其他排序都要快得多。快速排序引人注目的特点包括它是原地排序...

小车车 ⋅ 2016/09/03 ⋅ 0

快速排序算法QuickSort

1.说明 快速排序法(quicksort)是目前所公认最快的排序方法之一(视解题的对象而定),虽然快速排序法在最差状况下可以达O(n2),但是在多数的情况下,快速排序法的效率表现是相当不错的。快...

嗯哼9925 ⋅ 2017/12/14 ⋅ 0

排序——快速排序法

一、快速排序法概念 快速排序(Quick Sort)法是对冒泡排序的一种改进,其基本思想是:通过一遍排序将需要排序的数据划分成两部分,使其中一部分数据比另一部分数据小,然后再分别对这两部分...

翼动动空 ⋅ 2016/06/06 ⋅ 0

Java学习资料-Java常用算法-快速排序算法

/** * 快速排序 X为假定的中间值 从j开始向左搜索,即由右开始向左搜索j--,找到第一个小于X的值,两者交换 * 从i开始向右搜索,即由左开始向右搜索i++,找到第一个大于X的值,两者交换 * * @param...

晓阳 ⋅ 2015/01/26 ⋅ 1

没有更多内容

加载失败,请刷新页面

加载更多

下一页

Spring | IOC AOP 注解 简单使用

写在前面的话 很久没更新笔记了,有人会抱怨:小冯啊,你是不是在偷懒啊,没有学习了。老哥,真的冤枉:我觉得我自己很菜,还在努力学习呢,正在学习Vue.js做管理系统呢。即便这样,我还是不...

Wenyi_Feng ⋅ 今天 ⋅ 0

博客迁移到 https://www.jianshu.com/u/aa501451a235

博客迁移到 https://www.jianshu.com/u/aa501451a235 本博客不再更新

为为02 ⋅ 今天 ⋅ 0

win10怎么彻底关闭自动更新

win10自带的更新每天都很多,每一次下载都要占用大量网络,而且安装要等得时间也蛮久的。 工具/原料 Win10 方法/步骤 单击左下角开始菜单点击设置图标进入设置界面 在设置窗口中输入“服务”...

阿K1225 ⋅ 今天 ⋅ 0

Elasticsearch 6.3.0 SQL功能使用案例分享

The best elasticsearch highlevel java rest api-----bboss Elasticsearch 6.3.0 官方新推出的SQL检索插件非常不错,本文一个实际案例来介绍其使用方法。 1.代码中的sql检索 @Testpu...

bboss ⋅ 今天 ⋅ 0

informix数据库在linux中的安装以及用java/c/c++访问

一、安装前准备 安装JDK(略) 到IBM官网上下载informix软件:iif.12.10.FC9DE.linux-x86_64.tar放在某个大家都可以访问的目录比如:/mypkg,并解压到该目录下。 我也放到了百度云和天翼云上...

wangxuwei ⋅ 今天 ⋅ 0

PHP语言系统ZBLOG或许无法重现月光博客的闪耀历史[图]

最近在写博客,希望通过自己努力打造一个优秀的教育类主题博客,名动江湖,但是问题来了,现在写博客还有前途吗?面对强大的自媒体站点围剿,还有信心和可能型吗? 至于程序部分,我选择了P...

原创小博客 ⋅ 今天 ⋅ 0

IntelliJ IDEA 2018.1新特性

工欲善其事必先利其器,如果有一款IDE可以让你更高效地专注于开发以及源码阅读,为什么不试一试? 本文转载自:netty技术内幕 3月27日,jetbrains正式发布期待已久的IntelliJ IDEA 2018.1,再...

Romane ⋅ 今天 ⋅ 0

浅谈设计模式之工厂模式

工厂模式(Factory Pattern)是 Java 中最常用的设计模式之一。这种类型的设计模式属于创建型模式,它提供了一种创建对象的最佳方式。 在工厂模式中,我们在创建对象时不会对客户端暴露创建逻...

佛系程序猿灬 ⋅ 今天 ⋅ 0

Dockerfile基础命令总结

FROM 指定使用的基础base image FROM scratch # 制作base image ,不使用任何基础imageFROM centos # 使用base imageFROM ubuntu:14.04 尽量使用官方的base image,为了安全 LABEL 描述作...

ExtreU ⋅ 昨天 ⋅ 0

存储,对比私有云和公有云的不同

导读 说起公共存储,很难不与后网络公司时代的选择性外包联系起来,但尽管如此,它还是具备着简单和固有的可用性。公共存储的名字听起来也缺乏专有性,很像是把东西直接堆放在那里而不会得到...

问题终结者 ⋅ 昨天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部