Java 7大常见排序方法实例详解

2024-02-25 09:59:03 46

直接插入排序

importjava.util.HashMap;
publicclassInsertSort{
privatestaticintcontrastCount=0;//对比次数
privatestaticintswapCount=0;//交换次数
publicstaticvoidmain(String[]args){
System.out.println("直接插入排序：\n假设前面的序列都已经排序好了，把后面未排序的数往已排好序的序列内插入,时间复杂度O(n^2),空间复杂度O(1)，稳定排序");
HashMaphashMap=newHashMap();
init(hashMap);//初始化
System.out.println("初始序列为：");
print(hashMap,0);//打印
insert(hashMap);//排序
}
/**
*初始化函数
*@paramhashMap
*/
privatestaticvoidinit(HashMaphashMap){
hashMap.put(0,null);//第一位置空
hashMap.put(1,0);
hashMap.put(2,5);
hashMap.put(3,11);
hashMap.put(4,12);
hashMap.put(5,13);
hashMap.put(6,4);
hashMap.put(7,1);
hashMap.put(8,5);
hashMap.put(9,8);
hashMap.put(10,6);
hashMap.put(11,4);
hashMap.put(12,8);
}
/**
*进行插入排序
*@paramhashMap待排序的表
*/
privatestaticvoidinsert(HashMaphashMap){
System.out.println("开始插入排序：");
inti,j;
//排序开始时间
longstart=System.currentTimeMillis();
for(i=2;i

冒泡排序

importjava.util.HashMap;
/**
*冒泡排序
*@authorHHF
*2014年3月19日
*/
publicclassBubbleSort{
privatestaticintcontrastCount=0;//对比次数
privatestaticintswapCount=0;//交换次数
publicstaticvoidmain(String[]args){
System.out.println("冒泡排序：\n第一轮使最大值沉淀到最底下，采用从头开始的两两比较的办法，如果i大于i++则交换，下一次有从第一个开始循环，比较次数减一，然后依次重复即可,"
+"\n如果一次比较为发生任何交换，则可提前终止，时间复杂度O(n^2),空间复杂度O(1)，稳定排序");
HashMaphashMap=newHashMap();
init(hashMap);//初始化
System.out.println("初始序列为：");
print(hashMap,0);//打印
bubble(hashMap);//排序
}
/**
*初始化函数
*@paramhashMap
*/
privatestaticvoidinit(HashMaphashMap){
hashMap.put(0,null);//第一位置空
hashMap.put(1,10);
hashMap.put(2,5);
hashMap.put(3,11);
hashMap.put(4,12);
hashMap.put(5,13);
hashMap.put(6,4);
hashMap.put(7,1);
hashMap.put(8,5);
hashMap.put(9,8);
hashMap.put(10,6);
hashMap.put(11,4);
hashMap.put(12,8);
}
/**
*进行冒泡排序
*@paramhashMap待排序的表
*/
privatestaticvoidbubble(HashMaphashMap){
System.out.println("开始冒泡排序：");
//排序开始时间
longstart=System.currentTimeMillis();
booleanswap=false;//是否发生交换
intcount=1;//只为了计数
for(inti=1;ihashMap.get(j+1)){//需要发生交换j和j+1
hashMap.put(0,hashMap.get(j));
hashMap.put(j,hashMap.get(j+1));
hashMap.put(j+1,hashMap.get(0));
swap=true;
contrastCount++;//发生一次对比
swapCount++;//发生一次交换
swapCount++;//发生一次交换
swapCount++;//发生一次交换
}
contrastCount++;//跳出if还有一次对比
}
print(hashMap,count++);
if(!swap)
break;
}
//排序结束时间
longend=System.currentTimeMillis();
System.out.println("结果为：");
print(hashMap,0);//输出排序结束的序列
hashMap.clear();//清空
System.out.print("一共发生了"+contrastCount+"次对比\t");
System.out.print("一共发生了"+swapCount+"次交换\t");
System.out.println("执行时间为"+(end-start)+"毫秒");
}
/**
*打印已排序好的元素
*@paramhashMap已排序的表
*@paramj第j趟排序
*/
privatestaticvoidprint(HashMaphashMap,intj){
if(j!=0)
System.out.print("第"+j+"趟：\t");
for(inti=1;i

快速排序

importjava.util.HashMap;
publicclassQuickSort{
privatestaticintcontrastCount=0;//对比次数
privatestaticintswapCount=0;//交换次数
publicstaticvoidmain(String[]args){
System.out.println("快速排序：\n任取一个数作为分界线，比它小的放到左边，比它大的放在其右边，然后分别对左右进行递归,时间复杂度O(nLgn),空间复杂度O(n)，不稳定排序");
HashMaphashMap=newHashMap();
init(hashMap);//初始化
System.out.println("初始序列为：");
print(hashMap,0,0);//打印
System.out.println("开始快速排序：");
//排序开始时间
longstart=System.currentTimeMillis();
quick(hashMap,1,hashMap.size()-1);//排序
//排序结束时间
longend=System.currentTimeMillis();
System.out.println("结果为：");
print(hashMap,0,0);//输出排序结束的序列
hashMap.clear();//清空
System.out.print("一共发生了"+contrastCount+"次对比\t");
System.out.print("一共发生了"+swapCount+"次交换\t");
System.out.println("执行时间为"+(end-start)+"毫秒");
System.out.println("(注：此输出序列为代码执行过程的序列，即先左边递归再右边递归，而教科书上的递归序列往往是左右同时进行的结果，特此说明)");
}
/**
*初始化函数
*@paramhashMap
*/
privatestaticvoidinit(HashMaphashMap){
hashMap.put(0,null);//第一位置空
hashMap.put(1,10);
hashMap.put(2,5);
hashMap.put(3,11);
hashMap.put(4,12);
hashMap.put(5,13);
hashMap.put(6,4);
hashMap.put(7,1);
hashMap.put(8,5);
hashMap.put(9,8);
hashMap.put(10,6);
hashMap.put(11,4);
hashMap.put(12,8);
}
/**
*进行快速排序
*@paramhashMap待排序的表
*@paramlow
*@paramhigh
*/
staticintcount=1;
privatestaticvoidquick(HashMaphashMap,intlow,inthigh){
if(lowhashMap,intlow,inthigh){
hashMap.put(0,hashMap.get(low));//选择一个分界值此时第low位元素内的值已经无所谓被覆盖了
swapCount++;//发生一次交换
while(lowhashMap.get(low)){//开始从左往右走直到有不对的数据或者到头了
low++;
contrastCount++;//发生一次对比
}
if(lowhashMap,intj,intk){
if(j!=0)
System.out.print("第"+j+"趟：(分界线为"+k+")\t");
for(inti=1;i

直接选择排序

importjava.util.HashMap;
publicclassSelectionSort{
privatestaticintcontrastCount=0;//对比次数
privatestaticintswapCount=0;//交换次数
publicstaticvoidmain(String[]args){
System.out.println("选择排序：\n每次选择最小的，然后与对应的位置处元素交换,时间复杂度O(n^2),空间复杂度O(1)，不稳定排序");
HashMaphashMap=newHashMap();
init(hashMap);//初始化
System.out.println("初始序列为：");
print(hashMap,0,0);//打印
select(hashMap);//排序
}
/**
*初始化函数
*@paramhashMap
*/
privatestaticvoidinit(HashMaphashMap){
hashMap.put(0,null);//第一位置空
hashMap.put(1,10);
hashMap.put(2,5);
hashMap.put(3,11);
hashMap.put(4,12);
hashMap.put(5,13);
hashMap.put(6,4);
hashMap.put(7,1);
hashMap.put(8,5);
hashMap.put(9,8);
hashMap.put(10,6);
hashMap.put(11,4);
hashMap.put(12,8);
}
/**
*进行选择排序
*@paramhashMap待排序的表
*/
privatestaticvoidselect(HashMaphashMap){
System.out.println("开始选择排序：");
//排序开始时间
longstart=System.currentTimeMillis();
intcount=1;//只为统计执行次数
for(inti=hashMap.size()-1;i>1;i--){//需要循环查询的次数最后一个元素不用考虑
intk=i;//记录本次查找序列最大值的下标初始为该数应该要放的位置
for(intj=1;j

堆排序

importjava.util.HashMap;
publicclassHeapSort{
privatestaticintcontrastCount=0;//对比次数
privatestaticintswapCount=0;//交换次数
privatestaticintprintCount=1;//执行打印次数
publicstaticvoidmain(String[]args){
System.out.println("堆排序：\n首先建立一个堆（方法是首先把序列排成二叉树，然后从下往上，从右往左使得每一个小子树中的父节点大于子节点，然后从上往下，从左往右记录堆入序列）,"
+"\n然后把堆的根节点和最底下的孩子节点交换，整理堆，再重复交换，整理，时间复杂度O(nlgn),空间复杂度O(1)，不稳定排序");
HashMaphashMap=newHashMap();
init(hashMap);//初始化
System.out.println("初始序列为：");
print(hashMap,0);//打印
heap(hashMap);//排序
}
/**
*初始化函数
*@paramhashMap
*/
privatestaticvoidinit(HashMaphashMap){
hashMap.put(0,null);//第一位置空
hashMap.put(1,10);
hashMap.put(2,5);
hashMap.put(3,11);
hashMap.put(4,12);
hashMap.put(5,13);
hashMap.put(6,4);
hashMap.put(7,1);
hashMap.put(8,5);
hashMap.put(9,8);
hashMap.put(10,6);
hashMap.put(11,4);
hashMap.put(12,8);
}
/**
*进行堆排序
*@paramhashMap待排序的表
*/
privatestaticvoidheap(HashMaphashMap){
System.out.println("开始建堆：");
//排序开始时间87
longstart=System.currentTimeMillis();
for(inti=(hashMap.size()-1)/2;i>=1;i--){//开始建堆
sift(hashMap,i,hashMap.size()-1);//把所有的节点调好位置即可以
}
System.out.println("建堆成功");
for(intj=hashMap.size()-1;j>=1;j--){//每次都把第一个元素与最后一个未排序的交换然后再调整第一个节点即可
hashMap.put(0,hashMap.get(1));
hashMap.put(1,hashMap.get(j));
hashMap.put(j,hashMap.get(0));
sift(hashMap,1,j-1);//剩下要排序的数位为j-1
swapCount++;//发生一次交换
swapCount++;//发生一次交换
swapCount++;//发生一次交换
}
//排序结束时间
longend=System.currentTimeMillis();
System.out.println("结果为：");
print(hashMap,0);//输出排序结束的序列
hashMap.clear();//清空
System.out.print("一共发生了"+contrastCount+"次对比\t");
System.out.print("一共发生了"+swapCount+"次交换\t");
System.out.println("执行时间为"+(end-start)+"毫秒");
}
/**
*把第i位的元素移动到合适位置与其子孩子的最大值比较如果有发生交换则继续往下比较
*@paramhashMap
*@parami待移动的数下标
*@paramn表示要查找的范围从1到n个
*/
privatestaticvoidsift(HashMaphashMap,inti,intn){
intj=2*i;//j为i的左孩子
hashMap.put(0,hashMap.get(i));//当前被待排序的数
while(j<=n){//如果有左孩子的
if(hashMap.containsKey(j+1)&&hashMap.get(j)hashMap,intj){
if(j!=0)
System.out.print("第"+j+"趟：\t");
for(inti=1;i

归并排序

importjava.util.HashMap;
publicclassMergeSort{
privatestaticintcontrastCount=0;//对比次数
privatestaticintswapCount=0;//交换次数
privatestaticintprintCount=1;//只为统计执行次数
publicstaticvoidmain(String[]args){
System.out.println("归并尔排序：\n先将数据分为n组，然后没两组开始合并，相邻两个合并为一个新的有序队列，重复合并直到整个队列有序,时间复杂度O(nlgn),空间复杂度O(n)，稳定排序");
HashMaphashMap=newHashMap();//未排序
HashMaphashMapNew=newHashMap();//已排序
hashMapNew.put(0,null);//第一位置空
init(hashMap);//初始化
System.out.println("初始序列为：");
print(hashMap,0);//打印
System.out.println("开始归并尔排序：");
//排序开始时间
longstart=System.currentTimeMillis();
merge(hashMap,hashMapNew,1,hashMap.size()-1);//排序
//排序结束时间
longend=System.currentTimeMillis();
System.out.println("结果为：");
print(hashMapNew,0);//输出排序结束的序列
hashMap.clear();//清空
System.out.print("一共发生了"+contrastCount+"次对比\t");
System.out.print("一共发生了"+swapCount+"次交换\t");
System.out.println("执行时间为"+(end-start)+"毫秒");
System.out.println("(注：此输出序列为代码执行过程的序列，即先左边递归再右边递归，而教科书上的递归序列往往是左右同时进行的结果，特此说明)");
}
/**
*初始化函数
*@paramhashMap
*/
privatestaticvoidinit(HashMaphashMap){
hashMap.put(0,null);//第一位置空
hashMap.put(1,10);
hashMap.put(2,5);
hashMap.put(3,11);
hashMap.put(4,12);
hashMap.put(5,13);
hashMap.put(6,4);
hashMap.put(7,1);
hashMap.put(8,5);
hashMap.put(9,8);
hashMap.put(10,6);
hashMap.put(11,4);
hashMap.put(12,8);
}
/**
*进行归并尔排序
*@paramhashMap待排序的表
*@paramhashMapNew已排序的表
*/
privatestaticvoidmerge(HashMaphashMap,HashMaphashMapNew,intlow,inthigh){
if(low==high){
hashMapNew.put(low,hashMap.get(low));
swapCount++;//发生一次交换
}else{
intmeddle=(int)((low+high)/2);//将这一序列数均分的中间值
merge(hashMap,hashMapNew,low,meddle);//继续对左边的序列递归
merge(hashMap,hashMapNew,meddle+1,high);//对右边的序列递归
mergeSort(hashMap,hashMapNew,low,meddle,high);//把相邻的序列组合起来
for(inti=low;i<=high;i++){//将已经排好序的hashMapNew【low，high】覆盖hashMap【low，high】以便进入下一次的递归归并
hashMap.put(i,hashMapNew.get(i));
swapCount++;//发生一次交换
}
}
}
/**
*进行归并尔排序把【low，meddle】和【meddle+1，high】和并为一个有序的hashMapNew【low,high】
*@paramhashMap待排序的表
*@paramhashMapNew已排序的表
*@paramlow低位
*@parammeddle中位
*@paramhigh高位
*/
privatestaticvoidmergeSort(HashMaphashMap,HashMaphashMapNew,intlow,intmeddle,inthigh){
intk=low;
intj=meddle+1;
while(low<=meddle&&j<=high){//两个序列组合成一个序列从小到达的顺序
if(hashMap.get(low)hashMap,intj){
if(j!=0)
System.out.print("第"+j+"趟：\t");
for(inti=1;i

最低位优先基数排序

/**
*最低位优先基数排序
*@authorHHF
*
*/
publicclassLSDSort{
privatestaticintcontrastCount=0;//对比次数
privatestaticintswapCount=0;//交换次数
privatestaticintprintCount=1;//只为统计执行次数

publicstaticvoidmain(String[]args){
System.out.println("最低位优先基数排序：\n按个位、十位、百位排序，不需要比较，只需要对数求余然后保存到相应下标的二维数组内，然后依次读取，每一进制重复依次,时间复杂度O(d（n+rd）),空间复杂度O(n+rd)，稳定排序");
int[]data={173,22,93,43,55,14,28,65,39,81,33,100};
System.out.println("初始序列为：");
print(data,0);//打印
LSD(data,3);
}
publicstaticvoidLSD(int[]number,intd){//d表示最大的数有多少位
intk=0;//number的小标
intn=1;//当比较十位的时候n=10比较百位的时候n=100用来吧高位降低方便求余数
intm=1;//正在比较number中数据的倒数第几位
int[][]temp=newint[10][number.length];//数组的第一维表示可能的余数0-9二维依次记录该余数相同的数
int[]order=newint[10];//数组orderp[i]用来表示该位的余数是i的数的个数
//排序开始时间
longstart=System.currentTimeMillis();
while(m<=d){//d=5则比较五次
for(inti=0;i

本篇文章希望能帮助到您

Java 7大常见排序方法实例详解

热门推荐

随机推荐