各种排序算法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
内容概要：本文提出了一种基于RGB-D的多人检测和跟踪系统，适用于移动机器人和头戴式摄像头。该系统将RGB-D视觉里程计、感兴趣区域（ROI）处理、地平面估计、行人检测和多假设跟踪结合起来，形成一个强大的视觉系统，能在笔记本电脑上以超过20fps的速度运行。文章着重讨论了对象检测的优化方法，特别是在近距离使用基于深度的上半身检测器和远距离使用基于外观的全身检测器，以及如何利用深度信息来减少检测计算量和误报率。 适合人群：从事移动机器人、AR技术、计算机视觉和深度感知技术的研究人员和技术开发者。 使用场景及目标：① 移动机器人的动态避障和人群导航；② 增强现实中的人体追踪应用。该系统旨在提高移动平台在复杂环境下的行人检测和跟踪能力。 其他说明：该系统在多种室内和室外环境中进行了测试，并取得了优越的性能，代码已开源供学术研究使用。
内容概要：本文探讨了小学低年级汉语拼音教学中存在的主要问题及其对策。通过对国内外相关文献的综述以及在小学实习中的观察与访谈，作者指出当前汉语拼音教学中存在的三个主要问题：教师采用单一枯燥的教学方法、学生汉语拼音水平参差不齐以及学生缺乏良好的汉语拼音学习习惯。为此，提出了创新汉语拼音教学方法、提高教师专业素养、关注学生差异性、培养学生良好习惯四大策略。 适合人群：小学语文教师、教育研究人员、关心孩子教育的家长。 使用场景及目标：适用于小学低年级语文课堂教学，旨在改善汉语拼音教学的效果，提高学生的语言综合能力。 其他说明：文章基于实证研究得出结论，提供了具体的教学改进措施，具有较强的实用性和操作性。
帝国CMS7.5仿《酷酷游戏网》源码，帝国CMS手游综合门户网站模板，外观大气漂亮的手机游戏下载、游戏资讯、游戏新闻门户、综合手游门户网站模板，包含礼包功能、开测功能、专题、专区。 内有详细的搭建教程
Windows 上一款搜索引擎，它能够基于文件名快速定文件和文件夹位置
c语言实现如果cmd中的ping
证件照处理的Python脚本，我们可以考虑以下几个步骤： 面部检测：使用人脸检测算法来定位图片中的面部。 裁剪与缩放：裁剪出面部区域并调整到证件照的标准尺寸。 对齐：调整面部方向，使眼睛和嘴巴在标准位置。 亮度和对比度调整：根据需要增强图片的亮度和对比度。 背景处理：去除或替换背景，保持面部的清晰度。 保存图像：以适当的格式保存处理后的图像
建荣蓝牙AX2227+CW6639模块使用说明书
内容概要：本文档展示了如何在一个多线程环境中管理多个类实例之间的同步与通信。四个类（AA、BB、CC、DD）分别代表了不同的任务，在主线程中创建这四个类的实例并启动各自的子线程。每个任务在其子线程内执行时，需要通过互斥锁(std::mutex)和条件变量(std::condition_variable)与其他任务协调运行时机，确保按序依次激活各自的任务。具体来说，AA 类的任务是整个链条的起点，通过设置一个布尔值触发器并唤醒等待的 BB 类，之后每次当某一任务完成自己部分的工作后都会更新这个触发状态，并唤醒后续等待的任务，以此方式循环往复。文章最后还包含了 main 函数，演示了如何在实际应用中整合这些组件来形成一个多线程协作的应用程序示例。 适合人群：对于C++语言有一定掌握能力的学习者或者开发者，尤其是对多线程编程感兴趣的读者。 使用场景及目标：帮助读者理解和实践在C++环境下，如何利用互斥量和条件变量实现多任务间的有序执行和有效沟通。同时也适用于讲解多线程基础知识的教学案例或项目。 其他说明：此示例中采用了最简单的线程同步机制——条件变量与互斥锁相结合的方法，虽然实现了基本的功能但可能不适应所有复杂的应用场景，实际生产环境还需要考虑更多的因素如性能优化、死锁避免等问题。此外，本例子没有考虑到异常处理的情况，如果要在实际项目中采用类似的解决方案，则需增加相应的错误处理逻辑以增强程序稳定性。
内容概要：本文围绕小学低年级识字教学中存在的问题及解决方案展开讨论。通过文献分析、观察和访谈等方法，发现了目前小学识字教学中的主要问题，如忽视识字内容与学生的年龄特点、识字教学层次不清、教学视野狭窄及学生缺乏学习兴趣和动机等。文章深入分析了这些问题的原因，并提出了具体的解决策略，包括重视学生个体差异、加强识字教学实效性、探索新的教学路径及拓宽教学视野等。 适合人群：小学语文教师、教育研究人员、小学教育管理者及对小学低年级语文教学感兴趣的读者。 使用场景及目标：旨在帮助一线教师提高小学低年级识字教学效果，培养学生的识字兴趣和自主学习能力；同时为教育管理者提供参考，优化小学语文教学管理策略。 其他说明：本文结合国内外研究成果，详细论述了识字教学的现状与问题，提出了一系列实用性强的对策，有助于提升小学低年级语文教学质量。
内容概要： 本文介绍了一个基于OpenCV库实现的信用卡数字识别系统。该系统能够从信用卡的图像中自动识别并提取卡号信息，极大地提高了信用卡信息输入的效率和准确性。文章首先概述了数字识别技术在金融领域的应用背景，然后详细阐述了系统的工作原理，包括图像预处理、数字定位、特征提取和分类识别等关键步骤。介绍了如何使用OpenCV进行图像处理，以及如何结合机器学习算法（如支持向量机SVM）来提高识别的准确率。最后，提供了完整的代码实现，并解释了代码的关键部分，包括如何处理图像中的噪声、如何分割数字以及如何训练和使用分类器。 使用场景和目标： 基于OpenCV的信用卡数字识别技术在金融科技、电子商务和客户服务等领域有着广泛的应用。在金融科技领域，该技术可以用于快速录入信用卡信息，减少人工输入错误，提高支付和验证流程的安全性和效率。在电子商务中，自动识别信用卡信息可以简化在线支付流程，提升用户体验。在客户服务中，该技术可以帮助客服人员快速获取客户信用卡信息，加快问题处理速度。此外，该技术还可以用于信用卡欺诈检测和风险管理，通过分析信用卡使用模式来识别异常交易。本文的目标是提供一个准确、可靠的信用卡
c语言做的播放器源码
BLDC无刷直流电机和PMSM永磁同步电机 基于stm32F1的有传感器和无传感驱动 直流无刷电机有传感器和无传感驱动程序， 无传感的实现是基于反电动势过零点实现的，有传感是霍尔实现。 永磁同步电机有感无感程序，有感为霍尔FOC和编码器方式， 无感为滑模观测器方式。 有原理图和文档 可供学习参考 程序有详细注释。
是一款免费、开源、跨平台文件传输工具,可以方便地在不同设备之间共享文件。它支持多种设备和操作系统,包括Windows、Mac、Linux、Android和iOS等。 LocalSend 使用REST API和HTTPS加密实现设备之间的安全通信。与依赖外部服务器的其他消息应用程序不同，LocalSend 不需要互联网连接或第三方服务器，因此成为本地通信的快速可靠解决方案。 创建一个名为 settings.json 的文件，放置在与可执行文件相同的目录中。 此文件可以为空。 应用程序将使用此文件来存储设置，而不是默认位置。 LocalSend 使用安全通信协议，允许设备通过 REST API 进行通信。所有数据都通过 HTTPS 安全地发送，并且 TLS/SSL 证书会在每台设备上动态生成，确保最大的安全性。
1228 后工序问题讨论.docx
【2024年电赛H题代码】是关于电子设计竞赛中的一项任务，这个任务主要涉及了软件、插件的使用，以及2024年电子竞赛H题的解决方案。在这一项目中，参赛者可能需要处理信号，并使用C语言编程以及STM32微控制器进行硬件控制。"separate_f1"这个文件可能是处理数据或功能模块的第一部分，可能是源代码文件或数据文件。 我们要理解电赛（电子设计竞赛）通常是针对大学生的一类科技竞赛，旨在提高学生的创新能力和实践技能，尤其是电子工程和计算机科学领域。在2024年的电赛H题中，参赛者可能需要解决一个与信号处理相关的挑战。信号处理涵盖了数字信号处理技术，包括滤波、频谱分析、编码解码等，这些都可能在实际应用中，如通信系统、图像处理或音频处理等领域发挥关键作用。 STM32是一款基于ARM Cortex-M内核的微控制器，由意法半导体（STMicroelectronics）制造。它被广泛用于嵌入式系统，因为其具有高性能、低功耗和丰富的外设接口。在电赛H题中，STM32可能作为核心处理器，负责采集信号、执行计算任务并控制外部设备。 C语言是一种通用的、面向过程的编程语言，特别适合用于系统级编程
介绍 Best-of-N (BoN) Jailbreaking，一种简单且有效的黑盒攻击算法，可以绕过多种模态的前沿 AI 系统的安全措施。 BoN 通过对提示进行多次采样和增强，直到诱发出有害的响应。 在闭源语言模型上取得了高攻击成功率 (ASR)，例如在 GPT-4o 上达到 89%，在 Claude 3.5 Sonnet 上达到 78%。 能够绕过最先进的开源防御机制，例如断路器。 可以扩展到其他模态，例如视觉语言模型 (VLM) 和音频语言模型 (ALM)。 ASR 随着采样次数 (N) 的增加呈幂律分布。 可以与其他黑盒算法结合使用，例如将 BoN 与优化前缀攻击结合，可以将 ASR 提高 35%。
1. 用户管理 用户注册与登录：支持学生、教师及管理员通过邮箱或身份证号码注册和登录。 角色权限管理：根据用户类型（如学生、教师、管理员）设置不同的权限，确保信息安全与隐私保护。 2. 考试信息管理 考试安排管理：管理员可以创建、修改和删除考试安排，包括考试时间、地点、科目等信息。 考生信息录入：记录每位考生的基本信息，如姓名、学号、班级、联系方式等。 3. 考试报名 在线报名系统：学生可以在线选择所需报考的科目并进行报名，系统实时更新可用名额。 报名状态查询：学生可以查看自己的报名状态，包括已报名、待审核、审核通过等信息。 4. 考试资源管理 试题库管理：系统支持上传、编辑和分类各种类型的试题，方便后续调取与使用。 试卷生成：根据设定的规则和标准，从试题库中自动生成试卷，并生成PDF文件供打印。 5. 考试监控与管理 考场安排：管理员可以根据考生人数和考场数量合理安排考场，并分配监考老师。 监考记录：监考人员可在系统上记录考生的出勤情况以及考试中的违规行为。 6. 成绩管理 成绩录入：教师可在系统内录入考生的考试成绩，支持批量导入和手动输入。 成绩查询：学生可随时查询个人的考试成绩，
web3.js 英文手册