Java深入篇~03.数组的排序算法(JDK1.8)

数组的排序算法(JDK1.8)
上一篇文章

数组

       数组与其他容器的区别有三大方面:效率,类型和保存基本类型的能力。在Java中,数组是一种效率最高的存储和随机访问对象引用序列的方式。数组是一个简单的线序序列。数组的优点是访问元素的速度会非常快,但代价是一旦确定了容器的大小,便不可再改变。可能有人会建议使用ArrayList,因为它可以通过创建新的实例然后把旧的实例传进去,从而达到扩容。就像本人上一篇文章关于StringBuilder数据结构一样,但我们要知道它们的底层都是基于数组的。所以说List之前我们会先说到数组。

       无论使用哪种类型的数组,数组标识符其实只是一个引用,指向堆中创建的一个真实对象。这个对象用于保存指向其他对象的引用。可以作为数组初始化语法一部分隐式地创建此对象,或者用new表达式显式的创建。不管是基本数据类型的数组还是引用数据类型的数组在使用上基本都相同

       在C/C++中,你无法返回一个数组,只能返回指向数组的指针,但是这样子会造成数组的生命周期变得困难。容易产生内存泄漏问题。而在Java中却可以直接返回一个数组。需要的时候它存在,不需要时垃圾处理器会清理掉它

Arrays

       Arrays是专门用来操作数组的一个工具类。由于我们使用数组的时候,会经常需要一些对里面元素产生变更的操作。为了省的程序员去重复写算法,所以Java里面已经提供好了工具类。在Arrays类中的方法基本上都是静态的,因此我们不需要去new一个对象。

sort方法
byte型数组

       Arrays.sort方法可以根据数组的大小和类型从而实现不同的排序。当数组的类型为byte数组时的长度小于29的时候,则会使用插入排序

   		for (int i = left, j = i; i < right; j = ++i) {
byte ai = a[i + 1];
while (ai < a[j]) {
a[j + 1] = a[j];
if (j-- == left) {
break;
}
}
a[j + 1] = ai;
}

       大于29的时候则使用计数排序

	int[] count = new int[NUM_BYTE_VALUES];

for (int i = left - 1; ++i <= right;
count[a[i] - Byte.MIN_VALUE]++
);
for (int i = NUM_BYTE_VALUES, k = right + 1; k > left; ) {
while (count[--i] == 0);
byte value = (byte) (i + Byte.MIN_VALUE);
int s = count[i];

do {
a[--k] = value;
} while (--s > 0);
}

int型数组

       当数组的类型是int的时候,如果数组的长度小于47则会使用插入排序

if (leftmost) {
for (int i = left, j = i; i < right; j = ++i) {
int ai = a[i + 1];
while (ai < a[j]) {
a[j + 1] = a[j];
if (j-- == left) {
break;
}
}
a[j + 1] = ai;
}

       如果大于47小于286,则会使用快速排序

    do {
if (left >= right) {
return;
}
} while (a[++left] >= a[left - 1]);

for (int k = left; ++left <= right; k = ++left) {
int a1 = a[k], a2 = a[left];

if (a1 < a2) {
a2 = a1; a1 = a[left];
}
while (a1 < a[--k]) {
a[k + 2] = a[k];
}
a[++k + 1] = a1;

while (a2 < a[--k]) {
a[k + 1] = a[k];
}
a[k + 1] = a2;
}
int last = a[right];

while (last < a[--right]) {
a[right + 1] = a[right];
}
a[right + 1] = last;
}

       当长度大于286的时候则会使用归并排序

        int[] run = new int[MAX_RUN_COUNT + 1];
int count = 0; run[0] = left;

