文档章节

另一种快速排序

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

没有更多内容

加载失败,请刷新页面

加载更多

laravel 微信支付

1.composer加载laravel微信支付第三方文件 composer require "overtrue/laravel-wechat:~4.0" composer require simplesoftwareio/simple-qrcode 1.3.* //composer生成二维码文件 2.改confi......

vio小黑
15分钟前
0
0
学习设计模式——抽象工厂模式

1. 认识抽象工厂模式 1. 定义:提供一个创建一系列相关或互相依赖的对象的接口,而无需指定它们具体的类。 2. 组成结构: AbstractFactory:抽象工厂类,定义创建一系列对象的操作接口 Fact...

江左煤郎
15分钟前
0
0
ES6的let块级作用域和变量不可提升导致一个比较容易出现的错误

今天在写NodeJS代码的时候出现一个变量一直提示未定义,简化后的代码如下: let param = 1;{ console.log(param);} 就在想,不至于啊。不是继承上层的声明吗? 继续看下去,发现原来...

MKjy
22分钟前
0
0
50:nginx访问日记|日记切割|静态文件不记录日记和过期时间

1、nginx访问日记: 日记格式:在主配置文件nginx.conf里搜索log_format; [root@localhost_001 conf]# vim nginx.conflog_format combined_realip '$remote_addr $http_x_forwarded_for ......

芬野de博客
26分钟前
0
0
前后端正常交互的流程

1、评审阶段:产品召集前后端进行需求评审,前后端各自捋清楚自己的业务量以及联调之间工作量,从而进行开发时间评估。 2、开发准备阶段:前后端一起商量需求中需要联调的部分,进行接口的口...

Jack088
26分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部