文档章节

另一种快速排序

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

之前 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

© 著作权归作者所有

共有 人打赏支持
兔之
粉丝 67
博文 247
码字总数 95896
作品 7
深圳
程序员
私信 提问
分治思想之排序算法

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

丶legend
2017/10/02
0
0
排序算法-选择,插入,希尔,归并,快排

排序 选择排序 selection 插入排序 insertion 希尔排序 shell 归并排序 快速排序 准备工作 交换方法,供后续调用: 自顶向下的归并排序 如果它能将两个子数组排序,它就能够通过归并两个子数...

rustfisher
2015/12/21
0
0
被忽视的 partition 算法

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

selfboot
2016/08/31
0
0
接触并理解 快速排序【基础+优化+三向切分】

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

LWADE
2017/12/07
0
0
快速排序及其优化

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

TinyDolphin
2017/11/15
0
0

没有更多内容

加载失败,请刷新页面

加载更多

[LintCode] Serialize and Deserialize Binary Tree(二叉树的序列化和反序列化)

描述 设计一个算法,并编写代码来序列化和反序列化二叉树。将树写入一个文件被称为“序列化”,读取文件后重建同样的二叉树被称为“反序列化”。 如何反序列化或序列化二叉树是没有限制的,你...

honeymose
今天
5
0
java框架学习日志-7(静态代理和JDK代理)

静态代理 我们平时去餐厅吃饭,不是直接告诉厨师做什么菜的,而是先告诉服务员点什么菜,然后由服务员传到给厨师,相当于服务员是厨师的代理,我们通过代理让厨师炒菜,这就是代理模式。代理...

白话
今天
23
0
Flink Window

1.Flink窗口 Window Assigner分配器。 窗口可以是时间驱动的(Time Window,例如:每30秒钟),也可以是数据驱动的(Count Window,例如:每一百个元素)。 一种经典的窗口分类可以分成: 翻...

满小茂
今天
18
0
my.ini

1

architect刘源源
今天
16
0
docker dns

There is a opensource application that solves this issue, it's called DNS Proxy Server It's a DNS server that solves containers hostnames, if could not found a hostname that mat......

kut
今天
17
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部