[자바] 자바. util. Arrays 에서 사용 하 는 sort 에서 사용 하 는 알고리즘 (회전)

http://book.douban.com/annotation/15154366/
Q: java.util.Arrays      sort         ？

 

A: java Arrays.sort         ，quick sort      merge sort。

 

Q:            ？

 

A: quick sort             （int, short, long, float, double ）  ，   merge sort            。

 

Q: quick sort           merge sort  ，       quick sort ？

 

A:     ，      ，       。                 quick sort      ，  merge sort   stable  。    stable                              （   ）。        ，       。       ，         ，                   ，                       ；                           ，  （       ）        ，       ，         。

 

merge sort

 

（1）         O(nlgn)；

 

（2）         O(nlgn)；

 

（3）       O(1)。

 

quick sort

 

（1）         O(n^2)；

 

（2）         O(nlgn)；

 

（3）       O(n)。

 

      java.util.Arrays.sort(arrayName)       ，    ：

 

/* constant variables */

final int NUM = 10;

final int OFFSET = 2;

final int LOOP = 100000;

/* arrays */

int[][] array = new int[NUM][];

long[] start = new long[NUM];

long[] end = new long[NUM];

long[] cost = new long[NUM];

/* initialization */

for (int i = 0; i < array.length; ++i) {

array[i] = new int[1 << (i * OFFSET)];

}

for (int i = 0; i < array.length; ++i) {

for (int j = 0; j < array[i].length; ++j) {

array[i][j] = (int)(Math.random());

}

}

/* sorting */

for (int count = 0; count < LOOP; ++count) {

for (int i = 0; i < array.length; ++i) {

start[i] = System.currentTimeMillis();

Arrays.sort(array[i]);

end[i] = System.currentTimeMillis();

cost[i] += end[i] - start[i];

}

}

/* output */

for (int i = 0; i < cost.length; ++i) {

System.out.println(

"n = " + array[i].length +

", time = " + cost[i] / 1000.0

);

}

 

     n   ，    10    ，  10        ，    ：

 

n = 1, time = 0.013s

 

n = 4, time = 0.011s

 

n = 16, time = 0.029s

 

n = 64, time = 0.066s

 

n = 256, time = 0.198s

 

n = 1024, time = 0.797s

 

n = 4096, time = 3.005s

 

n = 16384, time = 12.101s

 

n = 65536, time = 48.101s

 

n = 262144, time = 192.174s
http://book.douban.com/annotation/15154366/

다음으로 전송:https://www.cnblogs.com/Phoebe815/p/4249340.html