本文内容和代码均来自于《漫画算法》,小灰和大黄的对话,非常有趣味的一本书。现理论结合实践,做一下测试。
private static final int LEN = 20000;
void bubbleV1(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
for (int j = 0; j < arr.length - 1 - i; j++) {
int temp = 0;
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
log("第" + (i + 1) + "轮");
log(Arrays.toString(arr));
}
}
void bubbleV2(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
boolean isSorted = true;
for (int j = 0; j < arr.length - 1 - i; j++) {
int temp = 0;
log("compare " + arr[j] + " with " + arr[j + 1]);
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
isSorted = false;
}
}
if (isSorted) {
break;
}
log("第" + (i + 1) + "轮");
log(Arrays.toString(arr));
}
}
void bubbleV3(int[] arr) {
int lastExchangedIndex = 0;
int sortBorder = arr.length - 1;
for (int i = 0; i < arr.length - 1; i++) {
boolean isSorted = true;
for (int j = 0; j < sortBorder; j++) {
int temp = 0;
log("compare " + arr[j] + " with " + arr[j + 1]);
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
isSorted = false;
lastExchangedIndex = j;
}
}
sortBorder = lastExchangedIndex;
log("border:" + sortBorder);
if (isSorted) {
break;
}
log("第" + (i + 1) + "轮");
log(Arrays.toString(arr));
}
}
void bubbleV4(int[] arr) {
int temp = 0;
for (int i = 0; i < arr.length / 2; i++) {
boolean isSorted = true;
for (int j = i; j < arr.length - 1 - i; j++) {
log("compare " + arr[j] + " with " + arr[j + 1]);
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
isSorted = false;
}
}
if (isSorted) {
break;
}
log("第" + (i + 1) + "轮");
log(Arrays.toString(arr));
isSorted = true;
for (int k = arr.length - 1 - i; k > i; k--) {
if (arr[k] < arr[k - 1]) {
temp = arr[k];
arr[k] = arr[k - 1];
arr[k - 1] = temp;
isSorted = false;
}
}
if (isSorted) {
break;
}
log("第" + (i + 2) + "轮");
log(Arrays.toString(arr));
}
}
@Test
public void test() {
int[] arr = { 2, 3, 4, 5, 6, 7, 8, 1 };
bubbleV4(arr);
log(Arrays.toString(arr));
}
@Test
public void test2() {
int[] arr2 = new int[LEN];
Random random = new Random();
for (int i = 0; i < LEN; i++) {
arr2[i] = random.nextInt(100);
}
long begin, end;
begin = System.currentTimeMillis();
bubbleV1(arr2);
end = System.currentTimeMillis();
System.out.println(end - begin);
begin = System.currentTimeMillis();
bubbleV2(arr2);
end = System.currentTimeMillis();
System.out.println(end - begin);
begin = System.currentTimeMillis();
bubbleV3(arr2);
end = System.currentTimeMillis();
System.out.println(end - begin);
begin = System.currentTimeMillis();
bubbleV4(arr2);
end = System.currentTimeMillis();
System.out.println(end - begin);
}
void log(String x) {
if (false) {
System.out.println(x);
}
}
分别用1万个元素和2万个整型数据做测试,结果如下
方法版本 | 数组长度(万) | 耗时(ms) |
---|
1 | 1 | 2833 |
2 | 1 | 3 |
3 | 1 | 2 |
4 | 1 | 2 |
1 | 2 | 10475 |
2 | 2 | 4 |
3 | 2 | 3 |
4 | 2 | 3 |
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)