| 【算法】 | 您所在的位置：网站首页 › shell排序稳定吗 › 【算法】 |
【算法】
|
基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较 基数排序是一种稳定排序算法，在某些时候，基数排序的效率高于其它的稳定排序 基数排序的方式可以采用最低位优先LSD（Least sgnificant digital）法或最高位优先MSD（Most sgnificant digital）法，LSD就是从个位先进行排序，然后十位、百位......MSD则相反 举例分析有一组无序序列，我们将其用基数排序算法进行排序（LSD）
按个位划分之后，我们再将这些数据依次取出来（取出之后已经是个位上的数字有序） 第二次排序 然后再将以上数据，按十位上的数字大小进行划分
第三次排序 然后再将以上数据，按百位上的数字大小进行划分
按百位划分之后，我们再将这些数据依次取出来（取出之后已经是个位上的数字、十位上的数字、百位上的数字都有序）
在以上排序中我们可以看到，共进行了三次排序，为什么？ 因为整个数组中的元素，最大元素就是999，他是3位的，所以需要进行3次排序 假如最大元素时1314，是4位的，那么我们就需要进行4次排序 总结一下 先找到数组中最大元素的位数，判断要进行几次排序然后先排个位，再排十位......其中每趟排序中，先依次划分元素，然后再依次取出元素注意：划分元素和取出元素时，一定是按顺序进行的，才可保证排序成功（因为写代码的时候，肯定是按顺序遍历的，所以无需特殊操作，只需正常写即可） Java代码 package algorithm; import java.util.Arrays; public class Sort { // 基数排序 private static int[] radixSort(int array[]) { // 10个桶，每个桶最多放全部 int[][] temp = new int[10][array.length]; // 存放每个桶里面放了几个元素 int[] tempIndex = new int[10]; // 获得数组中最大的数字 int max = getMax(array); // 获得最大数字的位数， int maxLength = (max+"").length(); // 转换成字符串，再获取长度即可 // 共比较最大数字位数次 for (int i = 0, n = 1; i < maxLength ; i++, n *= 10) { // 一次排序，将对应元素放入对应数组中 for (int j = 0 ; j < array.length ; j++) { // 取个位：(520 / 1) % 10 = 0 // 取十位：(520 / 10) % 10 = 2 // 取百位：(520 / 100) % 10 = 5 // 所以第一次比较个位 n = 1，第二次比较十位 n = 10... int remainder = (array[j] / n) % 10; // 把当前元素放入指定数组中的指定位置 // 取出来的余数是几，就放入第几个桶中（数组的第几行） // 然后放入那个桶中的 tempIndex[remainder] 位置 temp[remainder][tempIndex[remainder]] = array[j]; tempIndex[remainder]++; } // 用于取出数据时放入原数组中的下标 int index = 0; // 将元素全部依次取出 for (int k = 0 ; k < tempIndex.length ; k++) { // k 代表第几个桶 if (tempIndex[k] != 0) { // 说明这个桶中放入了元素，将其取出 // 取出一个桶中的数据 for (int w = 0 ; w < tempIndex[k] ; w++) { array[index] = temp[k][w]; // 替换原数组元素 index++; } tempIndex[k] = 0; // 清零 } // 取完一个桶的元素 } // 取完全部桶的元素 } return array; } // 获得数组中最大的数字 private static int getMax(int array[]) { int max = 0; for (int anArray : array) { if (anArray > max) { max = anArray; } } return max; } public static void main(String[] args) { int[] array = new int[]{5, 2, 0, 13, 14, 520, 134, 1314, 9999}; int[] result = radixSort(array); System.out.println(Arrays.toString(result)); } } 在以上代码中，我们需要注意一下创建二维数组这个 // 10个桶，每个桶最多放全部 int[][] temp = new int[10][array.length];数组的大小是10 × array.length ，说明有十行， array.length 列，每行代表一个桶，而一行中有多少个列，就代表这个桶可以放多少个元素 因为我们并不知道个位为0的有多少个元素，个位为1的有多少个元素，十位为9的有多少个元素......所以我们创建数组时，有多少列是不确定的而列的最大数，就是当所有元素的某位上数字都是一样的时候，就是数组的长度所以我们这里将其设置为最大 array.length如果数据少的情况下还好，但是当数据量很大的情况，为数组指定很大的空间，而根本用不到这么多的空间，就会有很多的空间被浪费掉了 所以我们可以先为数组指定一些空间，如果空间不够的话，再进行数组扩容，这样就有效避免资源浪费 或者直接存入一维数组中，比如在遍历个位的时候，直接将元素放入新的一维数组的指定位置中，而新的数组大小我们可以直接指定为原数组的大小 这里为了看起来更直观，所以采用二维数组模拟放置的桶（不是桶排序）
基数排序是一种用空间换时间的排序算法 时间复杂度最好情况：O(k * N)，k 为数组中最大数的位数 平均情况：O(k * N) 最坏情况：O(k * N) 虽然同为基数排序，但不同的写法，时间复杂度也会有一些差异 |
【本文地址】