各种排序算法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;
}
}
分享到：
相关推荐
各种排序算法java实现的源代码.zip
内容概要：本文探讨了高吞吐量网络链路异常检测中流量采样技术的应用及其效果。面对现代分布式信息系统频繁遭受的网络安全威胁，特别是互联网服务提供商（ISP）面临的威胁，作者提出一种通过减少数据采样频率以降低异常检测计算复杂度的方法。文中介绍了实验环境、系统架构、采用的数据聚合与采样方法以及用于检测异常的人工智能模型（基于自编码器神经网络）。通过对一个真实中型ISP生产环境中实际网络流量数据进行研究，该研究展示了即使在较低采样频率情况下仍能保持较高的异常检测准确性，尤其是针对持续时间较长的DDoS攻击更为显著。此外，论文还验证了所提系统的有效性和应用潜力，为构建高效的网络安全监控机制提供了新思路。 适用人群：对于计算机网络安全、数据分析或机器学习有兴趣的研究人员和从业人员，特别是那些专注于提高异常检测性能和应对高流量数据流的技术人员。 使用场景及目标：适用于希望在不影响业务操作的前提下引入额外层次防护措施的企业级网络管理员；研究者可参考本文中提出的流量预处理方式来探索不同的统计分布和采样间隔设置；企业可以通过部署该类系统快速响应潜在的安全事件并降低成本。
unity ui画线插件
内容概要：本文研究了在基于正交频分多址接入（OFDMA）的中继网络中进行带有比例公平性的下行链路资源分配问题。作者们通过联合优化中继选择、子载波分配和功率分配问题，并采用拉格朗日对偶分解方法求解这一复杂的NP完全问题。实验结果显示所提出的算法相较于启发式算法能显著提高系统吞吐量，并带来更好的用户间公平性。 适合人群：通信工程、无线网络优化、电信行业研发工程师和研究人员。 使用场景及目标：主要应用于提升4G移动通信系统的频谱效率及缓解频率选择衰落的问题，确保多用户之间的传输速率更加公平。同时适用于研究OFDMA技术及其相关领域的学者和技术专家。 其他说明：文中提供了详细的数学模型和模拟结果图表支持理论发现，并讨论了各种假设条件下的性能对比。此外还探讨了连续松弛技巧在解决NP完全问题时的应用价值以及通过调整算法参数来获得近似最优解的方法论意义。
程序系统设计]MATLAB打印纸缺陷检测GUI（不同缺陷类型，GUI界面） [程序系统设计]MATLAB打印纸缺陷检测GUI（不同缺陷类型，GUI界面） [程序系统设计]MATLAB打印纸缺陷检测GUI（不同缺陷类型，GUI界面） [程序系统设计]MATLAB打印纸缺陷检测GUI（不同缺陷类型，GUI界面） [程序系统设计]MATLAB打印纸缺陷检测GUI（不同缺陷类型，GUI界面）
邮件分拣组态王6.55和西门子S7-200plc联机程序2023，带io表，运行效果视频 ,邮件分拣; 组态王6.55; 西门子S7-200plc; 联机程序2023; IO表; 运行效果视频,邮件分拣组态王6.55与S7-200PLC联机程序2023版：带IO表运行效果视频
内容概要：本文提出了一种新的基于跨时间差异(CTD)注意力机制的变化检测方法（称为CTD-Former），用于高效地提取多时相遥感图像中的变化特征。作者重新审视了自注意力机制并深入挖掘多时间相位图像间的关系变化，构建CTD变压器编码器和解码器来增强这些特征。此外，还引入了一致性感知模块（CPB）以保护变化区域的空间结构。实验结果显示，在LEVIR-CD、WHU-CD和CLCD数据集上，该模型相比于当前最优的方法表现出更好的性能。 适合人群：对深度学习、遥感图像处理、尤其是变化检测感兴趣的研究人员和技术专家，特别是熟悉变换器网络架构的从业者。 使用场景及目标：此方法适用于需要从多时相对比遥感影像中识别变化情况的任务，如环境监测、灾害评估、城市规划等领域内的应用开发，能够帮助研究者和决策者更准确地了解地面物体随时间的变化趋势。 其他说明：源代码可在GitHub仓库中获取，这为未来的研究提供了一个重要的参考平台，有助于推动该领域的进一步发展。
该项目是个人实践项目，答辩评审分达到90分，代码都经过调试测试，确保可以运行！，可用于小白学习、进阶。 该资源主要针对计算机、通信、人工智能、自动化等相关专业的学生、老师或从业者下载使用，亦可作为期末课程设计、课程大作业、毕业设计等。 项目整体具有较高的学习借鉴价值！基础能力强的可以在此基础上修改调整，以实现不同的功能。 欢迎下载，欢迎沟通，互相学习，共同进步！提供答疑！
fajslghjlghg
2008-2020年各省每十万人口高等学校平均在校生数数据 1、时间：2008-2020年 2、来源：国家统计j、统计nj 3、指标：行政区划代码、地区名称、年份、每十万人口高等学校平均在校生数 4、范围：31省
毕业设计&课程设计 基于STM32单片机基于RFID的电动车停车管理系统（软件源码+硬件资料+部署教程+功能说明+演示视频），高分项目，开箱即用 用户 分为老师 及 学生 管理员 管理员 登录 用户管理 电动车管理 车卡rfid 电动车进出记录 挂失申请列表 解冻申请列表 补办列表申请 用户(只能管理自己的车) 注册（注册的时候选身份，选择学生或者老师） 登录 个人信息查看 电动车管理 进出校记录 挂失申请 解冻申请 补办申请
内容概要：本文探讨了一种新的基于深度强化学习的方法来解决旅行商问题与无人机组合优化（Traveling Salesman Problem with Drone, TSP-D），针对当前无人机辅助卡车配送中面临的协同调度难题进行了改进。研究者提出一种混合模型（HM），整合了注意力编码器和长短期记忆网络（LSTM）解码器的优势，从而有效地记录了多个车辆的动作序列并实现了协调路径规划。该方法在各种测试用例上展现了卓越性能，并能显著提高大型问题实例的计算效率，同时在实际应用场景如最后一步送货中有潜在的巨大价值。 适合人群：对物流系统优化和无人机应用有兴趣的专业人士，特别是从事最后一公里交付方案设计和技术实施的研究人员及工程师。 使用场景及目标：本研究所提出的深度学习框架主要适用于城市环境中复杂条件下的车辆和无人驾驶飞行系统的共同优化配置，目的是为了找到最优的货物递送方案，在最短的时间内完成所有的客户服务任务并返回起点。 其他说明：实验结果显示该算法在随机位置数据集和现实情况中的优越性超过了现有传统算法，表明它不仅能在简单理想情况下发挥良好效果，同样可以在更为复杂的条件下表现出稳定的性能。
北京中启航向科技发展有限公司开发的城市生活垃圾处理费智慧征管系统，是一个全方位、一体化的解决方案，旨在协助城市管理部门高效、准确地收取生活垃圾处理费。该系统利用先进的人工智能和数据分析技术，实现垃圾分类、计量和收费的智能化管理，提升城市环境卫生质量，同时优化行政资源，提高征收效率。
水测试试纸行业剖析：欧洲是全球最大的市场，占40%的份额.pdf
《电力电子技术(第5版)》王兆安_第2章_电力电子器件
基于STM32的直流电机加减速正反转控制串口输出控制系统（P 1100009-基于STM32的直流电机加减速正反转控制串口输出控制系统（PCB 原理图 报告 源代码 proteus lcd1602） 功能描述：基于STM32平台 1、实现了电机控制正转、反转的功能 2、实现了电机控制加速、减速的功能 3、实现了串口输出控制信息的功能 4、串口可以模拟WIFI 蓝牙 RS232 等带有串口的功能。 资料包含： 1、源代码工程文件 2、仿真工程文件 3、lunwen报告1W字以上 4、原理图工程文件 5、PCB工程文件 ,核心关键词：STM32、直流电机、加减速、正反转控制、串口输出、控制信息、WIFI、蓝牙、RS232、源代码工程文件、仿真工程文件、原理图工程文件、PCB工程文件。,基于STM32的电机串口控制综合系统（含正反转、加减速及多种串口通信功能）
ZYNQ7010采集AD7768
apollo 泊车轨迹优化代码 hybridastar+iaps平滑优化+obca平滑优化 第一个图是matlab绘制 后面的图是程序用sdl库绘制 ,apollo;泊车轨迹优化;hybridastar;iaps平滑优化;obca平滑优化;Matlab绘制;SDL库绘制,基于Apollo的泊车轨迹优化：HybridA*算法+平滑优化技术的实现与展示