Flask接口签名sign原理与实例代码浅析
192
2023-05-22
Java 7大常见排序方法实例详解
直接插入排序
import java.util.HashMap;
public class InsertSort {
private static int contrastCount = 0;//对比次数
private static int swapCount = 0;//交换次数
public static void main(String[] args) {
System.out.println("直接插入排序:\n 假设前面的序列都已经排序好了,把后面未排序的数往已排好序的序列内插入,时间复杂度O(n^2),空间复杂度O(1),稳定排序");
HashMap
init(hashMap);//初始化
System.out.println("初始序列为:");
print(hashMap, 0);//打印
insert(hashMap);//排序
}
/**
* 初始化函数
* @param hashMap
*/
private static void init(HashMap
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);
}
/**
* 进行插入排序
* @param hashMap 待排序的表
*/
private static void insert(HashMap
System.out.println("开始插入排序:");
int i,j;
//排序开始时间
long start = System.currentTimeMillis();
for(i=2; i
冒泡排序
import java.util.HashMap;
/**
* 冒泡排序
* @author HHF
* 2014年3月19日
*/
public class BubbleSort {
private static int contrastCount = 0;//对比次数
private static int swapCount = 0;//交换次数
public static void main(String[] args) {
System.out.println("冒泡排序:\n 第一轮使最大值沉淀到最底下,采用从头开始的两两比较的办法,如果i大于i++则交换,下一次有从第一个开始循环,比较次数减一,然后依次重复即可,"
+ "\n 如果一次比较为发生任何交换,则可提前终止,时间复杂度O(n^2),空间复杂度O(1),稳定排序");
HashMap
init(hashMap);//初始化
System.out.println("初始序列为:");
print(hashMap, 0);//打印
bubble(hashMap);//排序
}
/**
* 初始化函数
* @param hashMap
*/
private static void init(HashMap
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);
}
/**
* 进行冒泡排序
* @param hashMap 待排序的表
*/
private static void bubble(HashMap
System.out.println("开始冒泡排序:");
//排序开始时间
long start = System.currentTimeMillis();
boolean swap = false;//是否发生交换
int count = 1;//只为了计数
for(int i=1; i
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;
}
//排序结束时间
long end = 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)+"毫秒");
}
/**
* 打印已排序好的元素
* @param hashMap 已排序的表
* @param j 第j趟排序
*/
private static void print(HashMap
if(j != 0)
System.out.print("第 "+j+" 趟:\t");
for(int i=1; i
快速排序
import java.util.HashMap;
public class QuickSort {
private static int contrastCount = 0;//对比次数
private static int swapCount = 0;//交换次数
public static void main(String[] args) {
System.out.println("快速排序:\n 任取一个数作为分界线,比它小的放到左边,比它大的放在其右边,然后分别对左右进行递归,时间复杂度O(nLgn),空间复杂度O(n),不稳定排序");
HashMap
init(hashMap);//初始化
System.out.println("初始序列为:");
print(hashMap, 0, 0);//打印
System.out.println("开始快速排序:");
//排序开始时间
long start = System.currentTimeMillis();
quick(hashMap, 1, hashMap.size()-1);//排序
//排序结束时间
long end = 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("(注:此输出序列为代码执行过程的序列, 即先左边递归 再 右边递归, 而教科书上的递归序列往往是左右同时进行的结果,特此说明)");
}
/**
* 初始化函数
* @param hashMap
*/
private static void init(HashMap
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);
}
/**
* 进行快速排序
* @param hashMap 待排序的表
* @param low
* @param high
*/
static int count = 1;
private static void quick(HashMap
if(low
hashMap.put(0, hashMap.get(low));//选择一个分界值 此时第low位元素内的值已经无所谓被覆盖了
swapCount++;//发生一次交换
while(low
low++;
contrastCount++;//发生一次对比
}
if(low
if(j != 0)
System.out.print("第 "+j+" 趟:(分界线为"+k+")\t");
for(int i=1; i
直接选择排序
import java.util.HashMap;
public class SelectionSort {
private static int contrastCount = 0;//对比次数
private static int swapCount = 0;//交换次数
public static void main(String[] args) {
System.out.println("选择排序:\n 每次选择最小的,然后与对应的位置处元素交换,时间复杂度O(n^2),空间复杂度O(1),不稳定排序");
HashMap
init(hashMap);//初始化
System.out.println("初始序列为:");
print(hashMap, 0, 0);//打印
select(hashMap);//排序
}
/**
* 初始化函数
* @param hashMap
*/
private static void init(HashMap
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);
}
/**
* 进行选择排序
* @param hashMap 待排序的表
*/
private static void select(HashMap
System.out.println("开始选择排序:");
//排序开始时间
long start = System.currentTimeMillis();
int count = 1;//只为统计执行次数
for(int i=hashMap.size()-1; i>1; i--){//需要循环查询的次数 最后一个元素不用考虑
int k = i;//记录本次查找序列最大值的下标 初始为该数应该要放的位置
for(int j=1; j
堆排序
import java.util.HashMap;
public class HeapSort {
private static int contrastCount = 0;//对比次数
private static int swapCount = 0;//交换次数
private static int printCount = 1;//执行打印次数
public static void main(String[] args) {
System.out.println("堆排序:\n 首先建立一个堆(方法是首先把序列排成二叉树,然后从下往上,从右往左使得每一个小子树中的父节点大于子节点,然后从上往下,从左往右记录堆入序列),"
+ "\n 然后把堆的根节点和最底下 的孩子节点交换,整理堆,再重复交换,整理,时间复杂度O(nlgn),空间复杂度O(1),不稳定排序");
HashMap
init(hashMap);//初始化
System.out.println("初始序列为:");
print(hashMap, 0);//打印
heap(hashMap);//排序
}
/**
* 初始化函数
* @param hashMap
*/
private static void init(HashMap
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);
}
/**
* 进行堆排序
* @param hashMap 待排序的表
*/
private static void heap(HashMap
System.out.println("开始建堆:");
//排序开始时间87
long start = System.currentTimeMillis();
for(int i=(hashMap.size()-1)/2; i>=1; i--){//开始建堆
sift(hashMap, i, hashMap.size()-1);//把所有的节点调好位置即可以
}
System.out.println("建堆成功");
for(int j=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++;//发生一次交换
}
//排序结束时间
long end = 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位的元素移动到合适位置 与其子孩子的最大值比较 如果有发生交换 则继续往下比较
* @param hashMap
* @param i 待移动的数下标
* @param n 表示要查找的范围 从1到n个
*/
private static void sift(HashMap
int j = 2*i;//j为i的左孩子
hashMap.put(0, hashMap.get(i));//当前被待排序的数
while(j<=n){//如果有左孩子的
if(hashMap.containsKey(j+1) && hashMap.get(j)
if(j != 0)
System.out.print("第 "+j+" 趟:\t");
for(int i=1; i
归并排序
import java.util.HashMap;
public class MergeSort {
private static int contrastCount = 0;//对比次数
private static int swapCount = 0;//交换次数
private static int printCount = 1;//只为统计执行次数
public static void main(String[] args) {
System.out.println("归并尔排序:\n 先将数据分为n组,然后没两组开始合并,相邻两个合并为一个新的有序队列,重复合并直到整个队列有序,时间复杂度O(nlgn),空间复杂度O(n),稳定排序");
HashMap
HashMap
hashMapNew.put(0, null);//第一位置空
init(hashMap);//初始化
System.out.println("初始序列为:");
print(hashMap, 0);//打印
System.out.println("开始归并尔排序:");
//排序开始时间
long start = System.currentTimeMillis();
merge(hashMap, hashMapNew, 1, hashMap.size()-1);//排序
//排序结束时间
long end = 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("(注:此输出序列为代码执行过程的序列, 即先左边递归 再 右边递归, 而教科书上的递归序列往往是左右同时进行的结果,特此说明)");
}
/**
* 初始化函数
* @param hashMap
*/
private static void init(HashMap
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);
}
/**
* 进行归并尔排序
* @payXQXnNram hashMap 待排序的表
* @param hashMapNew 已排序的表
*/
private static void merge(HashMap
if(low == high){
hashMapNew.put(low, hashMap.get(low));
swapCount++;//发生一次交换
}else{
int meddle = (int)((low+high)/2);//将这一序列数均分的中间值
merge(hashMap, hashMapNew, low, meddle);//继续对左边的序列递归
merge(hashMap, hashMapNew, meddle+1, high);//对右边的序列递归
mergeSort(hashMap, hashMapNew, low, meddle, high);//把相邻的序列组合起来
for(int i=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】
* @param hashMap 待排序的表
* @param hashMapNew 已排序的表
* @param low 低位
* @param meddle 中位
* @param high 高位
*/
private static void mergeSort(HashMap
int k = low;
int j = meddle+1;
while(low<=meddle && j<=high){//两个序列组合成一个序列 从小到达的顺序
if(hashMap.get(low) < hashMap.get(j)){
hashMapNew.put(k++, hashMap.get(low++));//放入合适的位置
}else{
hashMapNew.put(k++, hashMap.get(j++));//放入合适的位置
}
contrastCount++;//发生一次对比
swapCount++;//发生一次交换
}
//如果有一方多出来了 则直接赋值
while(low<=meddle){
hashMapNew.put(k++, hashMap.get(low++));//放入合适的位置
swapCount++;//发生一次交换
}
while(j<=high){
hashMapNew.put(k++, hashMap.get(j++));//放入合适的位置
swapCount++;//发生一次交换
}
print(hashMapNew, printCount++);
}
/**
* 打印已排序好的元素
* @param hashMap 已排序的表
* @param j 第j趟排序
*/
private static void print(HashMap
if(j != 0)
System.out.print("第 "+j+" 趟:\t");
for(int i=1; i
最低位优先基数排序
/**
* 最低位优先基数排序
* @author HHF
*
*/
public class LSDSort {
private static int contrastCount = 0;//对比次数
private static int swapCount = 0;//交换次数
private static int printCount = 1;//只为统计执行次数
public static void main(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);
}
public static void LSD(int[] number, int d) {// d表示最大的数有多少位
int k = 0;//number的小标
int n = 1;//当比较十位的时候 n=10 比较百位的时候 n=100 用来吧高位降低方便求余数
int m = 1;//正在比较number中数据的倒数第几位
int[][] temp = new int[10][number.length];// 数组的第一维表示可能的余数0-9 二维依次记录该余数相同的数
int[] order = new int[10];// 数组orderp[i]用来表示该位的余数是i的数的个数
//排序开始时间
long start = System.currentTimeMillis();
while (m <= d) {//d=5则比较五次
for (int i = 0; i < number.length; i++) {//把number中的数按余数插入到temp中去
int lsd = ((number[i] / n) % 10);//求得该数的余数
temp[lsd][order[lsd]] = number[i];//保存到相应的地方
order[lsd]++;//该余数有几个
swapCount++;//发生一次交换
}
for (int i = 0; i < 10; i++) {//将temp中的数据按顺序提取出来
if (order[i] != 0)//如果该余数没有数据则不需要考虑
for (int j = 0; j < order[i]; j++) {//有给余数的数一共有多少个
number[k] = temp[i][j];//一一赋值
k++;
swapCount++;//发生一次交换
}
order[i] = 0;//置零,以便下一次使用
}
n *= 10;//进制+1 往前走
k = 0;//从头开始
m++;//进制+1
print(number, printCount++);
}
//排序结束时间
long end = System.currentTimeMillis();
System.out.println("结果为:");
print(number, 0);//输出排序结束的序列
System.out.print("一共发生了 "+contrastCount+" 次对比\t");
System.out.print("一共发生了 "+swapCount+" 次交换\t");
System.out.println("执行时间为"+(end-start)+"毫秒");
}
/**
* 打印已排序好的元素
* @param data 已排序的表
* @param j 第j趟排序
*/
private static void print(int[] data, int j){
if(j != 0)
System.out.print("第 "+j+" 趟:\t");
for (yXQXnNint i = 0; i < data.length; i++) {
System.out.print(data[i] + " ");
}
System.out.println();
}
}
本篇文章希望能帮助到您
版权声明:本文内容由网络用户投稿,版权归原作者所有,本站不拥有其著作权,亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容,请联系我们jiasou666@gmail.com 处理,核实后本网站将在24小时内删除侵权内容。
发表评论
暂时没有评论,来抢沙发吧~