バブルソートの最適化の改善
9221 ワード
バブルソート:小さいものから大きいものまで、各ソートは、ソートされていないシーケンスの最大値を最後にします.
private static int[] bubbleSort(int[] ints) {
int len = ints.length;
for (int i = 0; i < len; i++) {
for (int j = 1; j < len - i; j++) {
if (ints[j - 1] > ints[j]) {
int temp = ints[j];
ints[j] = ints[j-1];
ints[j-1] = temp;
}
}
}
return ints;
}
， ， 12345987 12345 ， ， 。
1： flag， flag=true， false。
private static int[] bubbleSort1(int[] ints) {
int len = ints.length;
boolean flag = true;
while (flag) {
flag = false;
for (int i = 1; i < len; i++) {
if (ints[i - 1] > ints[i]) {
int temp = ints[i];
ints[i] = ints[i-1];
ints[i-1] = temp;
flag = true;
}
}
len -- ;
}
return ints;
}
， 。 10000 ， 1000 ， 9000 100 。 ， 1000 ， 9000 ， 。 9000 ， 。
2： flag， ， flag ， 。
private static int[] bubbleSort2(int[] ints) {
int len = ints.length;
int flag = len;
while (flag>0) {// flag>0
flag = 0;
for (int i = 1; i < len; i++) {
if (ints[i - 1] > ints[i]) { //
int temp = ints[i];
ints[i] = ints[i-1];
ints[i-1] = temp;
flag = i; //
}
}
len = flag;//
}
return ints;
}
： for 10000 ， 1000 ， 9000 。
：
int[] ints = new int[10000];
// 10000 1000 ， 9000 。
for (int i = 0; i < 10000; i++) {
if (i<=1000) ints[i] = 1000-i;
else ints[i] = i;
}
System.out.println(" ：");
System.out.println(Arrays.toString(ints));
System.out.println(" ：");
// 3 ，
long startTime = System.currentTimeMillis();//
System.out.println(Arrays.toString(bubbleSort(ints))); // bubbleSort(ints)
//bubbleSort(ints);
long endTime = System.currentTimeMillis();//
System.out.println(" ："+(endTime-startTime)+"ms");// =
：
：bubbleSort
：100ms
：bubbleSort1（ ， bubbleSort bubbleSort1）
：30ms
：bubbleSort2（ ， bubbleSort bubbleSort2）
：13ms
， 90ms。 ， 。
。