Java基于分治法实现的快速排序算法示例
作者:誰將旧詞译成新曲 发布时间:2023-12-15 07:39:06
标签:Java,分治法,快速排序,算法
本文实例讲述了Java基于分治法实现的快速排序算法。分享给大家供大家参考,具体如下:
package cn.nwsuaf.quick;
/**
* 随机产生20个数,并对其进行快速排序
*
* @author 刘永浪
*
*/
public class Quick {
/**
* 交换函数,实现数组中两个数的交换操作
*
* @param array
* 待操作数组
* @param i
* 交换数组的第一个下标
* @param j
* 交换数组的第二个下标
*/
public static void swap(int[] array, int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
/**
* 分治法划分算法
*
* @param array
* 待操作数组
* @param low
* 划分中模块的起始地址
* @param height
* 划分中模块的结束地址
* @return 基准元素的位置下标
*/
public static int quick(int[] array, int low, int height) {
// 设置第一个数为基准元素
int pivot = array[low];
// 从右向左扫描,查找第1个小于pivot的元素
while (low < height) {
while (low < height && array[height] >= pivot)
height--;
// 表示找到了小于pivot的元素
if (low < height)
// 交换后low执行+1操作
swap(array, low++, height);
// 从左向右扫描,查找第1个大于pivot的元素
while (low < height && array[low] <= pivot)
low++;
// 表示找到了大于pivot的元素
if (low < height)
// 交换后heigh执行-1操作
swap(array, low, height--);
}
// 返回基准元素最终位置下标
return height;
}
/**
* 对array快速排序
*
* @param array
* 待操作数组
* @param low
* 低位
* @param height
* 高位
*/
public static void sort(int[] array, int low, int height) {
// 记录划分后的基准元素所对应的位置
int temp;
// 仅当区间长度大于1时才须排序
if (low < height) {
// 对array做划分
temp = quick(array, low, height);
// 对左区间递归排序
sort(array, low, temp - 1);
// 对右区间递归排序
sort(array, temp + 1, height);
}
}
public static void main(String[] args) {
int[] array = new int[20];
System.out.println("脚本之家测试结果:");
System.out.print("排序前序列:");
for (int i = 0; i < array.length; i++) {
// 随机产生20个0-99的整数
array[i] = (int) (Math.random() * 100);
System.out.print(array[i] + " ");
}
System.out.print("\n排序后序列:");
sort(array, 0, array.length - 1);
for (int i = 0; i < array.length; i++)
System.out.print(array[i] + " ");
}
}
运行结果:
PS:这里再为大家推荐一款关于排序的演示工具供大家参考:
在线动画演示插入/选择/冒泡/归并/希尔/快速排序算法过程工具:
http://tools.jb51.net/aideddesign/paixu_ys
希望本文所述对大家java程序设计有所帮助。
来源:http://blog.csdn.net/lylwanan/article/details/41447881
0
投稿
猜你喜欢
- Java中可以使用关键字synchronized进行线程同步控制,实现关键资源顺序访问,避免由于多线程并发执行导致的数据不一致性等问题。sy
- Java常用API介绍API概念什么是API?API(Application Programming interface) 应用程序编程接口
- 一、interrupt的使用特点我们先看2个线程打断的示例首先是可打断的情况:@Testpublic void interruptedTes
- 几个月前写过一篇博客《xUtils3.0框架学习笔记》 ,上面也有记录通过xUtils实现文件上传的使用方法,代码如下:private vo
- 为什么要使用路由在之前我们的代码中,页面跳转使用的代码如下所示:Navigator.of(context).push( Mate
- Java * 要想了解Java * ,首先要了解什么叫做代理,熟悉设计模式的朋友一定知道在Gof总结的23种设计模式中,有
- “Java is still not dead—and people are starting to figure that out.”本教
- 在eclipse中默认的maven,它加载的是国外的镜像,那样速度会比较慢,如果使用国内镜像,比如阿里的中央仓库;速度会快很多。那如何修改m
- 先看代码public class TestDemo1 { public static void main(String[] ar
- 微信分享接口的java开发的一些小步骤,具体内容如下1.配置接口信息进行验证代码如下: /** * 访问没认证的地
- 详解HDFS多文件Join操作的实例最近在做HDFS文件处理之时,遇到了多文件Join操作,其中包括:All Join以及常用的Left J
- 前言使用SpringBoot来开发项目相对于传统模式,要快速优雅许多,相信目前国内绝大部分web项目的开发还没有使用SpringBoot来做
- 好久就想着好好搭建一个ssm框架,自己以后用也方便吧,但是最近的事真的是很多,很多事情都没有去干,有时候自己会怀疑一下人生自己该不该去做程序
- 所谓文件的断点续传,就是一个线程传输文件,另一个线程控制传输标识,以达到暂停文件效果、恢复文件上传的效果。本demo使用最基本的线程之间的通
- 时间处理相关类:1.java.util.Date:时间类2.java.text.DateFormat:时间格式化类(抽象类),实现类:jav
- 1. 为什么写这篇文章?事情是这样的,在 2021年6月10日早上我在CSDN上发布了文章《你真的懂Java怎么输出Hello World吗
- 最近有时间,写一些很简单、很基础的东西,主要在操作层面。主要考虑如下: 1、经常搭建开发环境,所以有必要记录一下,自己也可以备查; 2、给新
- 面试官:sychronized关键字有哪些特性?应聘者:可以用来修饰方法;可以用来修饰代码块;可以用来修饰静态方法;可以保证线程安全;支持锁
- Spring Boot可以和大部分流行的测试框架协同工作:通过Spring JUnit创建单元测试;生成测试数据初始化数据库用于测试;Spr
- 项目中用到用户定义运算公式进行就算的需求,这样需要进行字符串四则运算解析,下面提供字符串公式四则运算解析与计算工具类,需要的同学可参考。工具