AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

用Java实现几种常见的排序算法

2006-09-02 615
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 用Java语言实现的各种排序，包括插入排序、冒泡排序、选择排序、Shell排序、快速排序、归并排序、堆排序、SortUtil等。

用Java语言实现的各种排序，包括插入排序、冒泡排序、选择排序、Shell排序、快速排序、归并排序、堆排序、SortUtil等。

　　插入排序：

　　package org.rut.util.algorithm.support;
　　import org.rut.util.algorithm.SortUtil;
　　/**
　　* @author treeroot
　　* @since 2006-9-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 for(int j=i;(j>0)&&(data[j] SortUtil.swap(data,j,j-1);
　　　}
　　}

　　冒泡排序：

　　package org.rut.util.algorithm.support;
　　import org.rut.util.algorithm.SortUtil;
　　/**
　　* @author treeroot
　　* @since 2006-9-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 for(int j=data.length-1;j>i;j--)
　　　　{
　　　　　if(data[j] SortUtil.swap(data,j,j-1);
　　　　}
　　　}
　　}

　　选择排序：

　　package org.rut.util.algorithm.support;
　　import org.rut.util.algorithm.SortUtil;
　　/**
　　* @author treeroot
　　* @since 2009-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 2009-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 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 for(int j=i;(j>=inc)&&(data[j] SortUtil.swap(data,j,j-inc);
　　}

　　快速排序：

　　package org.rut.util.algorithm.support;
　　import org.rut.util.algorithm.SortUtil;
　　/**
　　* @author treeroot
　　* @since 2009-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] while((r!=0)&&data[--r]>pivot);
　　　　　SortUtil.swap(data,l,r);
　　　　}
　　　　while(l SortUtil.swap(data,l,r);
　　　　return l;
　　　}
　　}

　　改进后的快速排序：

　　package org.rut.util.algorithm.support;
　　import org.rut.util.algorithm.SortUtil;
　　/**
　　* @author treeroot
　　* @since 2006-9-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] while((r!=0)&&(data[--r]>pivot));
　　　　　　SortUtil.swap(data,l,r);
　　　　　}
　　　　　while(l 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 for(int j=i;(j>0)&&(data[j] SortUtil.swap(data,j,j-1);
　　　}
　　}
归并排序：

　　package org.rut.util.algorithm.support;
　　import org.rut.util.algorithm.SortUtil;
　　/**
　　* @author treeroot
　　* @since 2006-9-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] 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-9-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 for(int j=i;(j>start) && data[j] SortUtil.swap(data,j,j-1);
　　　}
　　}
堆排序：

　　package org.rut.util.algorithm.support;
　　import org.rut.util.algorithm.SortUtil;
　　/**
　　* @author treeroot
　　* @since 2006-9-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 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 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] 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-9-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
搜索推荐
Shell
关键词：
Java算法
Java排序
Java排序算法
Java实现
Java实现排序算法
老牛的博客
目录
相关文章
青云交（Java大数据AI云原生Python）
|
4月前
|
负载均衡 算法 关系型数据库
大数据大厂之MySQL数据库课程设计：揭秘MySQL集群架构负载均衡核心算法：从理论到Java代码实战，让你的数据库性能飙升！
本文聚焦 MySQL 集群架构中的负载均衡算法，阐述其重要性。详细介绍轮询、加权轮询、最少连接、加权最少连接、随机、源地址哈希等常用算法，分析各自优缺点及适用场景。并提供 Java 语言代码实现示例，助力直观理解。文章结构清晰，语言通俗易懂，对理解和应用负载均衡算法具有实用价值和参考价值。
青云交（Java大数据AI云原生Python）
307 14
大数据大厂之MySQL数据库课程设计：揭秘MySQL集群架构负载均衡核心算法：从理论到Java代码实战，让你的数据库性能飙升！
陌陌谣
|
4月前
|
存储 缓存 监控
上网行为监控系统剖析：基于 Java LinkedHashMap 算法的时间序列追踪机制探究
数字化办公蓬勃发展的背景下，上网行为监控系统已成为企业维护信息安全、提升工作效能的关键手段。该系统需实时记录并深入分析员工的网络访问行为，如何高效存储和管理这些处于动态变化中的数据，便成为亟待解决的核心问题。Java 语言中的LinkedHashMap数据结构，凭借其独有的有序性特征以及可灵活配置的淘汰策略，为上网行为监控系统提供了一种兼顾性能与功能需求的数据管理方案。本文将对LinkedHashMap在上网行为监控系统中的应用原理、实现路径及其应用价值展开深入探究。
陌陌谣
99 3
2G冲浪词条
|
4月前
|
人工智能 算法 NoSQL
LRU算法的Java实现
LRU（Least Recently Used）算法用于淘汰最近最少使用的数据，常应用于内存管理策略中。在Redis中，通过`maxmemory-policy`配置实现不同淘汰策略，如`allkeys-lru`和`volatile-lru`等，采用采样方式近似LRU以优化性能。Java中可通过`LinkedHashMap`轻松实现LRUCache，利用其`accessOrder`特性和`removeEldestEntry`方法完成缓存淘汰逻辑，代码简洁高效。
2G冲浪词条
174 0
智物科技库
|
3月前
|
存储 算法 安全
Java中的对称加密算法的原理与实现
本文详细解析了Java中三种常用对称加密算法（AES、DES、3DES）的实现原理及应用。对称加密使用相同密钥进行加解密，适合数据安全传输与存储。AES作为现代标准，支持128/192/256位密钥，安全性高；DES采用56位密钥，现已不够安全；3DES通过三重加密增强安全性，但性能较低。文章提供了各算法的具体Java代码示例，便于快速上手实现加密解密操作，帮助用户根据需求选择合适的加密方案保护数据安全。
智物科技库
327 58
蓝易云
|
2月前
|
监控 Java API
Java语言按文件创建日期排序及获取最新文件的技术
这段代码实现了文件创建时间的读取、文件列表的获取与排序以及获取最新文件的需求。它具备良好的效率和可读性，对于绝大多数处理文件属性相关的需求来说足够健壮。在实际应用中，根据具体情况，可能还需要进一步处理如访问权限不足、文件系统不支持某些属性等边界情况。
蓝易云
163 14
程序员小假
|
2月前
|
存储 负载均衡 算法
我们来说一说 Java 的一致性 Hash 算法
我是小假 期待与你的下一次相遇 ~
程序员小假
93 1
陌陌谣
|
2月前
|
存储 监控 算法
企业上网监控场景下布隆过滤器的 Java 算法构建及其性能优化研究
布隆过滤器是一种高效的数据结构，广泛应用于企业上网监控系统中，用于快速判断员工访问的网址是否为违规站点。相比传统哈希表，它具有更低的内存占用和更快的查询速度，支持实时拦截、动态更新和资源压缩，有效提升系统性能并降低成本。
陌陌谣
53 0
陌陌谣
|
9月前
|
监控 算法 网络协议
Java 实现局域网电脑屏幕监控算法揭秘
在数字化办公环境中，局域网电脑屏幕监控至关重要。本文介绍用Java实现这一功能的算法，涵盖图像采集、数据传输和监控端显示三个关键环节。通过Java的AWT/Swing库和Robot类抓取屏幕图像，使用Socket进行TCP/IP通信传输图像数据，并利用ImageIO类在监控端展示图像。整个过程确保高效、实时和准确，为提升数字化管理提供了技术基础。
陌陌谣
189 15
java冯坚持
|
11月前
|
存储 人工智能 算法
数据结构与算法细节篇之最短路径问题：Dijkstra和Floyd算法详细描述，java语言实现。
这篇文章详细介绍了Dijkstra和Floyd算法，这两种算法分别用于解决单源和多源最短路径问题，并且提供了Java语言的实现代码。
java冯坚持
557 3
数据结构与算法细节篇之最短路径问题：Dijkstra和Floyd算法详细描述，java语言实现。
陌陌谣
|
5月前
|
存储 机器学习/深度学习 监控
如何监控员工的电脑——基于滑动时间窗口的Java事件聚合算法实现探析​
在企业管理场景中，如何监控员工的电脑操作行为是一个涉及效率与合规性的重要课题。传统方法依赖日志采集或屏幕截图，但数据量庞大且实时性不足。本文提出一种基于滑动时间窗口的事件聚合算法，通过Java语言实现高效、低资源占用的监控逻辑，为如何监控员工的电脑提供一种轻量化解决方案。
陌陌谣
121 3

热门文章

最新文章

  • 1
    2025 年 Java 全栈从环境搭建到项目上线实操全流程指南：Java 全栈最新实操指南（2025 版）
  • 2
    Java浮点类型详解：使用与区别
  • 3
    2025 Java 零基础到实战最新技术实操全攻略与学习指南
  • 4
    Java中的Lambda表达式：简化代码的利器
  • 5
    Java Stream API：现代数据处理之道
  • 6
    Java中的Switch表达式：更简洁的多路分支
  • 7
    Java中的Lambda表达式：简洁与功能的结合
  • 8
    2025 年最新 Java 学习路线图含实操指南助你高效入门 Java 编程掌握核心技能
  • 9
    Java 项目实战从入门到精通 ：Java Web 在线商城项目开发指南
  • 10
    Java 项目实战教程从基础到进阶实战案例分析详解
  • 1
    综合案例【商品管理系统-Java基础版】（附完整源码）
    456
  • 2
    Java常见异常及对应解决办法
    165
  • 3
    19 Java8概述（Java8概述+lambda表达式+函数式接口+方法引用+Stream+新时间API）
    126
  • 4
    18 Java反射reflect（类加载+获取类对象+通用操作+设计模式+枚举+注解）
    272
  • 5
    17 Java多线程（线程创建+线程状态+线程安全+死锁+线程池+Lock接口+线程安全集合）（下）
    164
  • 6
    17 Java多线程（线程创建+线程状态+线程安全+死锁+线程池+Lock接口+线程安全集合）（中）
    169
  • 7
    17 Java多线程（线程创建+线程状态+线程安全+死锁+线程池+Lock接口+线程安全集合）（上）
    154
  • 8
    16 Java网络编程（计算机网络+网络模型OSI/TCP/IP+通信协议等）
    185
  • 9
    15 Java IO流（File类+IO流+字节流+字符流+字节编码）
    120
  • 10
    13 Java异常（异常过程解析、throw、throws、try-catch关键字）
    276

    • 相关课程

    更多
  • Java面试疑难点解析 - 面试技巧及语言基础
  • Java面试疑难点解析 - Java Web开发
  • Java面试疑难点解析 - 系统架构及项目设计
  • Java编程入门
  • Java面向对象编程
  • Java高级编程

    • 相关电子书

    更多
  • Spring Cloud Alibaba - 重新定义 Java Cloud-Native
  • The Reactive Cloud Native Arch
  • JAVA开发手册1.5.0
    • 下一篇
    蛋白质语言模型 ProGen：在实验室合成由 AI 预测的蛋白质