java实现的各种排序算法代码示例
折半插入排序是对直接插入排序的简单改进。此处介绍的折半插入，其实就是通过不断地折半来快速确定第i个元素的
插入位置，这实际上是一种查找算法：折半查找。Java的Arrays类里的binarySearch()方法，就是折半查找的实现，用
于从指定数组中查找指定元素，前提是该数组已经处于有序状态。与直接插入排序的效果相同，只是更快了一些，因
为折半插入排序可以更快地确定第i个元素的插入位置
代码：
packageinterview;
/**
*@authorAdministrator
*折半插入排序
*/
publicclassBinaryInsertSort{
publicstaticvoidbinaryInsertSort(DataWrap[]data){
System.out.println("开始排序");
intarrayLength=data.length;
for(inti=1;i0){
low=mid+1;
}else{
high=mid-1;
}
}
for(intj=i;j>low;j--){
data[j]=data[j-1];
}
data[low]=temp;
System.out.println(java.util.Arrays.toString(data));
}
}
publicstaticvoidmain(String[]args){
DataWrap[]data={newDataWrap(9,""),newDataWrap(-16,""),
newDataWrap(21,"*"),newDataWrap(23,""),
newDataWrap(-30,""),newDataWrap(-49,""),
newDataWrap(21,""),newDataWrap(30,"*"),
newDataWrap(30,"")};
System.out.println("排序之前：\n"+java.util.Arrays.toString(data));
binaryInsertSort(data);
System.out.println("排序之后：\n"+java.util.Arrays.toString(data));
}
}
结果：
排序之前： [9,-16,21*,23,-30,-49,21,30*,30] 开始排序 [-16,9,21*,23,-30,-49,21,30*,30] [-16,9,21*,23,-30,-49,21,30*,30] [-16,9,21*,23,-30,-49,21,30*,30] [-30,-16,9,21*,23,-49,21,30*,30] [-49,-30,-16,9,21*,23,21,30*,30] [-49,-30,-16,9,21,21*,23,30*,30] [-49,-30,-16,9,21,21*,23,30*,30] [-49,-30,-16,9,21,21*,23,30,30*] 排序之后： [-49,-30,-16,9,21,21*,23,30,30*]
代码：
packageinterview;
/**
*@authorAdministrator
*冒泡排序
*/
publicclassBubbleSort{
publicstaticvoidbubbleSort(DataWrap[]data){
System.out.println("开始排序");
intarrayLength=data.length;
for(inti=0;i0){
DataWraptemp=data[j+1];
data[j+1]=data[j];
data[j]=temp;
flag=true;
}
}
System.out.println(java.util.Arrays.toString(data));
if(!flag)
break;
}
}
publicstaticvoidmain(String[]args){
DataWrap[]data={newDataWrap(9,""),newDataWrap(-16,""),
newDataWrap(21,"*"),newDataWrap(23,""),
newDataWrap(-30,""),newDataWrap(-49,""),
newDataWrap(21,""),newDataWrap(30,"*"),
newDataWrap(30,"")};
System.out.println("排序之前：\n"+java.util.Arrays.toString(data));
bubbleSort(data);
System.out.println("排序之后：\n"+java.util.Arrays.toString(data));
}
}
运行结果：
排序之前： [9,-16,21*,23,-30,-49,21,30*,30] 开始排序 [-16,9,21*,-30,-49,21,23,30*,30] [-16,9,-30,-49,21*,21,23,30*,30] [-16,-30,-49,9,21*,21,23,30*,30] [-30,-49,-16,9,21*,21,23,30*,30] [-49,-30,-16,9,21*,21,23,30*,30] [-49,-30,-16,9,21*,21,23,30*,30] 排序之后： [-49,-30,-16,9,21*,21,23,30*,30]
算法的时间效率：时间效率极高，只需经过两轮遍历即可算法的空间效率：空间开销较大，需要两个数组来完成，算
法的稳定性：稳定
代码：
packageinterview;
importjava.util.Arrays;
/**
*@authorAdministrator
*桶式排序
*/
publicclassBucketSort{
publicstaticvoidbucketSort(DataWrap[]data,intmin,intmax){
System.out.println("开始排序");
intarrayLength=data.length;
DataWrap[]temp=newDataWrap[arrayLength];
int[]buckets=newint[max-min];
for(inti=0;i=0;k--){
data[--buckets[temp[k].data-min]]=temp[k];
}
}
publicstaticvoidmain(String[]args){
DataWrap[]data={newDataWrap(9,""),newDataWrap(5,""),
newDataWrap(-1,""),newDataWrap(8,""),
newDataWrap(5,"*"),newDataWrap(7,""),
newDataWrap(3,""),newDataWrap(-3,""),
newDataWrap(1,""),newDataWrap(3,"*")};
System.out.println("排序之前：\n"+java.util.Arrays.toString(data));
bucketSort(data,-3,10);
System.out.println("排序之后：\n"+java.util.Arrays.toString(data));
}
}
结果
排序之前： [9,5,-1,8,5*,7,3,-3,1,3*] 开始排序 [1,0,1,0,1,0,2,0,2,0,1,1,1] [1,1,2,2,3,3,5,5,7,7,8,9,10] 排序之后： [-3,-1,1,3,3*,5,5*,7,8,9]
代码：
packageinterview;
/**
*@authorAdministrator
*堆排序
*/
publicclassHeapSort{
publicstaticvoidheapSort(DataWrap[]data){
System.out.println("开始排序");
intarrayLength=data.length;
//循环建堆
for(inti=0;i=0;i--){
//k保存当前正在判断的节点
intk=i;
//如果当前k节点的子节点存在
while(k*2+1<=lastIndex){
//k节点的左子节点的索引
intbiggerIndex=2*k+1;
//如果biggerIndex小于lastIndex，即biggerIndex+1
//代表k节点的右子节点存在
if(biggerIndex
结果：
排序之前：
[9,-16,21*,23,-30,-49,21,30*,30]
开始排序
[-16,30,21*,23,-30,-49,21,9,30*]
[-16,23,21*,9,-30,-49,21,30,30*]
[21,9,21*,-16,-30,-49,23,30,30*]
[-49,9,21*,-16,-30,21,23,30,30*]
[-30,9,-49,-16,21*,21,23,30,30*]
[-30,-16,-49,9,21*,21,23,30,30*]
[-49,-30,-16,9,21*,21,23,30,30*]
[-49,-30,-16,9,21*,21,23,30,30*]
排序之后：
[-49,-30,-16,9,21*,21,23,30,30*]
直接插入排序
packageinterview;
publicclassInsertSort{
publicstaticvoidinsertSort(DataWrap[]data){
System.out.println("开始排序");
intarrayLength=data.length;
for(inti=1;i=0&&data[j].compareTo(temp)>0;j--){
data[j+1]=data[j];
}
data[j+1]=temp;
}
System.out.println(java.util.Arrays.toString(data));
}
}
publicstaticvoidmain(String[]args){
DataWrap[]data={newDataWrap(9,""),newDataWrap(-16,""),
newDataWrap(21,"*"),newDataWrap(23,""),
newDataWrap(-30,""),newDataWrap(-49,""),
newDataWrap(21,""),newDataWrap(30,"*"),
newDataWrap(30,"")};
System.out.println("排序之前：\n"+java.util.Arrays.toString(data));
insertSort(data);
System.out.println("排序之后：\n"+java.util.Arrays.toString(data));
}
}
结果
排序之前：
[9,-16,21*,23,-30,-49,21,30*,30]
开始排序
[-16,9,21*,23,-30,-49,21,30*,30]
[-16,9,21*,23,-30,-49,21,30*,30]
[-16,9,21*,23,-30,-49,21,30*,30]
[-30,-16,9,21*,23,-49,21,30*,30]
[-49,-30,-16,9,21*,23,21,30*,30]
[-49,-30,-16,9,21*,21,23,30*,30]
[-49,-30,-16,9,21*,21,23,30*,30]
[-49,-30,-16,9,21*,21,23,30*,30]
排序之后：
[-49,-30,-16,9,21*,21,23,30*,30]
归并排序
算法的时间效率：归并算法需要递归地进行分解、合并，每进行一趟归并排序，需要merge()方法一次，每次执行
merge()需要比较n次，较差，需要一个与原始序列同样大小的辅助序列。算法的稳定性：稳定
代码：
packageinterview;
/**
*@authorAdministrator
*归并排序
*/
publicclassMergeSort{
publicstaticvoidmergeSort(DataWrap[]data){
//归并排序
sort(data,0,data.length-1);
}
//将索引从left到right范围的数组元素进行归并排序
privatestaticvoidsort(DataWrap[]data,intleft,intright){
if(left
结果：
排序之前：
[9,-16,21*,23,-30,-49,21,30*,30]
排序之后：
[-49,-30,-16,9,21*,21,23,30*,30]
基数排序
基数排序已经不再是一种常规的排序方法，它更多地像是一种排序方法的应用，基数排序必须依赖于另外的排序方法。
基数排序的总体思路就是将待排数据拆分成多个关键字进行排序，也就是说，基数排序的实质是多关键字排序。
多关键字排序的思路是将待排数据里的排序关键字拆分成多个排序关键字：第1个子关键字、第2个子关键字、第3个子
关键字。。。然后，根据子关键字对待排数据进行排序。在进行多关键字排序时有两种解决方案：
最高位优先法MSD
最低位优先法LSD
比较MSD法和LSD法，一般来讲，LSD法要比MSD法来得简单，因为LSD法是从头到尾进行若干次分配和收集，执行
的次数取决于构成关键字值的成分为多少；而MSD法则要处理各序列与子序列的独立排序问题，就可能复杂一些。
代码：
packageinterview;
importjava.util.Arrays;
/**
*@authorAdministrator
*基数排序
*/
publicclassMultiKeyRadixSort{
publicstaticvoidradixSort(int[]data,intradix,intd){
System.out.println("开始排序：");
intarrayLength=data.length;
int[]temp=newint[arrayLength];
int[]buckets=newint[radix];
for(inti=0,rate=1;i=0;m--){
intsubKey=(temp[m]/rate)%radix;
data[--buckets[subKey]]=temp[m];
}
System.out.println("对"+rate+"位上子关键字排序："
+java.util.Arrays.toString(data));
rate*=radix;
}
}
publicstaticvoidmain(String[]args){
int[]data={1100,192,221,12,13};
System.out.println("排序之前：\n"+java.util.Arrays.toString(data));
radixSort(data,10,4);
System.out.println("排序之后：\n"+java.util.Arrays.toString(data));
}
}
结果
排序之前：
[1100,192,221,12,13]
开始排序：
对1位上子关键字排序：[1100,221,192,12,13]
对10位上子关键字排序：[1100,12,13,221,192]
对100位上子关键字排序：[12,13,1100,192,221]
对1000位上子关键字排序：[12,13,192,221,1100]
排序之后：
[12,13,192,221,1100]
快速排序
代码：
packageinterview;
/**
*@authorAdministrator
*快速排序
*/
publicclassQuickSort{
privatestaticvoidswap(DataWrap[]data,inti,intj){
DataWraptemp=data[i];
data[i]=data[j];
data[j]=temp;
}
privatestaticvoidsubSort(DataWrap[]data,intstart,intend){
if(startstart&&data[--j].compareTo(base)>=0)
;
if(i
结果
排序之前：
[9,-16,21*,23,-30,-49,21,30*,30]
排序之后：
[-49,-30,-16,9,21,21*,23,30*,30]
直接选择排序
代码：
packageinterview;
/**
*@authorAdministrator
*直接选择排序
*/
publicclassSelectSort{
publicstaticvoidselectSort(DataWrap[]data){
System.out.println("开始排序");
intarrayLength=data.length;
for(inti=0;i0){
DataWraptemp=data[i];
data[i]=data[j];
data[j]=temp;
}
}
System.out.println(java.util.Arrays.toString(data));
}
}
publicstaticvoidmain(String[]args){
DataWrap[]data={newDataWrap(9,""),newDataWrap(-16,""),
newDataWrap(21,"*"),newDataWrap(23,""),
newDataWrap(-30,""),newDataWrap(-49,""),
newDataWrap(21,""),newDataWrap(30,"*"),
newDataWrap(30,"")};
System.out.println("排序之前：\n"+java.util.Arrays.toString(data));
selectSort(data);
System.out.println("排序之后：\n"+java.util.Arrays.toString(data));
}
}
排序之前：
[9,-16,21*,23,-30,-49,21,30*,30]
开始排序
[-49,9,21*,23,-16,-30,21,30*,30]
[-49,-30,21*,23,9,-16,21,30*,30]
[-49,-30,-16,23,21*,9,21,30*,30]
[-49,-30,-16,9,23,21*,21,30*,30]
[-49,-30,-16,9,21*,23,21,30*,30]
[-49,-30,-16,9,21*,21,23,30*,30]
[-49,-30,-16,9,21*,21,23,30*,30]
[-49,-30,-16,9,21*,21,23,30*,30]
排序之后：
[-49,-30,-16,9,21*,21,23,30*,30]
希尔排序
代码：
packageinterview;
/**
*@authorAdministrator
*Shell排序
*/
publicclassShellSort{
publicstaticvoidShellSort(DataWrap[]data){
System.out.println("开始排序");
intarrayLength=data.length;
inth=1;
/**
*将数组分割成若干个子序列
*/
while(h<=arrayLength/3){
h=h*3+1;
System.out.println("h的结果："+h);
}
while(h>0){
System.out.println("===h的值："+h+"===");
/**
*将分成的若干子序列进行直接插入排序
*/
for(inti=h;i=0&&data[j].compareTo(temp)>0;j-=h){
data[j+h]=data[j];
}
data[j+h]=temp;
}
System.out.println(java.util.Arrays.toString(data));
}
h=(h-1)/3;
}
}
publicstaticvoidmain(String[]args){
DataWrap[]data={
newDataWrap(9,""),newDataWrap(-16,""),
newDataWrap(21,"*"),newDataWrap(23,""),
newDataWrap(-30,""),newDataWrap(-49,""),
newDataWrap(21,""),newDataWrap(30,"*"),
newDataWrap(30,"")};
System.out.println("排序之前：\n"+java.util.Arrays.toString(data));
ShellSort(data);
System.out.println("排序之后：\n"+java.util.Arrays.toString(data));
}
}
结果：
排序之前：
[9,-16,21*,23,-30,-49,21,30*,30]
开始排序
h的结果：4
===h的值：4===
[-30,-16,21*,23,9,-49,21,30*,30]
[-30,-49,21*,23,9,-16,21,30*,30]
[-30,-49,21*,23,9,-16,21,30*,30]
[-30,-49,21*,23,9,-16,21,30*,30]
[-30,-49,21*,23,9,-16,21,30*,30]
===h的值：1===
[-49,-30,21*,23,9,-16,21,30*,30]
[-49,-30,21*,23,9,-16,21,30*,30]
[-49,-30,21*,23,9,-16,21,30*,30]
[-49,-30,9,21*,23,-16,21,30*,30]
[-49,-30,-16,9,21*,23,21,30*,30]
[-49,-30,-16,9,21*,21,23,30*,30]
[-49,-30,-16,9,21*,21,23,30*,30]
[-49,-30,-16,9,21*,21,23,30*,30]
排序之后：
[-49,-30,-16,9,21*,21,23,30*,30]
所需要的工具类：
packageinterview;
publicclassDataWrapimplementsComparable{
intdata;
Stringflag;
publicDataWrap(intdata,Stringflag){
this.data=data;
this.flag=flag;
}
publicStringtoString(){
returndata+flag;
}
@Override
publicintcompareTo(DataWrapdw){
returnthis.data>dw.data?
1:(this.data==dw.data?0:-1);
}
}
以上代码亲测可用，供大家参考。
关于java实现的各种排序算法代码示例的内容，就到这里，希望对大家有所帮助。感兴趣的朋友可以继续参阅本站：Java蒙特卡洛算法求圆周率近似值实例详解、Java编程实现递增排序链表的合并、Java编程ssh整合常见错误解析等，有什么问题可以随时留言，小编会及时回复大家的。这里推荐本站几本关于Java的书籍，免费下载，供广大编程爱好及工作者参考。
Java经典实例(第三版)完整版([美]达尔文)中文pdf扫描版
https://www.nhooo.com/books/577859.html
数据挖掘：实用机器学习技术及Java实现（英文第2版）高清PDF
www.nhooo.com/books/577815.html
Java初级开发工程师面试题汇总.PDF
https://www.nhooo.com/books/576989.html
希望大家能够喜欢。