文档章节

数据算法之快速排序(quickSort)的Java实现

C
 Claroja
发布于 2017/05/08 23:20
字数 340
阅读 2
收藏 0

  本文的代码来自于《数据结构与算法(JAVA语言版)》,是笔者在网上找到的资料,非正式出刊版物。笔者对代码一些比较难以理解的部分添加了注释和图解,欢迎大家来讨论。
  快速排序的基本思想是通过一个枢轴,将比枢轴小的数排在枢轴左边,将比枢轴大的数字排在枢轴右边,然后再对两边分别快速排序。


  如图所示
快速排序


输入:数据元素数组r,划分序列区间[low..high]
输出:将序列划分为两个子序列并返回枢轴元素的位置

private int partition(Object[] r, int low, int high){
    Object pivot = r[low]; //使用r[low]作为枢轴元素
    while (low<high){ //从两端交替向内扫描
        while(low<high&&strategy.compare(r[high],pivot)>=0) high--;
        r[low] = r[high]; //将比pivot 小的元素移向低端
        while(low<high&&strategy.compare(r[low],pivot)<=0) low++;
        r[high] = r[low]; //将比pivot 大的元素移向高端
    }
    r[low] = pivot; //设置枢轴
    return low; //返回枢轴元素位置
}

输入:数据元素数组r,数组r 的待排序区间[low..high]
输出:数组r 以关键字有序

public void quickSort(Object[] r, int low, int high){
    if (low<high){
        int pa = partition(r,low,high);
        quickSort(r,low,pa-1);
        quickSort(r,pa+1,high);
    }
}

© 著作权归作者所有

C
粉丝 0
博文 128
码字总数 44892
作品 0
南京
私信 提问
使用Java泛型实现快速排序(快排,Quicksort)算法

快排算法的特点 实用性强。 很多实际的项目中使用了快排算法。但通常对算法都进行了调整(tuning),比如Java.util.Arrays类中的sort函数就使用了快排算法,但使用了双参考值(Dual-Pivot Qu...

NealFeng
2013/10/18
7.1K
0
好程序员Java教程教你5分钟了解快速排序

好程序员Java教程教你5分钟了解快速排序,前言: 快速排序是面试中经常会问到的一种排序算法,对比其他一些排序算法,快速排序的平均时间相对较少。 快速排序思想介绍 快速排序使用了分治的思...

好程序员IT
06/21
38
0
java 通配符的应用— java 排序算法

这几天无聊,又重新学起java的排序算法,为DualPivotQuickSort做准备。为了更好地适应各种情况,我们选择使用通用类型T和通配符的上下界来实现,同时这次谈的是对数组对象的排序。如果你对j...

天地一MADAO_
2014/03/02
117
0
08《Java核心技术》之Vector、ArrayList、LinkedList有何区别?

一、提出问题 我们在日常的工作中,能够高效地管理和操作数据是非常重要的。由于每个编程语言支持的数据结构不尽相同,比如我们最早接触到的 C 语言,需要自己实现很多基础数据结构,管理和操...

飞鱼说编程
2018/10/11
33
0
算法设计:两种快速排序代码实现

快速排序是一种高效且使用广泛的排序算法,在很多语言的标准库中自带的排序都是快速排序,所以我们也有必要了解快排的原理以及其实现方法。 快排的大致思想 快速排序实现的重点在于数组的拆分...

Sunrise_1018
2018/11/23
0
0

没有更多内容

加载失败,请刷新页面

加载更多

设计模式之访问者模式

定义 Represent an operation to be performed on the elements of an object structure. Visitor lets you define a new operation without changing the classes of the elements on which......

陈年之后是青葱
昨天
9
0
PhotoShop 高级应用 : 分层云彩 - 简单闪电效果

1.创建黑白渐水平渐变图层 2.选择滤镜选项卡: 渲染--->分层云彩功能 3.将滤镜-云彩效果渲染后的图层进行反相操作 【此时出现闪电效果】 6.调整色阶,使得闪电效果更明显 7.创建剪贴蒙版:色...

东方墨天
昨天
9
0
三种实现Android主界面Tab的方式

三种实现Android主界面Tab的方式 https://www.cnblogs.com/caobotao/p/5103673.html

shzwork
昨天
9
0
java8-Optional类

背景 NPE问题,100%的Java程序员都碰到,并且曾经是心中的痛。 1965年英国TonyHoare引入了Null引用,后续的设计语言包括Java都保持了这种设计。 一个例子 业务模型 Person 有车一族, 有Car...

春天springcarter
昨天
11
0
py 登录github时token以及cookie的应用

import requestsfrom bs4 import BeautifulSoup## 获取tokenr1 = requests.get('https://github.com/login')s1 = BeautifulSoup(r1.text,'html.parser')token = s1.find(name='input',......

子枫Eric
昨天
8
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部