MyException - 我的异常网
当前位置:我的异常网» 编程 » 【code】java兑现十种常见内部排序

【code】java兑现十种常见内部排序

www.MyException.Cn  网友分享于:2013-10-30  浏览:8次
【code】java实现十种常见内部排序

常见的内部排序:

下面介绍这十种常见内部排序(都是从小到大的排序)

直接选择排序

import java.util.*;
//定义一个数据包装类
class DataWrap implements Comparable<DataWrap>
{
	int data;
	String flag;
	public DataWrap(int data, String flag)
	{
		this.data = data;
		this.flag = flag;
	}
	public String toString()
	{
		return data + flag;
	}
	//根据data实例变量来决定两个DataWrap的大小
	public int compareTo(DataWrap dw)
	{
		return this.data > dw.data ? 1 
			: (this.data == dw.data ? 0 : -1);
	}
}
public class SelectSort
{
	public static void selectSort(DataWrap[] data) 
	{
		System.out.println("开始排序");
		int arrayLength = data.length;
		//依次进行n-1趟比较, 第i趟比较将第i大的值选出放在i位置上。
		for (int i = 0; i < arrayLength - 1 ; i++ )
		{
			int minIndex = i ;
			//第i个数据只需和它后面的数据比较
			for (int j = i + 1 ; j < arrayLength ; j++ )
			{				
				//如果第i位置的数据 > j位置的数据, 交换它们
				if (data[i].compareTo(data[j]) > 0)
				{
					DataWrap tmp = data[i];
					data[i] = data[j];
					data[j] = tmp;
				}
			}
			System.out.println(java.util.Arrays.toString(data));
		}
	}
	public static void main(String[] args)
	{
		DataWrap[] data = {
			new DataWrap(21 , ""),
			new DataWrap(30 , ""),
			new DataWrap(49 , ""),
			new DataWrap(30 , "*"),
			new DataWrap(16 , ""),
			new DataWrap(9 , "")
		};
		System.out.println("排序之前:\n"
			+ java.util.Arrays.toString(data));
		selectSort(data);
		System.out.println("排序之后:\n" 
			+ java.util.Arrays.toString(data));
	}
}

 优化后:

import java.util.*;
class DataWrap implements Comparable<DataWrap>
{
	int data;
	String flag;
	public DataWrap(int data, String flag)
	{
		this.data = data;
		this.flag = flag;
	}
	public String toString()
	{
		return data + flag;
	}
	public int compareTo(DataWrap dw)
	{
		return this.data > dw.data ? 1 
			: (this.data == dw.data ? 0 : -1);
	}
}
public class SelectSort2
{
	public static void selectSort(DataWrap[] data) 
	{
		System.out.println("开始排序");
		int arrayLength = data.length;
		//依次进行n-1趟比较, 第i趟比较将第i大的值选出放在i位置上。
		for (int i = 0; i < arrayLength - 1 ; i++ )
		{
			//minIndex永远保留本趟比较中最小值的索引
			int minIndex = i ;
			//第i个数据只需和它后面的数据比较
			for (int j = i + 1 ; j < arrayLength ; j++ )
			{
				//如果第minIndex位置的数据 > j位置的数据
				if (data[minIndex].compareTo(data[j]) > 0)
				{
					//将j的值赋给minIndex
					minIndex = j;
				}
			}
			//每趟比较最多交换一次
			if (minIndex != i)
			{
				DataWrap tmp = data[i];
				data[i] = data[minIndex];
				data[minIndex] = tmp;
			}
			System.out.println(java.util.Arrays.toString(data));
		}
	}
	public static void main(String[] args)
	{
		DataWrap[] data = {
			new DataWrap(21 , ""),
			new DataWrap(30 , ""),
			new DataWrap(49 , ""),
			new DataWrap(30 , "*"),
			new DataWrap(16 , ""),
			new DataWrap(9 , "")
		};
		System.out.println("排序之前:\n"
			+ java.util.Arrays.toString(data));
		selectSort(data);
		System.out.println("排序之后:\n" 
			+ java.util.Arrays.toString(data));
	}
}
//时间复杂度:n的平方
//空间复杂度:1
//稳定性:不稳定

