`
啸笑天
  • 浏览: 3465821 次
  • 性别: Icon_minigender_1
  • 来自: China
社区版块
存档分类
最新评论

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

JavaJ#算法 
阅读更多

常见的内部排序：

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

直接选择排序

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排序的一种特例：直接使用增量为1的Shell

排序。）

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));
	}
}
 
  • 大小: 104.8 KB
分享到：
| 每天读一遍，坚持77天，你的英语就可以凑合 ...
评论
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

    java实现的设计模式code

    "java实现的设计模式code"这个压缩包可能包含了《JAVA与模式》这本书中的多个实例，这些实例有助于开发者理解和应用各种设计模式。 首先，我们来看一下一些常见的设计模式，并讨论它们在Java中的实现： 1. **单例...

    java算法练习代码code

    1. **排序算法**：Java代码可能会包含常见的排序算法，如冒泡排序、插入排序、选择排序、快速排序、归并排序和堆排序等。这些排序算法各有优缺点，适用于不同的场景，理解和掌握它们对于优化程序性能至关重要。 2. ...

    Java程序设计-常见算法

    本主题“Java程序设计-常见算法”主要涵盖查找算法和排序算法两个大类，下面将详细阐述这两个领域的基本概念、原理以及它们在Java中的实现。 首先，我们来讨论查找算法。查找算法的目标是在数据集合中找到特定元素...

    java编程常见面试题目

    2. **匿名内部类**：匿名内部类可以继承其他类并实现接口，但不能同时继承类和实现接口，因为Java不支持多继承。 3. **Static Nested Class 和 Inner Class**： - 静态嵌套类（Static Nested Class）与内部类...

    Java程序员常见笔试题

    ### Java程序员常见笔试题知识点详解 #### 一、final, finally, finalize的区别 - **final**: 这个关键字用于声明不可变的实体。当应用于类时，表示该类不能被继承；应用于方法时，表示该方法不能被重写；应用于...

    mongoDB Driver Java Real SourceCode

    这份"mongoDB Driver Java Real SourceCode"包含了MongoDB Java驱动程序的完整源代码，可以帮助我们深入理解其内部工作机制，提升开发效率。 源代码库名称为`mongo-java-driver-master`，表明这是驱动的主分支，很...

    java中常见字符的ASCII码表

    ASCII（美国标准信息交换代码，American Standard Code for Information Interchange）是一种广泛使用的字符编码标准，它定义了128个不同的字符，包括数字、大写字母、小写字母、标点符号和一些控制字符。在Java编程...

    java面试题

    51.5. java中有几种方法可以实现一个线程？用什么关键字修饰同步方法? stop()和suspend()方法为何不推荐使用？ 25 52. 数据连接池 25 52.1. 连接池的基本原理： 25 52.2. 连接池的工作机制 25 52.3. 建立连接池 26 ...

    Java常见面试题集及答案.docx

    以下是一些Java面试中常见的问题和答案，这些问题涵盖了语言核心、多线程、集合框架、异常处理等方面。 1. **final, finally, finalize的区别**： - `final`：用于声明变量、方法或类不可变，防止被修改。 - `...

    Java面试宝典-经典

    46、java中有几种方法可以实现一个线程？用什么关键字修饰同步方法? stop()和suspend()方法为何不推荐使用？ 29 47、sleep() 和 wait() 有什么区别? 30 48、同步和异步有何异同，在什么情况下分别使用他们？举例说明...

    java面试宝典

    76、什么是java序列化，如何实现java序列化？ 18 77、简述synchronized和java.util.concurrent.locks.Lock的异同 ？ 18 78、abstract class Name { private String name; public abstract boolean isStupidName...

    JAVA程序员面试三十二问

    【JAVA程序员面试三十二问详解】 1. **final, finally, finalize的区别** - `final`：用于声明类、变量或方法，表示不可变或不可继承。对于变量，一旦赋值后不能更改；对于方法，不能被重写；对于类，不能有子类。...

    java源码结构-Java-data-structure-source-code:Java数据结构

    这个"Java-data-structure-source-code"项目很可能是为了帮助开发者理解和学习这些数据结构的内部工作原理和实现细节，通过阅读和分析源代码，可以提高对Java编程和数据结构的深入理解。对于系统开发而言，熟悉和...

    java面试题大全（2012版）

    46、java中有几种方法可以实现一个线程？用什么关键字修饰同步方法? stop()和suspend()方法为何不推荐使用？ 29 47、sleep() 和 wait() 有什么区别? 30 48、同步和异步有何异同，在什么情况下分别使用他们？举例说明...

    java面试常见基础（深层次，高级研发）

    - **本地方法栈**：用于支持Java代码调用本地代码（Native Code）。 - **堆**：用于存储所有对象实例和数组，是所有线程共享的。 - **方法区**：存储已被虚拟机加载的类信息、常量、静态变量、即时编译器编译后的...

    IT java 面试题库

    - `TreeSet`: 实现了SortedSet接口，提供排序功能的Set集合。 2. **Collection和Collections的区别？** - `Collection`是集合层次结构中的根接口，它是所有具体集合类的父接口。 - `Collections`是工具类，提供...

    Android字母排序 (类似通讯录字母检索).rar

    在Android开发中，实现字母排序，类似于通讯录的字母检索功能，是一项常见且重要的任务。这一功能使得用户能够快速定位并查找目标联系人，极大地提高了用户体验。本项目名为"Android字母排序 (类似通讯录字母检索)...

    java陷阱--面试(题集)杂谈

    但在Java中，匿名内部类只能继承一个非抽象类或实现一个接口，不能同时做这两件事。 第三，Static Nested Class（静态嵌套类）和Inner Class（内部类）的主要区别在于，静态嵌套类不持有对外部类的隐式引用，可以...

Magicbox
Global site tag (gtag.js) - Google Analytics