java数组的排序对于short,int和long型,采用不同的排序策略。int和long采用快速排序,而short采用计数排序。
计数排序是一个非基于比较的排序算法,该算法于1954年由 Harold H. Seward 提出。它的优势在于在对一定范围内的整数排序时,它的复杂度为Ο(n+k)(其中k是整数的范围),快于任何比较排序算法。
计数排序利用的是数组的随机访问特性,将要排序的数k转换成数组的下标K,该数组中以k为下标的值A[k]代表这个数K的个数。这种排序非常快,但应用条件比较苛刻。
主要受需要排序的序列规模(n),序列最大值(max(n))影响,如果max(n)过大,算法空间复杂度比较高,也是该算法的一个制约因素。
先看看计数排序的定义
Counting sort (sometimes referred to as ultra sort or math sort[1]) is a sorting algorithm which (like bucket sort) takes advantage of knowing the range of the numbers in the array to be sorted (array A). It uses this range to create an array C of this length. Each index i in array C is then used to count how many elements in A have the value i; then counts stored in C can then be used to put the elements in A into their right position in the resulting sorted array. The algorithm was created by Harold H. Seward in 1954.
计数排序是一个类似于桶排序的排序算法,其优势是对已知数量范围的数组进行排序。它创建一个长度为这个数据范围的数组C,C中每个元素记录要排序数组中对应记录的出现个数。这个算法于1954年由 Harold H. Seward 提出。
下面以示例来说明这个算法
假设要排序的数组为 A = {1,0,3,1,0,1,1}
这里最大值为3,最小值为0,那么我们创建一个数组C,长度为4.
然后一趟扫描数组A,得到A中各个元素的总数,并保持到数组C的对应单元中。
比如0 的出现次数为2次,则 C[0] = 2;1 的出现次数为4次,则C[1] = 4
由于C 是以A的元素为下标的,所以这样一做,A中的元素在C中自然就成为有序的了,这里我们可以知道 顺序为 0,1,3 (2 的计数为0)
然后我们把这个在C中的记录按每个元素的计数展开到输出数组B中,排序就完成了。
也就是 B[0] 到 B[1] 为0 B[2] 到 B[5] 为1 这样依此类推。
这种排序算法,依靠一个辅助数组来实现,不基于比较,算法复杂度为 O(n) ,但由于要一个辅助数组C,所以空间复杂度要大一些,由于计算机的内存有限,这种算法不适合范围很大的数的排序。注:基于比较的排序算法的最佳平均时间复杂度为 O(nlogn)
这是JDK源码中的arrays.java, count是辅助排序的数组,具体的算法解释。见中文注释。
/** * Sorts the specified range of the array using the given * workspace array slice if possible for merging * * @param a the array to be sorted * @param left the index of the first element, inclusive, to be sorted * @param right the index of the last element, inclusive, to be sorted * @param work a workspace array (slice) * @param workBase origin of usable space in work array * @param workLen usable size of work array */ static void sort(short[] a, int left, int right, short[] work, int workBase, int workLen) { // Use counting sort on large arrays if (right - left > COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR) { //COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR = 3200 int[] count = new int[NUM_SHORT_VALUES]; //NUM_SHORT_VALUES=1 << 16 for (int i = left - 1; ++i <= right; count[a[i] - Short.MIN_VALUE]++ ); //计算排序数组中,每一个元素出现的次数 for (int i = NUM_SHORT_VALUES, k = right + 1; k > left; ) { while (count[--i] == 0); //数组上部清零 short value = (short) (i + Short.MIN_VALUE); int s = count[i]; do { a[--k] = value; //对数组a[]进行排序 } while (--s > 0); } } else { // Use Dual-Pivot Quicksort on small arrays doSort(a, left, right, work, workBase, workLen); } }
相关推荐
java中数组的自定义排序,种类繁多,简单实现,可自由操控。
java数组排序的思想,过程和代码实现。多种数组排序的方法,主要有冒泡排序,堆排序,插入排序, 归并操作(merge), 归并操作(merge),选择排序,希尔排序。
java 数组递增排序 java 数组递增排序 java 数组递增排序
JAVA\数组排序,JAVA语言实现随机数的输入以及数组的排序。JAVA 随机数 数组排序
java 部分数组递增排序 java 部分数组递增排序 java 部分数组递增排序
Java数组排序:冒泡排序、选择排序 、插入排序 、快速排序、希尔排序、堆排序和归并排序 三种Java数组复制方法 Java数组最大最小值 四种合并Java数组方法 Java数组升降序排序 Java数组查找:二分查找、顺序查找、...
java冒泡排序 代码为排序源代码 简洁明了 无其他
Java数组阶段的选择题、填空题、编程题、判断题都有,适合想自己测试下的学生以及准备出题的老师
Java 数组以及排序算法
JAVA数组的排序方法实例.docx
Java数组在内存分配方面的知识;Java数组的静态特征;对于数组变量而言,一定要区分它何时是数组变量,何时代表数组对象本身。
java 数组初始化 详解 doc
使用冒泡排序实现的java语言编写的关于二维数组的排序,实现了行、列的排序输出。
文件读出数组进行选择排序和二分查找文件读出数组进行选择排序和二分查找java实现
46.java数组遍历1.zip46.java数组遍历1.zip46.java数组遍历1.zip46.java数组遍历1.zip46.java数组遍历1.zip46.java数组遍历1.zip46.java数组遍历1.zip46.java数组遍历1.zip46.java数组遍历1.zip46.java数组遍历1.zip...
43.java数组定义1.zip43.java数组定义1.zip43.java数组定义1.zip43.java数组定义1.zip43.java数组定义1.zip43.java数组定义1.zip43.java数组定义1.zip43.java数组定义1.zip43.java数组定义1.zip43.java数组定义1.zip...
22.java数组的复制.zip22.java数组的复制.zip22.java数组的复制.zip22.java数组的复制.zip22.java数组的复制.zip22.java数组的复制.zip22.java数组的复制.zip22.java数组的复制.zip22.java数组的复制.zip22.java数组...
20.java数组空间分配.zip20.java数组空间分配.zip20.java数组空间分配.zip20.java数组空间分配.zip20.java数组空间分配.zip20.java数组空间分配.zip20.java数组空间分配.zip20.java数组空间分配.zip20.java数组空间...
java 数组求和计算 java 数组求和计算 java 数组求和计算
第03讲 JAVA数组.ppt第03讲 JAVA数组.ppt第03讲 JAVA数组.ppt第03讲 JAVA数组.ppt第03讲 JAVA数组.ppt第03讲 JAVA数组.ppt