堆排序

建大堆求得从小到大的排序。每次建立大堆把大堆顶与数组最后一个元素交换。

import java.util.*;
//定义一个数据包装类
class DataWrap implements Comparable<DataWrap>
{
	int data;
	String flag;
	public DataWrap(int data, String flag)
	{
		this.data = data;
		this.flag = flag;
	}
	public String toString()
	{
		return data + flag;
	}
	//根据data实例变量来决定两个DataWrap的大小
	public int compareTo(DataWrap dw)
	{
		return this.data > dw.data ? 1 
			: (this.data == dw.data ? 0 : -1);
	}
}
public class HeapSort
{
	public static void heapSort(DataWrap[] data) 
	{
		System.out.println("开始排序");
		int arrayLength = data.length;
		//循环建堆
		for (int i = 0; i < arrayLength - 1 ; i++ )//n-1次循环
		{
			//建堆
			builMaxdHeap(data , arrayLength - 1 - i);
			//交换堆顶和最后一个元素
			swap(data , 0 , arrayLength - 1 - i);
			System.out.println(java.util.Arrays.toString(data));
		}
	}
	//对data数组从0到lastIndex建大顶堆
	private static void builMaxdHeap(DataWrap[] data , int lastIndex)
	{
		//从lastIndex处节点(最后一个节点)的父节点开始
		for (int i = (lastIndex - 1) / 2 ; i >= 0  ; i--)
		{
			//k保存当前正在判断的节点
			int k = i;
			//如果当前k节点的子节点存在
			while (k * 2 + 1 <= lastIndex)
			{
				//k节点的左子节点的索引
				int biggerIndex = 2 * k  + 1; 
				//如果biggerIndex小于lastIndex,即biggerIndex + 1
				//代表的k节点的右子节点存在
				if (biggerIndex < lastIndex)
				{
					 //如果右子节点的值较大
					if(data[biggerIndex].compareTo(data[biggerIndex + 1]) < 0)
					{
						//biggerIndex总是记录较大子节点的索引
						biggerIndex++; 
					}
				}
				//如果k节点的值小于其较大子节点的值
				if(data[k].compareTo(data[biggerIndex]) < 0)
				{
					//交换它们
					swap(data , k , biggerIndex);
					//将biggerIndex赋给k,开始while循环的下一次循环,
					//重新保证k节点的值大于其左、右子节点的值。
					k = biggerIndex;
				}
				else
				{
					break;
				}
			}
		}
	}
	//交换data数组中i、j两个索引处的元素
	private static void swap(DataWrap[] data , int i , int j)
	{
		DataWrap tmp = data[i];
		data[i] = data[j];
		data[j] = tmp;
	}
	public static void main(String[] args)
	{
		DataWrap[] data = {
			new DataWrap(21 , ""),
			new DataWrap(30 , ""),
			new DataWrap(49 , ""),
			new DataWrap(30 , "*"),
			new DataWrap(21 , "*"),
			new DataWrap(16 , ""),
			new DataWrap(9 , "")
		};
		System.out.println("排序之前:\n"
			+ java.util.Arrays.toString(data));
		heapSort(data);
		System.out.println("排序之后:\n" 
			+ java.util.Arrays.toString(data));
	}
}
//时间复杂度:nlog2n
//空间复杂度:1
//稳定性:不稳定

 冒泡排序

