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

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

2006-09-02 598
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 用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冯坚持
|
2月前
|
存储 人工智能 算法
数据结构与算法细节篇之最短路径问题：Dijkstra和Floyd算法详细描述，java语言实现。
这篇文章详细介绍了Dijkstra和Floyd算法，这两种算法分别用于解决单源和多源最短路径问题，并且提供了Java语言的实现代码。
java冯坚持
97 3
数据结构与算法细节篇之最短路径问题：Dijkstra和Floyd算法详细描述，java语言实现。
蓝易云
|
6天前
|
缓存 算法 搜索推荐
Java中的算法优化与复杂度分析
在Java开发中，理解和优化算法的时间复杂度和空间复杂度是提升程序性能的关键。通过合理选择数据结构、避免重复计算、应用分治法等策略，可以显著提高算法效率。在实际开发中，应该根据具体需求和场景，选择合适的优化方法，从而编写出高效、可靠的代码。
蓝易云
20 6
软件求生
|
4月前
|
搜索推荐 算法 Java
手写快排：教你用Java写出高效排序算法！
快速排序（QuickSort）是经典的排序算法之一，基于分治思想，平均时间复杂度为O(n log n)，广泛应用于各种场合。在这篇文章中，我们将手写一个Java版本的快速排序，从基础实现到优化策略，并逐步解析代码背后的逻辑。
软件求生
189 1
java冯坚持
|
2月前
|
算法 搜索推荐 Java
java 后端 使用 Graphics2D 制作海报，画echarts图，带工具类，各种细节：如头像切割成圆形，文字换行算法（完美实验success），解决画上文字、图片后不清晰问题
这篇文章介绍了如何使用Java后端技术，结合Graphics2D和Echarts等工具，生成包含个性化信息和图表的海报，并提供了详细的代码实现和GitHub项目链接。
java冯坚持
158 0
java 后端 使用 Graphics2D 制作海报，画echarts图，带工具类，各种细节：如头像切割成圆形，文字换行算法（完美实验success），解决画上文字、图片后不清晰问题
GuGuStudy
|
2月前
|
存储 搜索推荐 算法
【用Java学习数据结构系列】七大排序要悄咪咪的学（直接插入，希尔，归并，选择，堆排，冒泡，快排）以及计数排序（非比较排序）
【用Java学习数据结构系列】七大排序要悄咪咪的学（直接插入，希尔，归并，选择，堆排，冒泡，快排）以及计数排序（非比较排序）
GuGuStudy
33 1
java冯坚持
|
2月前
|
算法 Java Linux
java制作海报一：java使用Graphics2D 在图片上写字，文字换行算法详解
这篇文章介绍了如何在Java中使用Graphics2D在图片上绘制文字，并实现自动换行的功能。
java冯坚持
156 0
dream_ready
|
2月前
|
算法 Java 测试技术
数据结构 —— Java自定义代码实现顺序表，包含测试用例以及ArrayList的使用以及相关算法题
文章详细介绍了如何用Java自定义实现一个顺序表类，包括插入、删除、获取数据元素、求数据个数等功能，并对顺序表进行了测试，最后还提及了Java中自带的顺序表实现类ArrayList。
dream_ready
40 0
wljslmz
|
4月前
|
Java API
Java 8，如何对 ArrayList 元素进行排序？
【8月更文挑战第16天】
wljslmz
482 2
Java 8，如何对 ArrayList 元素进行排序？
土木林森
|
4月前
|
设计模式 缓存 算法
揭秘策略模式：如何用Java设计模式轻松切换算法？
【8月更文挑战第30天】设计模式是解决软件开发中特定问题的可重用方案。其中，策略模式是一种常用的行为型模式，允许在运行时选择算法行为。它通过定义一系列可互换的算法来封装具体的实现，使算法的变化与客户端分离。例如，在电商系统中，可以通过定义 `DiscountStrategy` 接口和多种折扣策略类（如 `FidelityDiscount`、`BulkDiscount` 和 `NoDiscount`），在运行时动态切换不同的折扣逻辑。这样，`ShoppingCart` 类无需关心具体折扣计算细节，只需设置不同的策略即可实现灵活的价格计算，符合开闭原则并提高代码的可维护性和扩展性。
土木林森
73 2
风吹落叶花飘荡
|
4月前
|
存储 Java
Java中ArrayList 元素的排序
本文提供了Java中根据`ArrayList`元素的某个属性进行排序的示例代码，包括实现`Comparable`接口和重载`compareTo`方法，然后使用`Collections.sort`方法进行排序。
风吹落叶花飘荡
29 1

热门文章

最新文章

  • 1
    Java volatile关键字：你真的懂了吗？
  • 2
    java小工具util系列2：字符串工具
  • 3
    Java爬虫：数据采集的强大工具
  • 4
    Java多线程并发编程：同步机制与实践应用
  • 5
    Java中的异常处理：从基础到高级
  • 6
    深入理解Java异常处理机制
  • 7
    Liunx部署java项目Tomcat、Redis、Mysql教程
  • 8
    Java爬虫：深入解析商品详情的利器
  • 9
    java实现从HDFS上下载文件及文件夹的功能，以流形式输出，便于用户自定义保存任何路径下
  • 10
    Java 异常处理：机制、策略与最佳实践
  • 1
    【Java开发指南 | 第三十一篇】Java 包(package)
    84
  • 2
    【Java开发指南 | 第二十九篇】Java接口
    50
  • 3
    【Java开发指南 | 第二十八篇】Java封装
    60
  • 4
    【Java开发指南 | 第二十六篇】Java多态
    41
  • 5
    【Java开发指南 | 第二十四篇】Java继承
    61
  • 6
    【Java开发指南 | 第九篇】访问实例变量和方法、继承、接口
    59
  • 7
    【Java开发指南 | 第八篇】Java变量、构造方法、创建对象
    93
  • 8
    Java Stream API详解与使用
    99
  • 9
    Java医院绩效考核系统源码B/S+avue+MySQL助力医院实现精细化管理
    82
  • 10
    《手把手教你》系列技巧篇（四十三）-java+ selenium自动化测试-处理https 安全问题或者非信任站点-上篇（详解教程）
    134

    • 相关课程

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

    • 相关电子书

    更多
  • Spring Cloud Alibaba - 重新定义 Java Cloud-Native
  • The Reactive Cloud Native Arch
  • JAVA开发手册1.5.0

    • 相关实验场景

    更多
  • 使用Swing算法实现商品推荐
  • 阿里云平台上进行Java程序的编译与运行
  • RSA密码算法设计与实现
  • 欧拉图的构造性证明与算法实现
  • 使用Java面向对象编写网络通信程序应用
  • 手动部署Java Web环境（Alibaba Cloud Linux 2）
    • 下一篇
    手把手教你白嫖阿里云服务器(免费领服务器)