各种排序算法java实现
出处
插入排序:
package org.rut.util.algorithm.support;
import org.rut.util.algorithm.SortUtil;
/**
* @author treeroot
* @since 2006-2-2
* @version 1.0
*/
public class InsertSort implements SortUtil.Sort{
/* (non-Javadoc)
* @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
*/
public void sort(int[] data) {
int temp;
for(int i=1;i<data.length;i++){
for(int j=i;(j>0)&&(data[j]<data[j-1]);j--){
SortUtil.swap(data,j,j-1);
}
}
}
}
冒泡排序:
package org.rut.util.algorithm.support;
import org.rut.util.algorithm.SortUtil;
/**
* @author treeroot
* @since 2006-2-2
* @version 1.0
*/
public class BubbleSort implements SortUtil.Sort{
/* (non-Javadoc)
* @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
*/
public void sort(int[] data) {
int temp;
for(int i=0;i<data.length;i++){
for(int j=data.length-1;j>i;j--){
if(data[j]<data[j-1]){
SortUtil.swap(data,j,j-1);
}
}
}
}
}
选择排序:
package org.rut.util.algorithm.support;
import org.rut.util.algorithm.SortUtil;
/**
* @author treeroot
* @since 2006-2-2
* @version 1.0
*/
public class SelectionSort implements SortUtil.Sort {
/*
* (non-Javadoc)
*
* @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
*/
public void sort(int[] data) {
int temp;
for (int i = 0; i < data.length; i++) {
int lowIndex = i;
for (int j = data.length - 1; j > i; j--) {
if (data[j] < data[lowIndex]) {
lowIndex = j;
}
}
SortUtil.swap(data,i,lowIndex);
}
}
}
Shell排序:
package org.rut.util.algorithm.support;
import org.rut.util.algorithm.SortUtil;
/**
* @author treeroot
* @since 2006-2-2
* @version 1.0
*/
public class ShellSort implements SortUtil.Sort{
/* (non-Javadoc)
* @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
*/
public void sort(int[] data) {
for(int i=data.length/2;i>2;i/=2){
for(int j=0;j<i;j++){
insertSort(data,j,i);
}
}
insertSort(data,0,1);
}
/**
* @param data
* @param j
* @param i
*/
private void insertSort(int[] data, int start, int inc) {
int temp;
for(int i=start+inc;i<data.length;i+=inc){
for(int j=i;(j>=inc)&&(data[j]<data[j-inc]);j-=inc){
SortUtil.swap(data,j,j-inc);
}
}
}
}
快速排序:
package org.rut.util.algorithm.support;
import org.rut.util.algorithm.SortUtil;
/**
* @author treeroot
* @since 2006-2-2
* @version 1.0
*/
public class QuickSort implements SortUtil.Sort{
/* (non-Javadoc)
* @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
*/
public void sort(int[] data) {
quickSort(data,0,data.length-1);
}
private void quickSort(int[] data,int i,int j){
int pivotIndex=(i+j)/2;
//swap
SortUtil.swap(data,pivotIndex,j);
int k=partition(data,i-1,j,data[j]);
SortUtil.swap(data,k,j);
if((k-i)>1) quickSort(data,i,k-1);
if((j-k)>1) quickSort(data,k+1,j);
}
/**
* @param data
* @param i
* @param j
* @return
*/
private int partition(int[] data, int l, int r,int pivot) {
do{
while(data[++l]<pivot);
while((r!=0)&&data[--r]>pivot);
SortUtil.swap(data,l,r);
}
while(l<r);
SortUtil.swap(data,l,r);
return l;
}
}
改进后的快速排序:
package org.rut.util.algorithm.support;
import org.rut.util.algorithm.SortUtil;
/**
* @author treeroot
* @since 2006-2-2
* @version 1.0
*/
public class ImprovedQuickSort implements SortUtil.Sort {
private static int MAX_STACK_SIZE=4096;
private static int THRESHOLD=10;
/* (non-Javadoc)
* @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
*/
public void sort(int[] data) {
int[] stack=new int[MAX_STACK_SIZE];
int top=-1;
int pivot;
int pivotIndex,l,r;
stack[++top]=0;
stack[++top]=data.length-1;
while(top>0){
int j=stack[top--];
int i=stack[top--];
pivotIndex=(i+j)/2;
pivot=data[pivotIndex];
SortUtil.swap(data,pivotIndex,j);
//partition
l=i-1;
r=j;
do{
while(data[++l]<pivot);
while((r!=0)&&(data[--r]>pivot));
SortUtil.swap(data,l,r);
}
while(l<r);
SortUtil.swap(data,l,r);
SortUtil.swap(data,l,j);
if((l-i)>THRESHOLD){
stack[++top]=i;
stack[++top]=l-1;
}
if((j-l)>THRESHOLD){
stack[++top]=l+1;
stack[++top]=j;
}
}
//new InsertSort().sort(data);
insertSort(data);
}
/**
* @param data
*/
private void insertSort(int[] data) {
int temp;
for(int i=1;i<data.length;i++){
for(int j=i;(j>0)&&(data[j]<data[j-1]);j--){
SortUtil.swap(data,j,j-1);
}
}
}
}
归并排序:
package org.rut.util.algorithm.support;
import org.rut.util.algorithm.SortUtil;
/**
* @author treeroot
* @since 2006-2-2
* @version 1.0
*/
public class MergeSort implements SortUtil.Sort{
/* (non-Javadoc)
* @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
*/
public void sort(int[] data) {
int[] temp=new int[data.length];
mergeSort(data,temp,0,data.length-1);
}
private void mergeSort(int[] data,int[] temp,int l,int r){
int mid=(l+r)/2;
if(l==r) return ;
mergeSort(data,temp,l,mid);
mergeSort(data,temp,mid+1,r);
for(int i=l;i<=r;i++){
temp[i]=data[i];
}
int i1=l;
int i2=mid+1;
for(int cur=l;cur<=r;cur++){
if(i1==mid+1)
data[cur]=temp[i2++];
else if(i2>r)
data[cur]=temp[i1++];
else if(temp[i1]<temp[i2])
data[cur]=temp[i1++];
else
data[cur]=temp[i2++];
}
}
}
改进后的归并排序:
package org.rut.util.algorithm.support;
import org.rut.util.algorithm.SortUtil;
/**
* @author treeroot
* @since 2006-2-2
* @version 1.0
*/
public class ImprovedMergeSort implements SortUtil.Sort {
private static final int THRESHOLD = 10;
/*
* (non-Javadoc)
*
* @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
*/
public void sort(int[] data) {
int[] temp=new int[data.length];
mergeSort(data,temp,0,data.length-1);
}
private void mergeSort(int[] data, int[] temp, int l, int r) {
int i, j, k;
int mid = (l + r) / 2;
if (l == r)
return;
if ((mid - l) >= THRESHOLD)
mergeSort(data, temp, l, mid);
else
insertSort(data, l, mid - l + 1);
if ((r - mid) > THRESHOLD)
mergeSort(data, temp, mid + 1, r);
else
insertSort(data, mid + 1, r - mid);
for (i = l; i <= mid; i++) {
temp[i] = data[i];
}
for (j = 1; j <= r - mid; j++) {
temp[r - j + 1] = data[j + mid];
}
int a = temp[l];
int b = temp[r];
for (i = l, j = r, k = l; k <= r; k++) {
if (a < b) {
data[k] = temp[i++];
a = temp[i];
} else {
data[k] = temp[j--];
b = temp[j];
}
}
}
/**
* @param data
* @param l
* @param i
*/
private void insertSort(int[] data, int start, int len) {
for(int i=start+1;i<start+len;i++){
for(int j=i;(j>start) && data[j]<data[j-1];j--){
SortUtil.swap(data,j,j-1);
}
}
}
}
堆排序:
package org.rut.util.algorithm.support;
import org.rut.util.algorithm.SortUtil;
/**
* @author treeroot
* @since 2006-2-2
* @version 1.0
*/
public class HeapSort implements SortUtil.Sort{
/* (non-Javadoc)
* @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
*/
public void sort(int[] data) {
MaxHeap h=new MaxHeap();
h.init(data);
for(int i=0;i<data.length;i++)
h.remove();
System.arraycopy(h.queue,1,data,0,data.length);
}
private static class MaxHeap{
void init(int[] data){
this.queue=new int[data.length+1];
for(int i=0;i<data.length;i++){
queue[++size]=data[i];
fixUp(size);
}
}
private int size=0;
private int[] queue;
public int get() {
return queue[1];
}
public void remove() {
SortUtil.swap(queue,1,size--);
fixDown(1);
}
//fixdown
private void fixDown(int k) {
int j;
while ((j = k << 1) <= size) {
if (j < size && queue[j]<queue[j+1])
j++;
if (queue[k]>queue[j]) //不用交换
break;
SortUtil.swap(queue,j,k);
k = j;
}
}
private void fixUp(int k) {
while (k > 1) {
int j = k >> 1;
if (queue[j]>queue[k])
break;
SortUtil.swap(queue,j,k);
k = j;
}
}
}
}
SortUtil:
package org.rut.util.algorithm;
import org.rut.util.algorithm.support.BubbleSort;
import org.rut.util.algorithm.support.HeapSort;
import org.rut.util.algorithm.support.ImprovedMergeSort;
import org.rut.util.algorithm.support.ImprovedQuickSort;
import org.rut.util.algorithm.support.InsertSort;
import org.rut.util.algorithm.support.MergeSort;
import org.rut.util.algorithm.support.QuickSort;
import org.rut.util.algorithm.support.SelectionSort;
import org.rut.util.algorithm.support.ShellSort;
/**
* @author treeroot
* @since 2006-2-2
* @version 1.0
*/
public class SortUtil {
public final static int INSERT = 1;
public final static int BUBBLE = 2;
public final static int SELECTION = 3;
public final static int SHELL = 4;
public final static int QUICK = 5;
public final static int IMPROVED_QUICK = 6;
public final static int MERGE = 7;
public final static int IMPROVED_MERGE = 8;
public final static int HEAP = 9;
public static void sort(int[] data) {
sort(data, IMPROVED_QUICK);
}
private static String[] name={
"insert","bubble","selection","shell","quick","improved_quick","merge","improved_merge","heap"
};
private static Sort[] impl=new Sort[]{
new InsertSort(),
new BubbleSort(),
new SelectionSort(),
new ShellSort(),
new QuickSort(),
new ImprovedQuickSort(),
new MergeSort(),
new ImprovedMergeSort(),
new HeapSort()
};
public static String toString(int algorithm){
return name[algorithm-1];
}
public static void sort(int[] data, int algorithm) {
impl[algorithm-1].sort(data);
}
public static interface Sort {
public void sort(int[] data);
}
public static void swap(int[] data, int i, int j) {
int temp = data[i];
data[i] = data[j];
data[j] = temp;
}
}
分享到：
相关推荐
1.版本：matlab2014/2019a/2024a 2.附赠案例数据可直接运行matlab程序。 3.代码特点：参数化编程、参数可方便更改、代码编程思路清晰、注释明细。 4.适用对象：计算机，电子信息工程、数学等专业的大学生课程设计、期末大作业和毕业设计。
# 基于Spring Boot框架的用户管理系统 ## 项目简介 本项目是一个基于Spring Boot框架的用户管理系统，主要用于实现用户的注册、登录、权限管理等功能。项目使用了Spring Security框架进行身份验证和权限控制，结合JWT（JSON Web Token）实现无状态的会话管理。此外，项目还集成了SQLite数据库，简化了数据库的安装和配置。 ## 项目的主要特性和功能 1. 用户管理 用户注册、登录、登出功能。 用户信息的增删改查操作。 用户密码的修改和重置。 2. 权限管理 使用Spring Security进行权限控制。 通过JWT实现无状态的会话管理。 动态配置权限白名单，允许特定URL无需认证访问。 3. 系统监控 获取服务器的基本信息，如CPU、内存、JVM状态等。 提供服务器重启功能。 4. 邮件服务
基于springboot企业员工薪酬管理系统源码数据库文档.zip
Glmark2是Linux操作系统下广泛使用的3D图形性能测试工具，测试步骤： 1、搭建编译环境，安装必要的依赖项 sudo apt-get install g++ build-essential pkg-config sudo apt-get install libx11-dev libgl1-mesa-dev sudo apt-get install libjpeg-dev libpng-dev 2、执行配置、编译、安装命令： ./waf configure --with-flavors=x11-gl ./waf build -j 8 ##（8表示CPU核数） sudo ./waf install 3、终端中运行：$glmark2 4、等待测试完成（10min左右），结果分数越高，表示性能越好。
# 基于物联网的地震预警系统 ## 项目简介 随着自然灾害如风暴、地震、热浪和洪水等事件频率的增加，对这些事件的预测和了解的需求也日益凸显。本项目专注于地震预警系统，旨在利用物联网技术提供及时预警，对于保障安全和减少财产损失具有重要意义。 ## 项目目标 主要目标是开发一个能够检测地震早期预警信号的原型系统。该系统旨在通过可靠且高效的预警系统在地震多发区域提高安全性和应急准备。 ## 项目的主要特性和功能 1. 显示机制使用0.96英寸OLED显示屏和Adafruit NeoPixel Stick来展示地震数据。 2. 音频输出集成蜂鸣器以提供可听警告。 3. 电源来源采用Arduino Uno REV3作为电源。 4. 地震检测使用SW420振动传感器。 5. 时间保持引入DS3231实时时钟以准确记录事件。 6. 多级预警根据振动强度，系统能够触发不同级别的视觉和听觉警告。 ## 安装使用步骤 1. 硬件连接
keil5.26开发编译环境
# 基于TensorFlow的中文文本分类系统 ## 项目简介 本项目是一个基于TensorFlow的中文文本分类系统，使用卷积神经网络（CNN）和循环神经网络（RNN）进行文本分类。项目涵盖了从数据预处理、模型训练、模型评估到模型预测的全流程，旨在提供一个高效的中文文本分类解决方案。 ## 主要特性和功能 数据预处理包括读取文件数据、构建词汇表、转换分类目录、将文本数据转换为ID序列表示等。 模型构建实现了基于CNN和RNN的文本分类模型，支持LSTM和GRU作为RNN的单元。 模型训练提供了详细的训练配置，包括学习率、批次大小、迭代轮次等参数的设置。 模型评估在验证集上评估模型的性能，输出准确率、损失等信息，并生成混淆矩阵。 模型预测加载训练好的模型，对新的文本消息进行分类预测，并输出预测类别。 ## 安装使用步骤 1. 环境准备 安装Python 23 安装TensorFlow 1.3以上
基于springboot的智慧医疗采购系统源码数据库文档.zip
1、资源内容地址：https://blog.csdn.net/abc6838/article/details/143896285 2、数据特点：今年全新，手工精心整理，放心引用，数据来自权威，且标注《数据来源》，相对于其他人的控制变量数据准确很多,适合写论文做实证用 ，不会出现数据造假问题 3、适用对象：大学生，本科生，研究生小白可用，容易上手！！！ 4、课程引用: 经济学，地理学，城市规划与城市研究，公共政策与管理，社会学，商业与管理
基于SpringBoot+Vue的志愿者招募管理系统源码数据库文档.zip
本教程介绍了 Ruby 的基础语法、面向对象特性和高级功能（如代码块、异常处理和元编程），并提供了练习任务及其答案，帮助您快速入门并熟悉 Ruby 的强大功能。通过完成这些任务，您可以轻松掌握 Ruby 编程的核心技能。
# 基于C++的日志数据管理系统 ## 项目简介 本项目是一个基于C++的日志数据管理系统（DMS），主要用于在Linux环境下采集、处理和发送日志数据。系统通过读取日志文件、处理登录记录、匹配登录和登出记录，并将处理后的数据发送到服务器。项目结合了多线程技术，确保数据处理的效率和系统的响应性。 ## 项目的主要特性和功能 1. 日志读取与处理 读取日志文件并处理其中的登录记录。 匹配登录和登出记录，保存匹配和未匹配的记录。 处理字节序问题，确保数据准确性。 2. 日志数据发送 向服务器发送处理后的日志数据。 处理发送失败的情况，保存未成功发送的日志记录。 3. 多线程支持 使用多线程技术处理日志读取和发送，提高系统的并发处理能力。 通过线程间通信实现界面更新和数据处理。 4. 用户界面 提供基于Qt的客户端界面，用于显示数据和控制客户端操作。
编号：463 开发软件: Vs2008以上版本 数据库: sqlserver2005以上版本 开发语言和技术: C#结合三层开发模式 系统功能： 出租车管理查询系统开发设计要求能根据出租车的特点，时刻记录着车的实际位置，如经纬度、车速、方向，载客等情况，根据该系统可以方便用户快速的查询到车辆的状态位置等。因此要求系统具有录入、修正、查询、统计、分析等功能。采用asp.net和sqlserver来完成 出租车辆管理 出租车公司 驾驶员管理 模拟真实数据给一个录入模块根据时间查询其当时位置 前台可以查看车辆信息 驾驶员信息 出租公司信息 出租车运行路线查询 可以留言
基于springboot的招聘求职系统源码数据库文档.zip
# 基于Arduino的温湿度监测显示系统 ## 项目简介 该项目旨在设计一个基于Arduino的温湿度监测显示系统。通过DHT11温湿度传感器采集数据，并通过LCD显示屏展示温度和湿度信息。此外，项目还包含一个简单的状态图标显示功能。整个系统采用Arduino Uno作为主控板，操作简单，便于用户随时查看当前环境的温湿度情况。 ## 项目的主要特性和功能 1. 温湿度监测使用DHT11温湿度传感器实时监测环境温湿度。 2. LCD显示通过LCD显示屏展示温度和湿度信息，支持两行显示，每行最多显示16个字符。 3. 状态图标根据当前温度展示不同的状态图标，用于快速了解当前环境状况。 4. 简单易懂界面简洁明了，操作方便，适合各种用户群体使用。 ## 安装使用步骤 1. 硬件准备准备Arduino Uno、LCD显示屏、DHT11温湿度传感器、i2c模块等硬件。 2. 连接硬件按照项目中的Pinout图连接各硬件组件。
基于springboot高校创新创业课程体系源码数据库文档.zip
文档讲述了NS3中CSMA模型介绍（包括信道模型、网络设备、MAC和PHY等），并对CSMAHelper代码中数据收发处理流程、CSMA退避机制和状态机切换进行分析。
1.版本：matlab2014/2019a/2024a 2.附赠案例数据可直接运行matlab程序。 3.代码特点：参数化编程、参数可方便更改、代码编程思路清晰、注释明细。 4.适用对象：计算机，电子信息工程、数学等专业的大学生课程设计、期末大作业和毕业设计。
# 基于C语言的服务器集群健康检测系统 ## 项目简介 本项目是一个基于C语言的服务器集群健康检测系统。它通过客户端和服务器端的通信，实现服务器集群的健康状态监控。客户端定期向服务器发送心跳信号，服务器则接收并响应客户端的请求，以确保集群节点的可用性。同时，该系统还具备数据交互功能，允许客户端向服务器发送数据，服务器接收数据后进行处理并返回响应。此外，系统还包含恶意进程监控功能，以防范可能的恶意行为。 ## 项目的主要特性和功能 1. 心跳检测客户端定期向服务器发送心跳信号，以检测服务器集群的健康状态。 2. 数据交互客户端可以向服务器发送数据，服务器接收数据并处理，然后返回响应。 3. 恶意进程监控系统能够监控可能的恶意进程，确保服务器的安全。 4. 共享内存管理客户端和服务器使用共享内存进行通信和同步。 5. 日志记录系统的关键操作，如心跳检测、数据交互等，都会记录到日志文件中，以便于问题的追踪和调试。 ## 安装使用步骤