import java.util.*;
//定义一个数据包装类
class DataWrap implements Comparable<DataWrap>
{
	int data;
	String flag;
	public DataWrap(int data, String flag)
	{
		this.data = data;
		this.flag = flag;
	}
	public String toString()
	{
		return data + flag;
	}
	//根据data实例变量来决定两个DataWrap的大小
	public int compareTo(DataWrap dw)
	{
		return this.data > dw.data ? 1 
			: (this.data == dw.data ? 0 : -1);
	}
}
public class BubbleSort
{
	public static void bubbleSort(DataWrap[] data) 
	{
		System.out.println("开始排序");
		int arrayLength = data.length;
		//依次进行n-1趟比较, 第i趟把第i大的值选出放在arrayLength-1-i位置上。
		for (int i = 0; i < arrayLength - 1 ; i++ )
		{
			boolean flag = false;
			for (int j = 0; j < arrayLength - 1 - i ; j++ )
			{
				//如果j索引处的元素大于j+1索引处的元素
				if (data[j].compareTo(data[j + 1]) > 0)
				{
					//交换它们
					DataWrap tmp = data[j + 1];
					data[j + 1] = data[j];
					data[j] = tmp;
					flag = true;
				}
			}
			System.out.println(java.util.Arrays.toString(data));
			//如果某趟没有发生交换,则表明已处于有序状态
			if (!flag)
			{
				break;
			}
		}
	}
	public static void main(String[] args)
	{
		DataWrap[] data = {
			new DataWrap(9 , ""),
			new DataWrap(16 , ""),
			new DataWrap(21 , "*"),
			new DataWrap(23 , ""),
			new DataWrap(30 , ""),
			new DataWrap(49 , ""),
			new DataWrap(21 , ""),
			new DataWrap(30 , "*")
		};
		System.out.println("排序之前:\n"
			+ java.util.Arrays.toString(data));
		bubbleSort(data);
		System.out.println("排序之后:\n" 
			+ java.util.Arrays.toString(data));
	}
}
//时间复杂度:
//空间复杂度:1
//稳定性:稳定

快速排序

用到了递归。注意分界值是和j交换来建立从小到大的排序。

import java.util.*;
//定义一个数据包装类
class DataWrap implements Comparable<DataWrap>
{
	int data;
	String flag;
	public DataWrap(int data, String flag)
	{
		this.data = data;
		this.flag = flag;
	}
	public String toString()
	{
		return data + flag;
	}
	//根据data实例变量来决定两个DataWrap的大小
	public int compareTo(DataWrap dw)
	{
		return this.data > dw.data ? 1 
			: (this.data == dw.data ? 0 : -1);
	}
}
public class QuickSort
{
	//将指定数组的i和j索引处的元素交换
    private static void swap(DataWrap[] data, int i, int j)
    {
        DataWrap tmp;
        tmp = data[i];
        data[i] = data[j];
        data[j] = tmp;
    }
	//对data数组中从start~end索引范围的子序列进行处理
	//使之满足所有小于分界值的放在左边,所有大于分界值的放在右边
	private static void subSort(DataWrap[] data
		, int start , int end)
	{
		//需要排序
		if (start < end)
		{
			//以第一个元素作为分界值
			DataWrap base = data[start];
			//i从左边搜索,搜索大于分界值的元素的索引
			int i = start;
			//j从右边开始搜索,搜索小于分界值的元素的索引
			int j = end + 1;
			while(true)
			{
				//找到大于分界值的元素的索引,或i已经到了end处
				while(i < end && data[++i].compareTo(base) <= 0);
				//找到小于分界值的元素的索引,或j已经到了start处
				while(j > start && data[--j].compareTo(base) >= 0);
				if (i < j)
				{
					swap(data , i , j);
				}
				else
				{
					break;
				}
			}
			swap(data , start , j);
			//递归左子序列
			subSort(data , start , j - 1);
			//递归右边子序列
			subSort(data , j + 1, end);
		}
	}
	public static void quickSort(DataWrap[] data) 
	{
		subSort(data , 0 , data.length - 1);
	}
	public static void main(String[] args)
	{
		DataWrap[] data = {
			new DataWrap(9 , ""),
			new DataWrap(-16 , ""),
			new DataWrap(21 , "*"),
			new DataWrap(23 , ""),
			new DataWrap(-30 , ""),
			new DataWrap(-49 , ""),
			new DataWrap(21 , ""),
			new DataWrap(30 , "*"),
			new DataWrap(13 , "*")
		};
		System.out.println("排序之前:\n"
			+ java.util.Arrays.toString(data));
		quickSort(data);
		System.out.println("排序之后:\n" 
			+ java.util.Arrays.toString(data));
	}
}
//时间复杂度:n的平方
//空间复杂度:1
//稳定性:稳定

