虽然以前写过两篇关于内排序的博客,但时间一长这算法也就容易忘记了,所以最近又整理了一次,将八种排序方法一一实现下,它们分别是:
直接插入排序 | 希尔排序 |
冒泡排序 | 快速排序 |
直接选择排序 | 堆排序 |
归并排序 | 最低位优先的基数排序 |
前面七种排序我用的数据结构是hashMap,其储存方式为<key,value>的键值对形式,我选的则是<Integer,Integer>(读者也可以使用数组类型保存数据,正如我前两篇博客那样),值得一提的是哈希表中的0号位全是来用作交换数据的中间值(即hashMap.put(0, null);//第一位置空),如对HashMap不熟悉的读者可以参考相关API,程序中会使用到的方法也只有hashPut.put(key, value)、hashMap.get(key)和hashMap.clear()而已。算法的思想我在这里就不一一详细介绍了,原因是下面的代码中有更为详尽的解释,我就不多此一举了。
——————————————————直接插入排序——————————————————————
package com.sorting; import java.util.HashMap; /** * 直接插入排序 * @author HHF * 2014年3月19日 */ 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<Integer,Integer> hashMap = new HashMap<Integer,Integer>(); init(hashMap);//初始化 System.out.println("初始序列为:"); print(hashMap, 0);//打印 insert(hashMap);//排序 } /** * 初始化函数 * @param hashMap */ private static void init(HashMap<Integer, Integer> 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<Integer, Integer> hashMap){ System.out.println("开始插入排序:"); int i,j; //排序开始时间 long start = System.currentTimeMillis(); for(i=2; i<hashMap.size(); i++){//从第二个开始排序,知道最后一个结束 hashMap.put(0, hashMap.get(i));//储存待排序的数,以便前面的书好向后交换位置 swapCount++;//发生一次交换 j = i-1;//指向有序列 while(hashMap.get(0) < hashMap.get(j)){//当发现有比待排序书大的时候 该数后移一位 hashMap.put(j+1, hashMap.get(j)); j--;//继续向前寻找合适的位置 swapCount++;//发生一次交换 contrastCount++;//发生一次对比 } contrastCount++;//跳出while循环还有一次对比 hashMap.put(j+1, hashMap.get(0));//放入合适的位置 swapCount++;//发生一次交换 /*比如说 我发现从第5号元素开始前面的数都比待排序值小 则j=5,且第6号元素位为合适的位置且为空 所以有j++ */ print(hashMap, i-1);//输出每趟的序列 } //排序结束时间 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<Integer, Integer> hashMap, int j){ if(j != 0) System.out.print("第 "+j+" 趟:\t"); for(int i=1; i<hashMap.size(); i++){//从第一个一直输出到最后一个 System.out.print(hashMap.get(i)+"\t"); } System.out.println(); } }
——————————————————希尔排序————————————————————————
package com.sorting; import java.util.HashMap; /** * 希尔排序 * @author HHF * 2014年3月19日 */ public class HillSort { private static int contrastCount = 0;//对比次数 private static int swapCount = 0;//交换次数 public static void main(String[] args) { System.out.println("希尔排序:\n 分间隔的直接插入排序,假定一个增量d,把全部n个记录分成d组,各组内直接插入排序;再取d1<d,重复分组排序,直到d=1,时间复杂度O(n^1.3),空间复杂度O(1),不稳定排序"); HashMap<Integer,Integer> hashMap = new HashMap<Integer,Integer>(); init(hashMap);//初始化 System.out.println("初始序列为:"); print(hashMap, 0, 0);//打印 hill(hashMap);//排序 } /** * 初始化函数 * @param hashMap */ private static void init(HashMap<Integer, Integer> 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 hill(HashMap<Integer, Integer> hashMap){ System.out.println("开始希尔排序:"); //排序开始时间 long start = System.currentTimeMillis(); int d = hashMap.size()-1;//初始化增量d int count = 1;//只为统计执行次数 while(true){ d = d / 2;//增量每次对半减 for(int x=1;x<=d;x++){//一共有d组 x表示每一组的一个数的下表 for(int i=x+d; i<hashMap.size(); i=i+d){//开始直接插入排序 每组内的数下标间隔d i表示这一组数的下标 hashMap.put(0, hashMap.get(i));//当前被待排序的书 swapCount++;//发生一次交换 int j = 0;//i之前的同一组数的下标 for(j=i-d; j>=0&&(hashMap.get(j)>hashMap.get(0)); j=j-d){//寻找i的当前合适位置 从i-d开始往前找 //只有当被查下标有效 且 被查值比待排序值大时才应该发生交换 hashMap.put(j+d, hashMap.get(j)); contrastCount++;//发生一次对比 swapCount++;//发生一次交换 } contrastCount++;//跳出for循环还有一次对比 hashMap.put(j+d, hashMap.get(0));//放入合适的位置 swapCount++;//发生一次交换 //一趟直接插入排序结束 } } print(hashMap, count++, d); if(d == 1){ break; } } //排序结束时间 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)+"毫秒"); } /** * 打印已排序好的元素 * @param hashMap 已排序的表 * @param j 第j趟排序 * @param d 当前的增量 */ private static void print(HashMap<Integer, Integer> hashMap, int j, int d){ if(j != 0) System.out.print("第 "+j+" 趟:(d="+d+")\t"); for(int i=1; i<hashMap.size(); i++){//从第一个一直输出到最后一个 System.out.print(hashMap.get(i)+"\t"); } System.out.println(); } }
——————————————————冒泡排序————————————————————————
package com.sorting; 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<Integer,Integer> hashMap = new HashMap<Integer,Integer>(); init(hashMap);//初始化 System.out.println("初始序列为:"); print(hashMap, 0);//打印 bubble(hashMap);//排序 } /** * 初始化函数 * @param hashMap */ private static void init(HashMap<Integer, Integer> 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<Integer, Integer> hashMap){ System.out.println("开始冒泡排序:"); //排序开始时间 long start = System.currentTimeMillis(); boolean swap = false;//是否发生交换 int count = 1;//只为了计数 for(int i=1; i<hashMap.size(); i++){ swap = false; for(int j=1; j<hashMap.size()-i; j++){ if(hashMap.get(j)>hashMap.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; } //排序结束时间 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<Integer, Integer> hashMap, int j){ if(j != 0) System.out.print("第 "+j+" 趟:\t"); for(int i=1; i<hashMap.size(); i++){//从第一个一直输出到最后一个 System.out.print(hashMap.get(i)+"\t"); } System.out.println(); } }
——————————————————快速排序————————————————————————
package com.sorting; import java.util.HashMap; /** * 快速排序 * @author HHF * 2014年3月19日 */ 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<Integer,Integer> hashMap = new HashMap<Integer,Integer>(); 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<Integer, Integer> 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<Integer, Integer> hashMap, int low, int high){ if(low<high){//跳出递归的条件 int k = quickOnePass(hashMap, low, high);//开始一趟排序 print(hashMap, count++, hashMap.get(k)); quick(hashMap, low, k-1);//对左边的序列递归排序 quick(hashMap, k+1, high);//对右边的序列递归排序 } } /** * 进行快速排序 * @param hashMap 待排序的表 * @param low * @param high */ private static int quickOnePass(HashMap<Integer, Integer> hashMap, int low, int high){ hashMap.put(0, hashMap.get(low));//选择一个分界值 此时第low位元素内的值已经无所谓被覆盖了 swapCount++;//发生一次交换 while(low<high){//左右两边还有数据为检查时 while(low<high && hashMap.get(0)<hashMap.get(high)){//先开始从右往左走 直到有不对的数据 或者 到头了 high--; contrastCount++;//发生一次对比 } if(low<high){//如果停下来是因为不对的数据 而不是 到头了 hashMap.put(low++, hashMap.get(high)); swapCount++;//发生一次交换 } while(low<high && hashMap.get(0)>hashMap.get(low)){//开始从左往右走 直到有不对的数据 或者 到头了 low++; contrastCount++;//发生一次对比 } if(low<high){//如果停下来是因为不对的数据 而不是 到头了 hashMap.put(high--, hashMap.get(low)); swapCount++;//发生一次交换 } } hashMap.put(low, hashMap.get(0)); swapCount++;//发生一次交换 return low; } /** * 打印已排序好的元素 * @param hashMap 已排序的表 * @param j 第j趟排序 * @param k 第k个元素被选中为分界线 */ private static void print(HashMap<Integer, Integer> hashMap, int j, int k){ if(j != 0) System.out.print("第 "+j+" 趟:(分界线为"+k+")\t"); for(int i=1; i<hashMap.size(); i++){//从第一个一直输出到最后一个 System.out.print(hashMap.get(i)+"\t"); } System.out.println(); } }
——————————————————直接选择排序——————————————————————
package com.sorting; import java.util.HashMap; /** * 选择排序 * @author HHF * 2014年3月19日 */ 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<Integer,Integer> hashMap = new HashMap<Integer,Integer>(); init(hashMap);//初始化 System.out.println("初始序列为:"); print(hashMap, 0, 0);//打印 select(hashMap);//排序 } /** * 初始化函数 * @param hashMap */ private static void init(HashMap<Integer, Integer> 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<Integer, Integer> 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<i; j++){// if(hashMap.get(k)<hashMap.get(j)){ k=j;//记录当前最大的数的下标 contrastCount++;//发生一次对比 } } //此时k中保存了i位置应该放的数的下标 于是发生交换 if(i != k ){ hashMap.put(0, hashMap.get(k)); hashMap.put(k, hashMap.get(i)); hashMap.put(i, hashMap.get(0)); swapCount++;//发生一次交换 swapCount++;//发生一次交换 swapCount++;//发生一次交换 } print(hashMap, count++, i);//输出排序结束的序列 } //排序结束时间 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)+"毫秒"); } /** * 打印已排序好的元素 * @param hashMap 已排序的表 * @param j 第j趟排序 * @param d 被选到的数 */ private static void print(HashMap<Integer, Integer> hashMap, int j, int d){ if(j != 0) System.out.print("第 "+j+" 趟:\t"); for(int i=1; i<hashMap.size(); i++){//从第一个一直输出到最后一个 System.out.print(hashMap.get(i)+"\t"); } System.out.println(); } }
——————————————————堆排序—————————————————————————
package com.sorting; import java.util.HashMap; /** * 堆排序——极大堆 * @author HHF * 2014年3月19日 */ 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<Integer,Integer> hashMap = new HashMap<Integer,Integer>(); init(hashMap);//初始化 System.out.println("初始序列为:"); print(hashMap, 0);//打印 heap(hashMap);//排序 } /** * 初始化函数 * @param hashMap */ private static void init(HashMap<Integer, Integer> 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<Integer, Integer> 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<Integer, Integer> hashMap, int i, int n){ int j = 2*i;//j为i的左孩子 hashMap.put(0, hashMap.get(i));//当前被待排序的数 while(j<=n){//如果有左孩子的 if(hashMap.containsKey(j+1) && hashMap.get(j)<hashMap.get(j+1)){//保证j为最大的孩子 j++; } contrastCount++;//发生一次对比 if(hashMap.get(0)<hashMap.get(j)){//如果是孩子比较大 hashMap.put(i, hashMap.get(j));//交换 i=j;//转移根节点下标 j*=2;//转移孩子节点下标 swapCount++;//发生一次交换 }else//如果是根比较大 break; contrastCount++;//发生一次对比 } hashMap.put(i, hashMap.get(0));//i为当前的合适位置 swapCount++;//发生一次交换 print(hashMap, printCount++);//输出排序结束的序列 } /** * 打印已排序好的元素 * @param hashMap 已排序的表 * @param j 第j趟排序 */ private static void print(HashMap<Integer, Integer> hashMap, int j){ if(j != 0) System.out.print("第 "+j+" 趟:\t"); for(int i=1; i<hashMap.size(); i++){//从第一个一直输出到最后一个 System.out.print(hashMap.get(i)+"\t"); } System.out.println(); } }
——————————————————归并排序————————————————————————
package com.sorting; import java.util.HashMap; /** * 归并排序 * @author HHF * 2014年3月19日 */ 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<Integer,Integer> hashMap = new HashMap<Integer,Integer>();//未排序 HashMap<Integer,Integer> hashMapNew = new HashMap<Integer,Integer>();//已排序 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<Integer, Integer> 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 hashMapNew 已排序的表 */ private static void merge(HashMap<Integer, Integer> hashMap, HashMap<Integer, Integer> hashMapNew, int low, int high){ 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<Integer, Integer> hashMap, HashMap<Integer, Integer> hashMapNew, int low, int meddle, int high){ 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<Integer, Integer> hashMap, int j){ if(j != 0) System.out.print("第 "+j+" 趟:\t"); for(int i=1; i<hashMap.size(); i++){//从第一个一直输出到最后一个 System.out.print(hashMap.get(i)+"\t"); } System.out.println(); } }
——————————————————最低位优先基数排序———————————————————
package com.sorting; /** * 最低位优先基数排序 * @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 (int i = 0; i < data.length; i++) { System.out.print(data[i] + " "); } System.out.println(); } }
——————————————————算法分析————————————————————————
排序方法 | 最好时间 | 平均时间 | 最坏时间 | 辅助空间 | 稳定性 |
直接插入 | O(n) | O(n^2) | O(n^2) | O(1) | 稳定 |
冒泡 | O(n) | O(n^2) | O(n^2) | O(1) | 稳定 |
简单选择 | O(n^2) | O(n^2) | O(n^2) | O(1) | 不稳定 |
希尔 | O(n^1.3) | O(1) | 不稳定 | ||
快速 | O(nLNn) | O(nLNn) | O(n^2) | O(LNn) | 不稳定 |
堆 | O(nLNn) | O(nLNn) | O(nLNn) | O(1) | 不稳定 |
归并 | O(nLNn) | O(nLNn) | O(nLNn) | O(n) | 稳定 |
基数 | O(d(n+rd)) | O(d(n+rd)) | O(d(n+rd)) | O(n+rd) | 稳定 |
相关推荐
AB PLC例程代码项目案例 【备注】 1、该资源内项目代码都经过测试运行成功,功能ok的情况下才上传的,请放心下载使用!有问题请及时沟通交流。 2、适用人群:计算机相关专业(如计科、信息安全、数据科学与大数据技术、人工智能、通信、物联网、自动化、电子信息等)在校学生、专业老师或者企业员工下载使用。 3、用途:项目具有较高的学习借鉴价值,不仅适用于小白学习入门进阶。也可作为毕设项目、课程设计、大作业、初期项目立项演示等。 4、如果基础还行,或热爱钻研,亦可在此项目代码基础上进行修改添加,实现其他不同功能。 欢迎下载!欢迎交流学习!不清楚的可以私信问我!
kolesar_3cd_01_0716
latchman_01_0108
matlab程序代码项目案例 【备注】 1、该资源内项目代码都经过测试运行成功,功能ok的情况下才上传的,请放心下载使用!有问题请及时沟通交流。 2、适用人群:计算机相关专业(如计科、信息安全、数据科学与大数据技术、人工智能、通信、物联网、自动化、电子信息等)在校学生、专业老师或者企业员工下载使用。 3、用途:项目具有较高的学习借鉴价值,不仅适用于小白学习入门进阶。也可作为毕设项目、课程设计、大作业、初期项目立项演示等。 4、如果基础还行,或热爱钻研,亦可在此项目代码基础上进行修改添加,实现其他不同功能。 欢迎下载!欢迎交流学习!不清楚的可以私信问我!
pimpinella_3cd_01_0716
petrilla_01_0308
AB PLC例程代码项目案例 【备注】 1、该资源内项目代码都经过测试运行成功,功能ok的情况下才上传的,请放心下载使用!有问题请及时沟通交流。 2、适用人群:计算机相关专业(如计科、信息安全、数据科学与大数据技术、人工智能、通信、物联网、自动化、电子信息等)在校学生、专业老师或者企业员工下载使用。 3、用途:项目具有较高的学习借鉴价值,不仅适用于小白学习入门进阶。也可作为毕设项目、课程设计、大作业、初期项目立项演示等。 4、如果基础还行,或热爱钻研,亦可在此项目代码基础上进行修改添加,实现其他不同功能。 欢迎下载!欢迎交流学习!不清楚的可以私信问我!
内容概要:本文档由张卓老师讲解,重点探讨DeepSeek的技术革新及强化学习对未来AI发展的重要性。文章回顾了AI的历史与发展阶段,详细解析Transformer架构在AI上半场所起到的作用,深入介绍了MoE混合专家以及MLA低秩注意机制等技术特点如何帮助DeepSeek在AI中场建立优势,并探讨了当前强化学习的挑战和边界。文档不仅提及AlphaGo和小游戏等成功案例来说明强化学习的强大力量,还提出了关于未来人工通用智能(AGI)的展望,特别是如何利用强化学习提升现有LLMs的能力和性能。 适用人群:本资料适宜对深度学习感兴趣的研究人员、开发者以及想要深入了解人工智能最新进展的专业人士。 使用场景及目标:通过了解最新的AI技术和前沿概念,在实际工作中能够运用更先进的工具和技术解决问题。同时为那些寻求职业转型或者学术深造的人提供了宝贵的参考。 其他说明:文中提到了许多具体的例子和技术细节,如DeepSeek的技术特色、RL的理论背景等等,有助于加深读者对于现代AI系统的理解和认识。
有师傅小程序开源版v2.4.14 新增报价短信奉告 优化部分细节
AB PLC例程代码项目案例 【备注】 1、该资源内项目代码都经过测试运行成功,功能ok的情况下才上传的,请放心下载使用!有问题请及时沟通交流。 2、适用人群:计算机相关专业(如计科、信息安全、数据科学与大数据技术、人工智能、通信、物联网、自动化、电子信息等)在校学生、专业老师或者企业员工下载使用。 3、用途:项目具有较高的学习借鉴价值,不仅适用于小白学习入门进阶。也可作为毕设项目、课程设计、大作业、初期项目立项演示等。 4、如果基础还行,或热爱钻研,亦可在此项目代码基础上进行修改添加,实现其他不同功能。 欢迎下载!欢迎交流学习!不清楚的可以私信问我!
商城二级三级分销系统(小程序+后台含源码).zip
li_3ck_01b_0918
nicholl_3cd_01_0516
媒体关注度是一个衡量公众对某个事件、话题或个体关注程度的重要指标。它主要反映了新闻媒体、社交媒体、博客等对于某一事件、话题或个体的报道和讨论程度。 媒体监督的J-F系数(Janis-Fadner系数)是一种用于测量媒体关注度的指标,特别是用于评估媒体对企业、事件或话题的监督力度。J-F系数基于媒体报道的正面和负面内容来计算,从而为公众、研究者或企业提供一个量化工具,以了解媒体对其关注的方向和强度。 本数据含原始数据、参考文献、代码do文件、最终结果。参考文献中JF系数计算公式。 指标 代码、年份、标题出现该公司的新闻总数、内容出现该公司的新闻总数、正面新闻数全部、中性新闻数全部、负面新闻数全部、正面新闻数原创、中性新闻数原创、负面新闻数原创,媒体监督JF系数。
AB PLC例程代码项目案例 【备注】 1、该资源内项目代码都经过测试运行成功,功能ok的情况下才上传的,请放心下载使用!有问题请及时沟通交流。 2、适用人群:计算机相关专业(如计科、信息安全、数据科学与大数据技术、人工智能、通信、物联网、自动化、电子信息等)在校学生、专业老师或者企业员工下载使用。 3、用途:项目具有较高的学习借鉴价值,不仅适用于小白学习入门进阶。也可作为毕设项目、课程设计、大作业、初期项目立项演示等。 4、如果基础还行,或热爱钻研,亦可在此项目代码基础上进行修改添加,实现其他不同功能。 欢迎下载!欢迎交流学习!不清楚的可以私信问我!
AB PLC例程代码项目案例 【备注】 1、该资源内项目代码都经过测试运行成功,功能ok的情况下才上传的,请放心下载使用!有问题请及时沟通交流。 2、适用人群:计算机相关专业(如计科、信息安全、数据科学与大数据技术、人工智能、通信、物联网、自动化、电子信息等)在校学生、专业老师或者企业员工下载使用。 3、用途:项目具有较高的学习借鉴价值,不仅适用于小白学习入门进阶。也可作为毕设项目、课程设计、大作业、初期项目立项演示等。 4、如果基础还行,或热爱钻研,亦可在此项目代码基础上进行修改添加,实现其他不同功能。 欢迎下载!欢迎交流学习!不清楚的可以私信问我!
AB PLC例程代码项目案例 【备注】 1、该资源内项目代码都经过测试运行成功,功能ok的情况下才上传的,请放心下载使用!有问题请及时沟通交流。 2、适用人群:计算机相关专业(如计科、信息安全、数据科学与大数据技术、人工智能、通信、物联网、自动化、电子信息等)在校学生、专业老师或者企业员工下载使用。 3、用途:项目具有较高的学习借鉴价值,不仅适用于小白学习入门进阶。也可作为毕设项目、课程设计、大作业、初期项目立项演示等。 4、如果基础还行,或热爱钻研,亦可在此项目代码基础上进行修改添加,实现其他不同功能。 欢迎下载!欢迎交流学习!不清楚的可以私信问我!
matlab程序代码项目案例 【备注】 1、该资源内项目代码都经过测试运行成功,功能ok的情况下才上传的,请放心下载使用!有问题请及时沟通交流。 2、适用人群:计算机相关专业(如计科、信息安全、数据科学与大数据技术、人工智能、通信、物联网、自动化、电子信息等)在校学生、专业老师或者企业员工下载使用。 3、用途:项目具有较高的学习借鉴价值,不仅适用于小白学习入门进阶。也可作为毕设项目、课程设计、大作业、初期项目立项演示等。 4、如果基础还行,或热爱钻研,亦可在此项目代码基础上进行修改添加,实现其他不同功能。 欢迎下载!欢迎交流学习!不清楚的可以私信问我!
lusted_3cd_02_0716
pepeljugoski_01_0107