`
啸笑天
  • 浏览: 3462737 次
  • 性别: 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天，你的英语就可以凑合 ...
评论
发表评论

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

相关推荐

    U盘量产工具SM3280&3281&3282-AvidiaV0209整合版

    U盘量产工具FLASH量产工具SM3280&3281&3282-AvidiaV0209整合版

    java课程期末考试.zip

    java课程期末考试

    分布式消息中间件，参考kafka，未完成.zip

    分布式消息中间件，参考kafka，未完成

    修木工施工规范及流程.docx

    修木工施工规范及流程.docx

    汽车电子中MICROSAR OBD协议栈解决方案及其应用

    内容概要：本文详细介绍了VECTOR提供的MICROSAR OBD协议栈解决方案，涵盖了OBD模块、ECU支持、监控功能和服务请求等方面的内容。此外，还讨论了OBD在不同国家和地区的技术标准与法规要求，以及MICROSAR OBD解决方案的优势，如适应不同项目的需求和高度集成于AUTOSAR 4平台。 适合人群：汽车电子工程师、软件开发者、汽车制造商及相关行业从业人员。 使用场景及目标：① 适用于车辆诊断系统的开发和维护；②帮助工程师理解和掌握OBD协议的具体实施方法和应用场景；③ 提供了一个成熟、可扩展的解决方案，用于满足OBD相关标准和法规的要求。 其他说明：本文不仅提供了技术层面的详细解析，还探讨了实际操作过程中可能遇到的问题和解决方案。同时强调了屏蔽信息过载的重要性，提醒工程师保持内心平静，专注做好本职工作。

    适用于 Python 的 LINE 消息 API SDK.zip

    适用于 Python 的 LINE 消息 API SDK适用于 Python 的 LINE Messaging API 的 SDK。介绍适用于 Python 的 LINE Messaging API SDK 可以轻松使用 LINE Messaging API 开发机器人，您可以在几分钟内创建一个示例机器人。文档请参阅官方 API 文档了解更多信息英语https //developers.line.biz/en/docs/messaging-api/overview/日语https://developers.line.biz/ja/docs/messaging-api/overview/要求Python >= 3.9安装$ pip 安装 line-bot-sdk概要用法from flask import Flask, request, abortfrom linebot.v3 import ( WebhookHandler)from linebot.v3.exceptions import ( InvalidSig

    Java字节码工程工具包.zip

    Java字节码工程工具包Javassist 版本 3版权所有 (C) 1999-2023 Shigeru Chiba，保留所有权利。Javassist（JAVA 编程助手）使 Java 字节码操作变得简单。它是一个用于编辑 Java 字节码的类库它使 Java 程序能够在运行时定义新类并在 JVM 加载类文件时对其进行修改。与其他类似的字节码编辑器不同，Javassist 提供两个级别的 API源代码级别和字节码级别。如果用户使用源代码级别 API，他们可以编辑类文件而无需了解 Java 字节码的规范。整个 API 仅使用 Java 语言的词汇表进行设计。您甚至可以以源文本的形式指定插入的字节码Javassist 会即时编译它。另一方面，字节码级别 API 允许用户像其他编辑器一样直接编辑类文件。该软件根据 Mozilla 公共许可证版本 1.1、GNU 宽通用公共许可证版本 2.1 或更高版本或 Apache 许可证版本 2.0 分发。文件README.md 此自述文件。Changes.md 发行说明。License.html 许可证文件。tuto

    毕设源码-基于python的西西家居全屋定制系统的设计与实现_ijsj--论文-期末大作业+说明文档.rar

    本项目是基于Python语言开发的西西家居全屋定制系统，旨在为家居行业提供一个高效、智能的定制解决方案。项目涵盖了从客户需求分析、设计方案生成、材料选购到最终订单生成的全过程，力求实现家居定制的数字化和智能化。 在主要功能方面，系统具备强大的客户管理模块，能够详细记录和分析客户的定制需求。设计模块则采用先进的三维建模技术，为客户提供直观、真实的家居设计方案预览。此外，系统还整合了丰富的材料数据库，方便客户根据自身喜好和预算进行材料选择。 框架方面，项目采用了B/S架构，确保了系统的稳定性和可扩展性。后端使用Python的Django框架，前端则结合了HTML、CSS和JavaScript等技术，实现了用户界面的友好和响应速度。 开发此项目的目的，不仅是为了满足家居行业对个性化定制的需求，也为计算机相关专业的学生提供了一个实践和学习的平台，有助于提升他们的实际开发能力。

    Javascript 是数字化创新的起点，是语言的基础，也是基本概念 .zip

    Javascript 是数字化创新的起点，是语言的基础，也是基本概念。Basecamp JavascriptJavascript 是数字化创新的起点，是语言的基础，也是基本概念。嵌套存储库，可作为启动项下待办事项的实践活动。

    已弃用 - Coinbase Python API.zip

    已弃用 — Coinbase Python APICoinbase Coinbase API V2的官方 Python 库。重要提示此库当前针对的是 API V2，而 OAuth 客户端需要 V2 权限（即wallet:accounts:read）。如果您仍在使用 API V1，请使用此库的旧版本。特征接近 100％ 的测试覆盖率。支持API Key + Secret和OAuth 2身份验证。调用 API 的便捷方法 - 为您打包 JSON！自动将 API 响应解析为相关的 Python 对象。使用IPython时，所有对象都具有可制表完成的方法和属性。安装coinbase可以在PYPI上使用。使用以下命令安装pippip install coinbase或者easy_installeasy_install coinbase该库目前针对 Python 版本 2.7 和 3.4+ 进行了测试。注意此软件包名称过去是指George Sibble维护的非官方 coinbase_python 库。George 慷慨地允许我们使用此软件包

    基于RBAC权限控制的基础后台.zip

    基于RBAC权限控制的基础后台

    毕设源码-python-基于Python爬虫的网络小说数据分析系统的设计与实现-期末大作业+说明文档.rar

    本项目是基于Python爬虫的网络小说数据分析系统的设计与实现，旨在为计算机相关专业的大学生提供一个实践平台，特别是在毕业设计和项目实战练习方面。项目通过Python强大的网络爬虫技术，从流行的网络小说网站自动抓取数据，包括书籍信息、章节内容、用户评论等。 主要功能涵盖数据采集、数据清洗、数据存储和数据分析。数据采集模块利用Scrapy等爬虫框架高效抓取网页内容；数据清洗模块确保数据的准确性和一致性；数据存储则采用MySQL等数据库系统，便于数据管理和查询；数据分析模块通过Pandas、NumPy等工具进行数据处理和分析，生成多维度的统计报告和可视化图表。 此项目不仅帮助学生掌握Python编程和网络爬虫技术，还能让他们深入了解数据分析的全过程，提升解决实际问题的能力。同时，系统的实现和应用也反映了现代信息技术在文学创作和消费领域的应用价值和潜力。

    ssm框架Java项目源码-基于Java的在线日语培训平台的设计与实现+jsp毕设-大作业.zip

    本项目是一个基于Java的在线日语培训平台的设计与实现，采用SSM框架（Spring+SpringMVC+MyBatis）进行开发，旨在为计算机相关专业的学生提供一个实践和学习的平台，同时也为日语学习者提供一个在线学习的空间。项目中主要功能涵盖了用户管理、课程管理、学习资源上传下载、在线测试与反馈等多个方面。通过该平台，教师能够轻松管理课程内容和学生信息，学生则可以随时随地访问学习资源，参与在线课程和测试，从而提高学习效率和兴趣。 在开发此项目的过程中，我们重点关注了系统的可维护性和可扩展性，确保代码结构清晰，便于后续的功能迭代和优化。此外，通过使用SSM框架，实现了前后端的分离，提高了开发效率和系统的响应速度。该项目不仅能够满足毕设的需求，还能作为Java学习者提升编程能力和实践经验的实用工具。

    基于java的机票管理系统设计与实现.docx

    基于java的机票管理系统设计与实现.docx

    基于Java实现的数据结构设计源码学习指南

    该项目为《基于Java实现的数据结构设计源码》，共包含51个文件，主要由46个Java源文件构成，辅以2个文本文件、1个Git忽略文件、1个许可证文件以及1个XML文件，全面涵盖了数据结构设计的核心内容。

    绿色食品 水稻生产操作规程.docx

    绿色食品 水稻生产操作规程.docx

    这款出色的应用程序可以纠正您之前的控制台命令 .zip

    他妈的 Fuck是一款出色的应用程序，其灵感来自@liamosaur 的 推文，它可以纠正以前控制台命令中的错误。The Fuck太慢了吗？试试实验性的即时模式！更多示例➜ apt-get install vimE: Could not open lock file /var/lib/dpkg/lock - open (13: Permission denied)E: Unable to lock the administration directory (/var/lib/dpkg/), are you root?➜ fucksudo apt-get install vim [enter/↑/↓/ctrl+c][sudo] password for nvbn:Reading package lists... Done...➜ git pushfatal: The current branch master has no upstream branch.To push the current branch and set the remote

    全国大学生FPGA创新设计竞赛作品 泡罩包装药品质量在线检测平台.zip

    全国大学生FPGA创新设计竞赛作品 “泡罩包装药品质量在线检测平台“.zip

    桃苗木质量基本要求表.docx

    桃苗木质量基本要求表.docx

    使用 Python 漂亮地打印表格数据，这是一个库和一个命令行实用程序 存储库从 bitbucket.org,astanin,python-tabulate 迁移而来 .zip

    使用 Python 漂亮地打印表格数据，这是一个库和一个命令行实用程序。存储库从 bitbucket.org/astanin/python-tabulate 迁移而来。python-tabulate使用 Python、库和命令行实用程序漂亮地打印表格数据。该库的主要用例是轻松打印小表格只需一个函数调用，格式由数据本身引导为轻量级纯文本标记创作表格数据多种输出格式适合进一步编辑或转换混合文本和数字数据的可读表示智能列对齐、可配置数字格式、小数点对齐安装要安装 Python 库和命令行实用程序，请运行pip install tabulate命令行实用程序将在 Linux 上安装为（例如tabulate）或者在 Windows 上的 Python 安装中安装为（例如）。bin/usr/bintabulate.exeScriptsC:\Python39\Scripts\tabulate.exe您可以考虑仅为当前用户安装该库pip install tabulate --user在这种情况下，命令行实用程序将安装到 ~/.local/bin/tabula

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