直接插入排序

import java.util.*;
//定义一个数据包装类
class DataWrap implements Comparable<DataWrap>
{
	int data;
	String flag;
	public DataWrap(int data, String flag)
	{
		this.data = data;
		this.flag = flag;
	}
	public String toString()
	{
		return data + flag;
	}
	//根据data实例变量来决定两个DataWrap的大小
	public int compareTo(DataWrap dw)
	{
		return this.data > dw.data ? 1 
			: (this.data == dw.data ? 0 : -1);
	}
}
public class InsertSort
{
	public static void insertSort(DataWrap[] data) 
	{
		System.out.println("直接插入排序\n开始排序:\n");
		int arrayLength = data.length;
		for (int i = 1 ; i < arrayLength ; i++ )
		{
			//当整体后移时,保证data[i]的值不会丢失
			DataWrap tmp = data[i];
			//i索引处的值已经比前面所有值都大,表明已经有序,无需插入
			//(i-1索引之前的数据已经有序的,i-1索引处元素的值就是最大值)
			if (data[i].compareTo(data[i - 1]) < 0)
			{
				int j = i - 1;
				//整体后移一格
				for ( ; j >= 0 && data[j].compareTo(tmp) > 0 ; j--)
				{
					data[j + 1] = data[j];
				}
				//最后将tmp的值插入合适位置
				data[j + 1] = tmp;
			}
			System.out.println(java.util.Arrays.toString(data));
		}
	}
	public static void main(String[] args)
	{
		DataWrap[] data = {
			new DataWrap(9 , ""),
			new DataWrap(-16 , ""),
			new DataWrap(21 , "*"),
			new DataWrap(23 , ""),
			new DataWrap(-30 , ""),
			new DataWrap(-49 , ""),
			new DataWrap(21 , ""),
			new DataWrap(30 , "*"),
			new DataWrap(30 , "")
		};
		System.out.println("排序之前:\n"
			+ java.util.Arrays.toString(data));
		insertSort(data);
		System.out.println("排序之后:\n" 
			+ java.util.Arrays.toString(data));
	}
}

折半插入排序

import java.util.*;
//定义一个数据包装类
class DataWrap implements Comparable<DataWrap>
{
	int data;
	String flag;
	public DataWrap(int data, String flag)
	{
		this.data = data;
		this.flag = flag;
	}
	public String toString()
	{
		return data + flag;
	}
	//根据data实例变量来决定两个DataWrap的大小
	public int compareTo(DataWrap dw)
	{
		return this.data > dw.data ? 1 
			: (this.data == dw.data ? 0 : -1);
	}
}
public class BinaryInsertSort
{
	public static void binaryInsertSort(DataWrap[] data)
	{
		System.out.println("开始排序:\n");
		int arrayLength = data.length;
		for(int i = 1 ; i < arrayLength ; i++)
		{
			//当整体后移时,保证data[i]的值不会丢失
			DataWrap tmp = data[i];
			int low = 0;
			int high = i - 1;
			while(low <= high)
			{
				//找出low、high中间的索引
				int mid = (low + high) / 2;
				//如果tmp值大于low、high中间元素的值
				if(tmp.compareTo(data[mid]) > 0)
				{
					//限制在索引大于mid的那一半中搜索
					low = mid + 1;
				} 
				else
				{
					//限制在索引小于mid的那一半中搜索
					high = mid - 1;
				}
			}
			//将low到i处的所有元素向后整体移一位
			for(int j = i ; j > low ; j--)
			{
				data[j] = data[j - 1];
			}
			//最后将tmp的值插入合适位置
			data[low] = tmp;
			System.out.println(java.util.Arrays.toString(data));
		}
	}
	public static void main(String[] args)
	{
		DataWrap[] data = {
			new DataWrap(9 , ""),
			new DataWrap(-16 , ""),
			new DataWrap(21 , "*"),
			new DataWrap(23 , ""),
			new DataWrap(-30 , ""),
			new DataWrap(-49 , ""),
			new DataWrap(21 , ""),
			new DataWrap(30 , "*"),
			new DataWrap(30 , "")
		};
		System.out.println("排序之前:\n"
			+ java.util.Arrays.toString(data));
		binaryInsertSort(data);
		System.out.println("排序之后:\n" 
			+ java.util.Arrays.toString(data));
	}
}

