虽然以前写过两篇关于内排序的博客，但时间一长这算法也就容易忘记了，所以最近又整理了一次，将八种排序方法一一实现下，它们分别是：
| 直接插入排序 | 希尔排序 |
| 冒泡排序 | 快速排序 |
| 直接选择排序 | 堆排序 |
| 归并排序 | 最低位优先的基数排序 |
前面七种排序我用的数据结构是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) | 稳定 |
相关推荐
### Java 实现几种常见排序方法 #### 泡泡排序（Bubble Sort） 泡泡排序是一种简单的排序算法，它重复地遍历待排序的数列，依次比较相邻的两个元素，如果它们的顺序错误就把它们交换过来。遍历数列的工作是重复...
本篇文章将详细探讨标题为“8种常用排序方法Java类实现”的主题，主要基于描述中的内容，即8种业务中常见的排序方法在Java语言中的实现。 1. **冒泡排序（Bubble Sort）**：冒泡排序是一种简单直观的排序算法，通过...
Java实现六种常用排序 并用多线程进行速度比较（其实意义不大） 含有代码
Java实现归并排序 Java 实现归并排序是一种常用的排序算法，通过分治策略将原始数组分成小组，然后对每个小组进行排序，最后将排序好的小组合并成一个有序数组。下面是 Java 实现归并排序的知识点总结： 基本思想 ...
这六种排序算法可能包括常见的快速排序、归并排序、插入排序、选择排序、冒泡排序以及堆排序。接下来，我们将对每一种排序算法进行详细介绍，并结合Java代码示例进行解析。 1. 插入排序（Insertion Sort） 插入排序...
Java实现中，通常会用递归方法实现，同时需要额外的空间来存储合并过程。 8. 基数排序（Radix Sort） 基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。从最低...
`Algorithm.java`文件可能包含了这些排序算法的Java实现代码，而`常见排序算法的实现与性能比较.doc`文档则可能详细比较了这些算法的性能和适用场景。`readme.txt`文件可能是对整个项目的简要说明，包括如何运行和...
本篇文章将详细讲解标题中提到的六种常见排序算法的Java实现。 1. **冒泡排序**：冒泡排序是最基础的排序算法之一，它通过不断交换相邻的逆序元素来逐渐将较大的元素“浮”到数组的前端。在Java中，冒泡排序的基本...
本篇文章将详细探讨Java中常见的八种排序算法，每一种都有其独特的特性和适用场景。 1. **冒泡排序(Bubble Sort)** 冒泡排序是最基础的排序算法之一，通过不断交换相邻的逆序元素来逐步完成排序。它的时间复杂度为...
根据给定的信息，本文将详细介绍如何使用Java语言来实现几种常见的...以上就是四种常见排序算法的Java实现及其基本思想介绍。通过学习这些排序算法，可以更好地理解排序的基本原理和技术，从而在实际编程中灵活应用。
本文将介绍两种常见的排序算法：直接插入排序和希尔排序，并通过Java代码实现来帮助理解。 1. 直接插入排序（直接插入排序） 直接插入排序是一种简单的排序方法，它的工作原理类似于我们平时手动整理扑克牌。在排序...
虽然树形选择排序和堆排序在这次实现中未涵盖，但理解这四种排序算法的基本原理和Java实现方式对于提升编程技能至关重要。 首先，让我们来看看插入排序。插入排序是一种简单直观的排序算法，它的工作原理类似于人们...
本篇文章将深入探讨八大常见的排序算法，并提供它们在Java语言中的具体实现。这八大排序算法包括冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序以及计数排序。 1. 冒泡排序（Bubble Sort）：...
本文将深入探讨标题"常用排序算法java演示"中涉及的知识点，包括排序算法的原理、Java实现方式以及其在实际应用中的图形演示。 首先，让我们逐一了解几种常见的排序算法： 1. **冒泡排序（Bubble Sort）**：这是一...
在Java实现中，我们通常使用两个嵌套的for循环，外层循环控制待排序的元素，内层循环则用于找到合适的位置将元素插入。例如，给定数组a，我们遍历每个元素，将其与前面已排序的元素进行比较，如果当前元素小于前面的...
以上就是Java中常见排序算法的概述和部分源码实现。实际应用中，根据数据特性、内存限制和性能要求，可以选择合适的排序算法。理解这些排序算法的工作原理和性能特点，有助于我们在编程实践中做出明智的选择。
### Java 实现数据结构常见排序算法及详解 #### 排序算法概述 排序算法是计算机科学中的基础概念之一，主要用于将一系列数据按照特定规则进行排列。根据数据处理方式的不同，排序算法大致分为两大类：比较排序与非...
总结起来，Java实现的插入排序和交换排序为程序员提供了处理各种数据排序问题的工具。了解和掌握这些排序算法不仅有助于提升编程能力，也是解决实际问题的基础，尤其是在大数据处理和性能优化方面。在实际应用中，...
内排序指的是数据在内存中完成的排序过程，这里我们将详细探讨八种常见的内排序算法在Java中的实现，包括它们的工作原理、优缺点以及在实际应用中的考虑因素。 1. **简单选择排序（Simple Selection Sort）**：它是...