欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

java实现常用的八种内排序方法

程序员文章站 2022-05-24 15:07:19
...

       虽然以前写过两篇关于内排序的博客,但时间一长这算法也就容易忘记了,所以最近又整理了一次,将八种排序方法一一实现下,它们分别是:

直接插入排序 希尔排序
冒泡排序 快速排序
直接选择排序 堆排序
归并排序 最低位优先的基数排序

      前面七种排序我用的数据结构是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) 稳定