Shell排序

在进行排序时的数据项之间的间隔被称为增量,习惯上用h表示。h序列从1开始,通过h=3*h+1计算产生(其实直接插入排序是Shell排序的一种特例:直接使用增量为1Shell

排序。)

import java.util.*;
//定义一个数据包装类
class DataWrap implements Comparable<DataWrap>
{
	int data;
	String flag;
	public DataWrap(int data, String flag)
	{
		this.data = data;
		this.flag = flag;
	}
	public String toString()
	{
		return data + flag;
	}
	//根据data实例变量来决定两个DataWrap的大小
	public int compareTo(DataWrap dw)
	{
		return this.data > dw.data ? 1 
			: (this.data == dw.data ? 0 : -1);
	}
}
public class ShellSort
{
	public static void shellSort(DataWrap[] data) 
	{
		System.out.println("Shell\n开始排序:");
		int arrayLength = data.length;
		//h变量保存可变增量
		int h = 1;
		//按h * 3 + 1得到增量序列的最大值
		while(h <= arrayLength / 3)
		{
			h = h * 3 + 1;
		}
		while(h > 0)
		{
			System.out.println("===h的值:" + h + "===");
			for (int i = h ; i < arrayLength ; i++ )
			{
				//当整体后移时,保证data[i]的值不会丢失
				DataWrap tmp = data[i];
				//i索引处的值已经比前面所有值都大,表明已经有序,无需插入
				//(i-1索引之前的数据已经有序的,i-1索引处元素的值就是最大值)
				if (data[i].compareTo(data[i - h]) < 0)
				{
					int j = i - h;
					//整体后移h格
					for ( ; j >= 0 && data[j].compareTo(tmp) > 0 ; j-=h)
					{
						data[j + h] = data[j];
					}
					//最后将tmp的值插入合适位置
					data[j + h] = tmp;
				}
				System.out.println(java.util.Arrays.toString(data));
			}
			h = (h - 1) / 3;
		}
	}
	public static void main(String[] args)
	{
		DataWrap[] data = {
			new DataWrap(9 , ""),
			new DataWrap(-16 , ""),
			new DataWrap(21 , "*"),
			new DataWrap(23 , ""),
			new DataWrap(-30 , ""),
			new DataWrap(-49 , ""),
			new DataWrap(21 , ""),
			new DataWrap(30 , "*"),
			new DataWrap(30 , ""),
		};
		System.out.println("排序之前:\n"
			+ java.util.Arrays.toString(data));
		shellSort(data);
		System.out.println("排序之后:\n" 
			+ java.util.Arrays.toString(data));
	}
}
//时间复杂度:
//空间复杂度:1
//稳定性:稳定

归并排序

他是将两个有序的数据序列合并成一个新的有序序列。

 

