Ronaldo

• 于 Read

java sort 方法源码学习

      在学习《Thinking in java》集合一章时,快到末尾时讲解了排序和搜索中用到了sort(),点进去看了下源码,发现第一遍看起来还有点不甚了解,遂专开一篇来学习理解。

一、sort(byte[] a, int left, int right)

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
package com.lizz.set;
import java.util.Arrays;
import java.util.Random;
public class Test222 {
	static Random r = new Random();
	public static void main(String[] args) {
		byte[] b = new byte[15];
		for(int i = 0; i < b.length; i++) {
			System.out.println("b[" + i + "] = " +b[i]);
		}
		r.nextBytes(b);
		for(int i = 0; i < b.length; i++) {
			System.out.println("b[" + i + "] = " +b[i]);
		}
		Arrays.sort(b);
		for(int i = 0; i < b.length; i++) {
			System.out.println("b[" + i + "] = " +b[i]);
		}
	}	
}

      上述代码中b初始化一个byte类型的数组,初始化时由于没有赋值,默认是0。随后调用了r.nextBytes(b)对b进行了赋值。紧接着直接Arrays.sort(b)排序成功。那么sort()是如何实现的呢?看下源码：
Arrays.class

1
2
3
public static void sort(byte[] a) {
    DualPivotQuicksort.sort(a, 0, a.length - 1);
}

Byte.class

1
public static final byte   MIN_VALUE = -128;

DualPivotQuicksort.class

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
private static final int COUNTING_SORT_THRESHOLD_FOR_BYTE = 29;
private static final int NUM_BYTE_VALUES = 1 << 8;
static void sort(byte[] a, int left, int right) {
    // Use counting sort on large arrays
    if (right - left > COUNTING_SORT_THRESHOLD_FOR_BYTE) {
        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);
        }
    } else { // Use insertion sort on small arrays
         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;
        }
    }
}

      Arrays.class里面的sort(byte[] a)直接调用了DualPivotQuicksort.sort(a, 0, a.length - 1),把传进来的byte类型的数组以及该数组最大下标传递进去。
      接下来着重分析static void sort(byte[] a, int left, int right)。老实说,一开始真没看懂这是啥玩意。网上百度了下,原来sort(byte[] a)里使用了计数排序和插入排序两种方法,当大于29时,便是计数排序否则用插入排序。计数排序可以看我这篇博客：https://lizhongzhen11.github.io/2018/03/30/%E8%AE%A1%E6%95%B0%E6%8E%92%E5%BA%8F/ 。
      学习完计数排序后再反过来看该方法,可能还不是立即能看懂的,这时候不妨将内部代码抽出来运行下。下面是我抽出来运行的部分代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
package com.lizz.set;
import java.util.Arrays;
import java.util.Random;
public class Test222 {
	static Random r = new Random();
	static void sort2(byte[] a, int left, int right) {
        // Use counting sort on large arrays
        if (right - left > 29) {
            int[] count = new int[256];
            for (int i = left - 1; ++i <= right; count[a[i] - (-128)]++);
            for(int i = 0; i < a.length; i++) {
            	System.out.print(a[i] + 128 + ";");
            }
            System.out.println();
            for(int i = 0; i < count.length; i++) {
            	System.out.print(count[i]); 
            }
        }
    }
	public static void main(String[] args) {
		byte[] b = new byte[31];
		r.nextBytes(b);
		for(int i = 0; i < b.length; i++) {
			System.out.print("b[" + i + "] = " +b[i] + ";");
		}
		System.out.println();
		sort2(b, 0, 30);
	}
}
  1. 首先是for (int i = left - 1; ++i <= right; count[a[i] - Byte.MIN_VALUE]++);这个for循环没看懂有什么用。我抽出来手动运行了一遍,猜测它可能是计数排序中用来计算重复值个数的,因为count[i]被改变了。根据实际打印输出,第二行输出的应该是改变后的count的下标值,以第一个输出15为例,它应该是下标15,而且在打印中输出了2次,那么在第三行从第一个开始数起(其实是从下标0开始数起),正好到下标15位置对于了2,所以网上没骗我,的确是计数排序的思想。(注意：由于b是通过r.nextBytes()随机产生的,所以每次打印输出并不一样,可以用自己实际打印输出的数值进行对比验证。)
  2. 接下来看看源码中的第三个for循环,通过打印输出,发现s应该是数组中相同值的个数,排好一个减去一个。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    public class Test222 {
    	static Random r = new Random();
    	static void sort2(byte[] a, int left, int right) {
            // Use counting sort on large arrays
            if (right - left > 29) {
                int[] count = new int[256];
                for (int i = left - 1; ++i <= right; count[a[i] - (-128)]++);
                for(int i = 0; i < a.length; i++) {
                	System.out.print(a[i] + 128 + ",");
                	System.out.print("a[" + i + "] = " + a[i] + ";");
                }
                System.out.println();
                for(int i = 0; i < count.length; i++) {
                	System.out.print(count[i]); // count[i] 对应 相同值在数组中的总数
                }
                System.out.println();
                for (int i = 256, k = right + 1; k > left; ) {
                	System.out.print("count["+ --i + "] = " + count[--i] + ",");
                    while (count[--i] == 0);
                    byte value = (byte) (i + (-128));
                    int s = count[i];
                    System.out.print("value = " + value + ",");
                    System.out.print("s = " + s + ";");
                    System.out.println();
                    do {
                        a[--k] = value;
                    } while (--s > 0); // 这里的s其实是用来判断是否有相同值的,如果有排好一个减去一个
                }
            }
        }
    	public static void main(String[] args) {
    		byte[] b = new byte[31];
    		r.nextBytes(b);
    		sort2(b, 0, 30);
    	}
    }
Newer Post

计数排序

摘抄自：https://www.cnblogs.com/developerY/p/3166462.html https://blog.csdn.net/gaoruxue918/article/details/61467416 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;& …

• 于 继续阅读
Older Post

快速排序和冒泡排序

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;最近空闲时间逛论坛发现,好多人在面试时问了排序算法,比如快速排序以及冒泡排序。我回想了下,依稀记得有什么for循环嵌套,然后就没了。这样可不好,不能工作了就忘了这些基础,会被淘汰的。所以又重新学习了下这两个算法,发现自己还是有 …

• 于 继续阅读