for (int k = left; k < right; run[count] = k) {
if (a[k] < a[k + 1]) {
while (++k <= right && a[k - 1] <= a[k]);
} else if (a[k] > a[k + 1]) {
while (++k <= right && a[k - 1] >= a[k]);
for (int lo = run[count] - 1, hi = k; ++lo < --hi; ) {
int t = a[lo]; a[lo] = a[hi]; a[hi] = t;
}
} else {
for (int m = MAX_RUN_LENGTH; ++k <= right && a[k - 1] == a[k]; ) {
if (--m == 0) {
sort(a, left, right, true);
return;
}
}
}

float型数组

       当数组是float型的时候就比较复杂了。因为它会分成不同的阶段来进行操作

第一阶段

       将非float的元素移动到末尾,isNaN方法在这里就是判断一个元素是否为float

 while (left <= right && Float.isNaN(a[right])) {
--right;
}
for (int k = right; --k >= left; ) {
float ak = a[k];
if (ak != ak) {
a[k] = a[right];
a[right] = ak;
--right;
}
}

public static boolean isNaN(float v) {
return (v != v);
}

第二阶段

       只要是float的元素就会根据规则进行排序

private static void doSort(float[] a, int left, int right,
float[] work, int workBase, int workLen) {
if (right - left < QUICKSORT_THRESHOLD) {
sort(a, left, right, true);
return;
}

  int[] run = new int[MAX_RUN_COUNT + 1];
int count = 0; run[0] = left;

for (int k = left; k < right; run[count] = k) {
if (a[k] < a[k + 1]) {
while (++k <= right && a[k - 1] <= a[k]);
} else if (a[k] > a[k + 1]) {
while (++k <= right && a[k - 1] >= a[k]);
for (int lo = run[count] - 1, hi = k; ++lo < --hi; ) {
float t = a[lo]; a[lo] = a[hi]; a[hi] = t;
}
} else {
for (int m = MAX_RUN_LENGTH; ++k <= right && a[k - 1] == a[k]; ) {
if (--m == 0) {
sort(a, left, right, true);
return;
}
}
}
if (++count == MAX_RUN_COUNT) {
sort(a, left, right, true);
return;
}
}
if (run[count] == right++) {
run[++count] = right;
} else if (count == 1) {
return;
}

byte odd = 0;
for (int n = 1; (n <<= 1) < count; odd ^= 1);

     float[] b;
int ao, bo;
int blen = right - left;
if (work == null || workLen < blen || workBase + blen > work.length) {
work = new float[blen];
workBase = 0;
}
if (odd == 0) {
System.arraycopy(a, left, work, workBase, blen);
b = a;
bo = 0;
a = work;
ao = workBase - left;
} else {
b = work;
ao = 0;
bo = workBase - left;
}

for (int last; count > 1; count = last) {
for (int k = (last = 0) + 2; k <= count; k += 2) {
int hi = run[k], mi = run[k - 1];
for (int i = run[k - 2], p = i, q = mi; i < hi; ++i) {
if (q >= hi || p < mi && a[p + ao] <= a[q + ao]) {
b[i + bo] = a[p++ + ao];
} else {
b[i + bo] = a[q++ + ao];
}
}
run[++last] = hi;
}
if ((count & 1) != 0) {
for (int i = right, lo = run[count - 1]; --i >= lo;
b[i + bo] = a[i + ao]
);
run[++last] = right;
}
float[] t = a; a = b; b = t;
int o = ao; ao = bo; bo = o;
}
}

       当长度小于47的时候则是插入排序

	if (length < INSERTION_SORT_THRESHOLD) {
if (leftmost) {
for (int i = left, j = i; i < right; j = ++i) {
int ai = a[i + 1];
while (ai < a[j]) {
a[j + 1] = a[j];
if (j-- == left) {
break;
}
}
a[j + 1] = ai;
}
} else {
do {
if (left >= right) {
return;
}
} while (a[++left] >= a[left - 1]);
for (int k = left; ++left <= right; k = ++left) {
int a1 = a[k], a2 = a[left];

if (a1 < a2) {
a2 = a1; a1 = a[left];
}
while (a1 < a[--k]) {
a[k + 2] = a[k];
}
a[++k + 1] = a1;

while (a2 < a[--k]) {
a[k + 1] = a[k];
}
a[k + 1] = a2;
}
int last = a[right];

while (last < a[--right]) {
a[right + 1] = a[right];
}
a[right + 1] = last;
}
return;
}

阶段3:最后的排序

		int hi = right;

while (left < hi) {
int middle = (left + hi) >>> 1;
float middleValue = a[middle];

if (middleValue < 0.0f) {
left = middle + 1;
} else {
hi = middle;
}
}
while (left <= right && Float.floatToRawIntBits(a[left]) < 0) {
++left;
}

for (int k = left, p = left - 1; ++k <= right; ) {
float ak = a[k];
if (ak != 0.0f) {
break;
}
if (Float.floatToRawIntBits(ak) < 0) { // ak is -0.0f
a[k] = 0.0f;
a[++p] = -0.0f;
}
}

double类型数组

       和float大同小异,这里就省略了~

String类型数组

       由于在Java里String是一个类而并非关键字,因此到了底层也就变成了Object类型数组的排序

public static void sort(Object[] a) {
if (LegacyMergeSort.userRequested)
legacyMergeSort(a);
else
ComparableTimSort.sort(a, 0, a.length, null, 0, 0);
}

       这里的排序会用到ComparableTimSort类,关于ComparableTimSort类的介绍翻译是这样子的:这是{@link TimSort}的一个近似副本,修改后可与一起使用实现{@link Comparable}的对象数组,而不是使用显式比较器。如果您正在使用优化虚拟机,您可能会发现与TimSort和只返回{@code((Comparable)first).compareTo(Second)}的比较器。如果是这种情况,最好删除可比较的时间排序到消除代码重复。

static void sort(Object[] a, int lo, int hi, Object[] work, int workBase, int workLen) {
assert a != null && lo >= 0 && lo <= hi && hi <= a.length;

int nRemaining = hi - lo;
if (nRemaining < 2)
return;
if (nRemaining < MIN_MERGE) {
int initRunLen = countRunAndMakeAscending(a, lo, hi);
binarySort(a, lo, hi, lo + initRunLen);
return;
}
ComparableTimSort ts = new ComparableTimSort(a, work, workBase, workLen);
int minRun = minRunLength(nRemaining);
do {
int runLen = countRunAndMakeAscending(a, lo, hi);
if (runLen < minRun) {
int force = nRemaining <= minRun ? nRemaining : minRun;
binarySort(a, lo, lo + force, lo + runLen);
runLen = force;
}
ts.pushRun(lo, runLen);
ts.mergeCollapse();

lo += runLen;
nRemaining -= runLen;
} while (nRemaining != 0);
assert lo == hi;
ts.mergeForceCollapse();
assert ts.stackSize == 1;
}

char类型数组

       当char类型数组长度小于3200的时候就会调用dosort方法,和float排序的第二阶段很相似

private static void doSort(char[] a, int left, int right,
char[] work, int workBase, int workLen) {
if (right - left < QUICKSORT_THRESHOLD) {
sort(a, left, right, true);
return;
}
int[] run = new int[MAX_RUN_COUNT + 1];
int count = 0; run[0] = left;

for (int k = left; k < right; run[count] = k) {
if (a[k] < a[k + 1]) {
while (++k <= right && a[k - 1] <= a[k]);
} else if (a[k] > a[k + 1]) {
while (++k <= right && a[k - 1] >= a[k]);
for (int lo = run[count] - 1, hi = k; ++lo < --hi; ) {
char t = a[lo]; a[lo] = a[hi]; a[hi] = t;
}
} else {
for (int m = MAX_RUN_LENGTH; ++k <= right && a[k - 1] == a[k]; ) {
if (--m == 0) {
sort(a, left, right, true);
return;
}
}
}
if (++count == MAX_RUN_COUNT) {
sort(a, left, right, true);
return;
}
}

       当长度大于3200的时候则会使用计数排序

	if (right - left > COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR) {
int[] count = new int[NUM_CHAR_VALUES];

for (int i = left - 1; ++i <= right;
count[a[i]]++
);
for (int i = NUM_CHAR_VALUES, k = right + 1; k > left; ) {
while (count[--i] == 0);
char value = (char) i;
int s = count[i];

do {
a[--k] = value;
} while (--s > 0);
}
}

原创:https://www.panoramacn.com
源码网提供WordPress源码,帝国CMS源码discuz源码,微信小程序,小说源码,杰奇源码,thinkphp源码,ecshop模板源码,微擎模板源码,dede源码,织梦源码等。

专业搭建小说网站,小说程序,杰奇系列,微信小说系列,app系列小说

Java深入篇~03.数组的排序算法(JDK1.8)

免责声明,若由于商用引起版权纠纷,一切责任均由使用者承担。

您必须遵守我们的协议,如果您下载了该资源行为将被视为对《免责声明》全部内容的认可-> 联系客服 投诉资源
www.panoramacn.com资源全部来自互联网收集,仅供用于学习和交流,请勿用于商业用途。如有侵权、不妥之处,请联系站长并出示版权证明以便删除。 敬请谅解! 侵权删帖/违法举报/投稿等事物联系邮箱:2640602276@qq.com
未经允许不得转载:书荒源码源码网每日更新网站源码模板! » Java深入篇~03.数组的排序算法(JDK1.8)
关注我们小说电影免费看
关注我们,获取更多的全网素材资源,有趣有料!
120000+人已关注
分享到:
赞(0) 打赏

评论抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

您的打赏就是我分享的动力!

支付宝扫一扫打赏

微信扫一扫打赏