class DataWrap implements Comparable<DataWrap>
{
	int data;
	String flag;
	public DataWrap(int data, String flag)
	{
		this.data = data;
		this.flag = flag;
	}
	public String toString()
	{
		return data + flag;
	}
	//根据data实例变量来决定两个DataWrap的大小
	public int compareTo(DataWrap dw)
	{
		return this.data > dw.data ? 1 
			: (this.data == dw.data ? 0 : -1);
	}
}
public class MergeSort 
{
	//利用归并排序算法对数组data进行排序 
	public static void mergeSort(DataWrap[] data) 
	{
		//归并排序 
		sort(data , 0 , data.length - 1);
	}
	/** 
	 * 将索引从left到right范围的数组元素进行归并排序 
	 * @param data 待排序的数组
	 * @param left 待排序的数组的第一个元素索引 
	 * @param right 待排序的数组的最后一个元素的索引 
	 */ 
	private static void sort(DataWrap[] data
		 , int left, int right) 
	{ 
		if (left < right) 
		{
			//找出中间索引
			int center = (left + right) / 2;
			//对左边数组进行递归
			sort(data, left, center); 
			//对右边数组进行递归
			sort(data, center + 1, right); 
			//合并
			merge(data, left, center, right); 
		} 
	} 
	/** 
	 * 将两个数组进行归并,归并前两个数组已经有序,归并后依然有序。 
	 * @param data 数组对象 
	 * @param left 左数组的第一个元素的索引 
	 * @param center 左数组的最后一个元素的索引,center+1是右数组第一个元素的索引
	 * @param right 右数组的最后一个元素的索引 
	 */ 
	private static void merge(DataWrap[] data
		, int left, int center, int right) 
	{
		//定义一个与待排序序列长度相同的临时数组 
		DataWrap[] tmpArr = new DataWrap[data.length];
		int mid = center + 1;
		//third记录中间数组的索引
		int third = left; 
		int tmp = left; 
		while (left <= center && mid <= right) 
		{ 
			//从两个数组中取出小的放入中间数组 
			if (data[left].compareTo(data[mid]) <= 0) 
			{ 
				tmpArr[third++] = data[left++]; 
			} 
			else
			{
				tmpArr[third++] = data[mid++]; 
			}
		} 
		//剩余部分依次放入中间数组 
		while (mid <= right) 
		{ 
			tmpArr[third++] = data[mid++]; 
		} 
		while (left <= center) 
		{ 
			tmpArr[third++] = data[left++]; 
		} 
		//将中间数组中的内容复制拷回原数组
		//(原left~right范围的内容复制回原数组) 
		while (tmp <= right)
		{
			data[tmp] = tmpArr[tmp++]; 
		}
	} 
	public static void main(String[] args)
	{
		DataWrap[] data = {
			new DataWrap(9 , ""),
			new DataWrap(-16 , ""),
			new DataWrap(21 , "*"),
			new DataWrap(23 , ""),
			new DataWrap(-30 , ""),
			new DataWrap(-49 , ""),
			new DataWrap(21 , ""),
			new DataWrap(30 , "*"),
			new DataWrap(30 , "")
		};
		System.out.println("排序之前:\n"
			+ java.util.Arrays.toString(data));
		mergeSort(data);
		System.out.println("排序之后:\n" 
			+ java.util.Arrays.toString(data));
	}
}
//时间复杂度:
//空间复杂度:
//稳定性:稳定
桶式排序

桶式排序的特征:

待排序列的所有值处于一个可枚举范围内;

待排序列所在的这个可枚举范围不应该太大,否则排序开销太大。

