文档章节

另一种快速排序

兔之
 兔之
发布于 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

© 著作权归作者所有

共有 人打赏支持
兔之
粉丝 66
博文 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

没有更多内容

加载失败,请刷新页面

加载更多

下一页

bat强制启用宏

运行bat文件后,将宏的安全等级设为低,达到启用宏的目的。 REM 这个文件将提供用户快速设置Excel宏的安全等级@ECHO OFFCLS:cmd4REG ADD "HKEY_CURRENT_USER\Software\Mi...

tedzheng
3分钟前
0
0
流,用声明性的方式处理数据集 - 读《Java 8实战》

引入流 Stream API的代码 声明性 更简洁,更易读 可复合 更灵活 可并行 性能更好 流是什么? 它允许以声明方式处理数据集合 遍历数据集的高级迭代器 透明地并行处理 简短定义:从支持数据处理...

yysue
4分钟前
0
0
postman发送json格式的post请求

postman发送json格式的post请求 在地址栏里输入请求url:http://127.0.0.1:8081/getmoney 选择“POST”方式, 在“headers”添加key:Content-Type , value:application/json 点击"body",''ra...

两广总督bogang
11分钟前
0
0
Javascript将html转成pdf,下载(html2canvas 和 jsPDF)

最近碰到个需求,需要把当前页面生成pdf,并下载。弄了几天,自己整理整理,记录下来,我觉得应该会有人需要 :) 项目源码地址:https://github.com/linwalker/render-html-to-pdf html2ca...

孟飞阳
11分钟前
0
0
pureftp源码编译及设定

--- use for RHEL 567 and Ubuntu 1604 1. download pureftpd wget http://download.pureftpd.org/pub/pure-ftpd/releases/pure-ftpd-1.0.47.tar.bz2 2. install gcc #apt-get install -y li......

zzimac
14分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部