關於氣泡排序的說明網路上很多，而且這應該是學校必教的項目，所以就不說明了~
如果有需要細項說明的話請參考這裡
為了測試執行的效率，所以設定了一個共1000個值的List給Bubble Sort做處理
第一種方法是過去學校教的，而第二種方法其實看起來沒什麼差，可是執行上出現15ms的差異
一、執行時間約62ms
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.Random;
import static java.util.Collections.swap;
public class BubbleSort {
public static void main(String[] args) throws InterruptedException {
long time1, time2;
time1 = System.currentTimeMillis();
List list = new ArrayList<>();
for(int i=0; i<1000; i++){
list.add(new Random().nextInt(1000));
}
Comparator compar = new Comparator() {
public int compare(Integer num1, Integer num2) {
return num1 - num2;
}
};
bubbleSort(list, compar);
System.out.println(list);
time2 = System.currentTimeMillis();
System.out.println((time2-time1) + "/ms");
}
public static void bubbleSort(List list, Comparator compar) {
for(int i = 0; i < list.size(); i++) {
for(int j = 0; j < list.size() - i - 1; j++) {
if(compar.compare(list.get(j + 1), list.get(j)) < 0) {
swap(list, j + 1, j);
}
}
}
}
}
二、執行時間約47ms
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.Random;
import static java.util.Collections.swap;
public class BubbleSort {
public static void main(String[] args) throws InterruptedException {
long time1, time2;
time1 = System.currentTimeMillis();
List list = new ArrayList<>();
for(int i=0; i<1000; i++){
list.add(new Random().nextInt(1000));
}
Comparator compar = new Comparator() {
public int compare(Integer num1, Integer num2) {
return num1 - num2;
}
};
bubbleSort(list, compar);
System.out.println(list);
time2 = System.currentTimeMillis();
System.out.println((time2-time1) + "/ms");
}
public static void bubbleSort(List list, Comparator compar) {
for(int i = 0; i < list.size(); i++) {
bubbleSwap(list, list.size() - i, compar);
}
}
public static void bubbleSwap(List list, int to, Comparator compar) {
for(int i = 0; i < to - 1; i++) {
if(compar.compare(list.get(i + 1), list.get(i)) < 0) {
swap(list, i + 1, i);
}
}
}
}
但在一些範例中會發現，List中的資料可能排序到一半就排完了，後面的資料雖然都沒有做到交換的動做，但還是一個一個做檢查
為了避免這些不必要的動作，要多加一個檢查，當資料完全沒做到交換的動做時List就視為排序完成並離迴圈
這樣執行的結果平均31~37ms就能執行完成
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.Random;
import static java.util.Collections.swap;
public class BubbleSort {
public static void main(String[] args) throws InterruptedException {
long time1, time2;
time1 = System.currentTimeMillis();
List list = new ArrayList<>();
for(int i=0; i<1000; i++){
list.add(new Random().nextInt(1000));
}
Comparator compar = new Comparator() {
public int compare(Integer num1, Integer num2) {
return num1 - num2;
}
};
bubbleSort(list, compar);
System.out.println(list);
time2 = System.currentTimeMillis();
System.out.println((time2-time1) + "/ms");
}
public static void bubbleSort(List list, Comparator compar) {
for(int i = 0; i < list.size(); i++) {
if(bubbleSwap(list, list.size() - i, compar)) break;
}
}
public static boolean bubbleSwap(List list, int to, Comparator compar) {
boolean complete = true;
for(int i = 0; i < to - 1; i++) {
if(compar.compare(list.get(i + 1), list.get(i)) < 0) {
swap(list, i + 1, i);
complete = false;
}
}
return complete;
}
}
最後是 Shark Sort 又稱為雙向氣泡排序法
以氣泡排序法為基礎做雙向排序，讓未排序的值集中到 List 中間
而雙向排序會讓中間未排序的部份快速減少，結束的時間自然也就提前了
而 Shark Sort 的執行速度則是穩穩的在31ms上下
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.Random;
import static java.util.Collections.swap;
public class BubbleSort {
public static void main(String[] args) throws InterruptedException {
long start, end;
start = System.currentTimeMillis();
List list = new ArrayList<>();
for(int i=0; i<1000; i++){
list.add(new Random().nextInt(1000));
}
Comparator com = new Comparator() {
public int compare(Integer num1, Integer num2) {
return num1 - num2;
}
};
sharkSort(list, com);
System.out.println(list);
end = System.currentTimeMillis();
System.out.println((end-start) + "/ms");
}
public static void sharkSort(List list, Comparator com) {
int left = 0;
int right = list.size() -1;
while(left < right){
right = leftToRight(list, left, right, com);
left = rightToLeft(list, left, right, com);
}
//上面的while也可以改寫成下面的for，但下面這樣的寫法不易閱讀所以不建議這樣寫
//for(int left = 0, right = list.size() - 1; left < right; right = leftToRight(list, left, right, com), left = rightToLeft(list, left, right, com));
}
public static int leftToRight(List list, int left, int right, Comparator com) {
int tag = left;
for(int i = left; i < right; i++) {
if(com.compare(list.get(i + 1), list.get(i)) < 0) {
swap(list, i + 1, i);
tag = i;
}
}
return tag;
}
public static int rightToLeft(List list, int left, int right, Comparator com) {
int tag = right;
for(int i = right; i > left; i--) {
if(com.compare(list.get(i), list.get(i - 1)) < 0) {
swap(list, i, i - 1);
tag = i;
}
}
return tag;
}
}
然而上面的方法只能給型態為 Integer 的資料使用
為了讓程式能夠 reuse，下面將它加入泛型的用法，使它可以排序其它型態的資料，並將 Sort 程式獨立出來
Main:
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.Random;
public class SortDemo {
public static void main(String[] args) {
List list = new ArrayList<>();
for(int i=0; i<1000; i++){
list.add(new Random().nextInt(1000));
}
Comparator com = new Comparator() {
public int compare(Integer num1, Integer num2) {
return num1 - num2;
}
};
list = new Sort().sharkSort(list, com);
System.out.println(list);
}
}
Sort:
import java.util.Comparator;
import java.util.List;
import static java.util.Collections.swap;
public class Sort {
public <T> List sharkSort(List<T> list, Comparator<? super T> com) {
int left = 0;
int right = list.size() -1;
while(left < right){
right = leftToRight(list, left, right, com);
left = rightToLeft(list, left, right, com);
}
return list;
}
private <T> int leftToRight(List<T> list, int left, int right, Comparator<? super T> com) {
int tag = left;
for(int i = left; i < right; i++) {
if(com.compare(list.get(i + 1), list.get(i)) < 0) {
swap(list, i + 1, i);
tag = i;
}
}
return tag;
}
private <T> int rightToLeft(List<T> list, int left, int right, Comparator<? super T> com) {
int tag = right;
for(int i = right; i > left; i--) {
if(com.compare(list.get(i), list.get(i - 1)) < 0) {
swap(list, i, i - 1);
tag = i;
}
}
return tag;
}
}
請先 登入 以發表留言。