import java.util.Arrays;
class DataWrap implements Comparable<DataWrap>
{
	int data;
	String flag;
	public DataWrap(int data, String flag)
	{
		this.data = data;
		this.flag = flag;
	}
	public String toString()
	{
		return data + flag;
	}
	//根据data实例变量来决定两个DataWrap的大小
	public int compareTo(DataWrap dw)
	{
		return this.data > dw.data ? 1 
			: (this.data == dw.data ? 0 : -1);
	}
}
public class BucketSort
{
	public static void bucketSort(DataWrap[] data 
		, int min , int max)
	{
		System.out.println("开始排序:");
		//arrayLength记录待排序数组的长度
		int arrayLength = data.length;
		DataWrap[] tmp = new DataWrap[arrayLength];
		//buckets数组相当于定义了max - min个桶,
		//buckets数组用于记录待排序元素的信息
		int[] buckets = new int[max - min];	
		//计算每个元素在序列出现的次数
		for(int i = 0 ; i < arrayLength ; i++)
		{
			//buckets数组记录了DataWrap出现的次数
			buckets[data[i].data - min]++;
		}
		System.out.println( Arrays.toString(buckets));
		//计算“落入”各桶内的元素在有序序列中的位置
		for(int i = 1 ; i < max - min; i++)
		{
			//前一个bucket的值 + 当前bucket的值 -> 当前bucket新的值
			buckets[i] = buckets[i] + buckets[i - 1];
		}
		//循环结束后,buckets数组元素记录了“落入”前面所有桶和 
		//“落入”当前bucket中元素的总数,
		//也就说:buckets数组元素的值代表了“落入”当前桶的元素在有序序列中的位置
		System.out.println( Arrays.toString(buckets));
		//将data数组中数据完全复制到tmp数组中缓存起来。
		System.arraycopy(data, 0, tmp, 0, arrayLength);
		//根据buckets数组中的信息将待排序列的各元素放入相应的位置。
		for(int k = arrayLength - 1 ; k >=  0 ; k--)//从高位开始可以保证排序的稳定性
		{
			data[--buckets[tmp[k].data - min]] = tmp[k];
		}
	}
	public static void main(String[] args)
	{
		DataWrap[] data = {
			new DataWrap(9 , ""),
			new DataWrap(5, ""),
			new DataWrap(-1, ""),
			new DataWrap(8 , ""),
			new DataWrap(5 , "*"),
			new DataWrap(7 , ""),
			new DataWrap(3 , ""),
			new DataWrap(-3, ""),
			new DataWrap(1 , ""),
			new DataWrap(3 , "*")
		};
		System.out.println("排序之前:\n"
			+ java.util.Arrays.toString(data));
		bucketSort(data , -3 , 10);
		System.out.println("排序之后:\n" 
			+ java.util.Arrays.toString(data));
	}
}
//时间复杂度:小
//空间复杂度:大
//稳定性:稳定
 基数排序

基数排序必须依赖于另外的排序方法。基数排序的总体思想就是将待排序数据拆分成多个关键字进行排序,也就是说,基数排序的实质是多关键字排序。

多关键字排序解决方案:

最高位优先法MSD

最低位优先法LSD

基数排序对任一子关键字排序时必须借助于另外一个排序方法,而且这种排序方法必须是稳定的,一般用通式排序。

import java.util.Arrays;
public class MultiKeyRadixSort
{	
	/**
	 * @param data 待排序的数组	
	 * @param radix  指定关键字拆分的进制。如radix=10,表明按10进制拆分
	 * @param d 指定将关键字拆分成几个子关键字
	 */
	public static void radixSort(int[] data, int radix, int d) 
	{
		System.out.println("开始排序:");
		int arrayLength = data.length;
		//需要一个临时数组
		int[] tmp = new int[arrayLength];
		//buckets数组是桶式排序必须buckets数组
		int[] buckets = new int[radix];
		//依次从最高位的子关键字对待排数据进行排序
		//下面循环中rate用于保存当前计算的位(比如十位时rate=10)
		for(int i = 0 , rate = 1 ; i < d ; i++)
		{
			//重置count数组,开始统计第二个关键字
			Arrays.fill(buckets, 0);
			//将data数组的元素复制到temporary数组中进行缓存
			System.arraycopy(data, 0, tmp, 0, arrayLength);
			//计算每个待排序数据的子关键字
			for(int j = 0 ; j < arrayLength ; j++)
			{
				//计算数据指定位上的子关键字
				int subKey = (tmp[j] / rate) % radix;
				buckets[subKey]++;
			}
			for(int j = 1 ; j < radix ; j++)
			{
				buckets[j] = buckets[j] + buckets[j-1];
			}
			//按子关键字对指定数据进行排序
			for(int m = arrayLength - 1 ; m >= 0 ; m--)
			{
				int subKey = (tmp[m] / rate) % radix;
				data[--buckets[subKey]] = tmp[m];
			}
			System.out.println("对" + rate + "位上子关键字排序:" 
				+ java.util.Arrays.toString(data));
			rate *= radix;
		}
	}
	public static void main(String[] args)
	{
		int[] data = {1100 , 192 , 221 , 12 , 13};
		System.out.println("排序之前:\n"
			+ java.util.Arrays.toString(data));
		radixSort(data , 10 , 4);
		System.out.println("排序之后:\n" 
			+ java.util.Arrays.toString(data));
	}
}
 

文章评论

为啥Android手机总会越用越慢?
为啥Android手机总会越用越慢?
程序员的鄙视链
程序员的鄙视链
漫画:程序员的工作
漫画:程序员的工作
Java 与 .NET 的平台发展之争
Java 与 .NET 的平台发展之争
一个程序员的时间管理
一个程序员的时间管理
为什么程序员都是夜猫子
为什么程序员都是夜猫子
10个调试和排错的小建议
10个调试和排错的小建议
中美印日四国程序员比较
中美印日四国程序员比较
Web开发人员为什么越来越懒了?
Web开发人员为什么越来越懒了?
我跳槽是因为他们的显示器更大
我跳槽是因为他们的显示器更大
科技史上最臭名昭著的13大罪犯
科技史上最臭名昭著的13大罪犯
程序员的一天:一寸光阴一寸金
程序员的一天:一寸光阴一寸金
程序员眼里IE浏览器是什么样的
程序员眼里IE浏览器是什么样的
 程序员的样子
程序员的样子
如何区分一个程序员是“老手“还是“新手“?
如何区分一个程序员是“老手“还是“新手“?
我的丈夫是个程序员
我的丈夫是个程序员
不懂技术不要对懂技术的人说这很容易实现
不懂技术不要对懂技术的人说这很容易实现
总结2014中国互联网十大段子
总结2014中国互联网十大段子
程序员和编码员之间的区别
程序员和编码员之间的区别
做程序猿的老婆应该注意的一些事情
做程序猿的老婆应该注意的一些事情
5款最佳正则表达式编辑调试器
5款最佳正则表达式编辑调试器
程序员必看的十大电影
程序员必看的十大电影
团队中“技术大拿”并非越多越好
团队中“技术大拿”并非越多越好
程序员都该阅读的书
程序员都该阅读的书
Web开发者需具备的8个好习惯
Web开发者需具备的8个好习惯
十大编程算法助程序员走上高手之路
十大编程算法助程序员走上高手之路
Java程序员必看电影
Java程序员必看电影
程序员最害怕的5件事 你中招了吗?
程序员最害怕的5件事 你中招了吗?
亲爱的项目经理,我恨你
亲爱的项目经理,我恨你
看13位CEO、创始人和高管如何提高工作效率
看13位CEO、创始人和高管如何提高工作效率
编程语言是女人
编程语言是女人
每天工作4小时的程序员
每天工作4小时的程序员
“懒”出效率是程序员的美德
“懒”出效率是程序员的美德
如何成为一名黑客
如何成为一名黑客
什么才是优秀的用户界面设计
什么才是优秀的用户界面设计
写给自己也写给你 自己到底该何去何从
写给自己也写给你 自己到底该何去何从
60个开发者不容错过的免费资源库
60个开发者不容错过的免费资源库
初级 vs 高级开发者 哪个性价比更高?
初级 vs 高级开发者 哪个性价比更高?
程序猿的崛起——Growth Hacker
程序猿的崛起——Growth Hacker
当下全球最炙手可热的八位少年创业者
当下全球最炙手可热的八位少年创业者
程序员应该关注的一些事儿
程序员应该关注的一些事儿
“肮脏的”IT工作排行榜
“肮脏的”IT工作排行榜
聊聊HTTPS和SSL/TLS协议
聊聊HTTPS和SSL/TLS协议
老程序员的下场
老程序员的下场
我是如何打败拖延症的
我是如何打败拖延症的
软件开发程序错误异常ExceptionCopyright © 2009-2015 MyException 版权所有