排序算法的Java實現全攻略

Collections.sort()

Java的排序可以用Collections.sort() 排序函數實現。
用Collections.sort方法對list排序有兩種方法：
第一種是list中的對象實現Comparable接口，如下：

 /*** 根據order對User排序*/public class User implements Comparable<User>{ private String name; private Integer order; public String getName() { return name; } public void setName(String name) { this.name = name; } public Integer getOrder() { return order; } public void setOrder(Integer order) { this.order = order; } public int compareTo(User arg0) { return this.getOrder().compareTo(arg0.getOrder() ); }}

測試一下：

 public class Test{ public static void main(String[] args) { User user1 = new User(); user1.setName("a"); user1.setOrder(1); User user2 = new User(); user2.setName ("b"); user2.setOrder(2); List<User> list = new ArrayList<User>(); //此處add user2再add user1 list.add(user2); list.add(user1); Collections.sort(list); for(User u : list){ System.out.println(u.getName()); } }}

輸出結果如下

ab

第二種方法是根據Collections.sort重載方法來實現，例如：

 /*** 根據order對User排序*/public class User { //此處無需實現Comparable接口private String name; private Integer order; public String getName() { return name; } public void setName(String name) { this .name = name; } public Integer getOrder() { return order; } public void setOrder(Integer order) { this.order = order; }}

主類中這樣寫即可：

 public class Test{ public static void main(String[] args) { User user1 = new User(); user1.setName("a"); user1.setOrder(1); User user2 = new User(); user2.setName ("b"); user2.setOrder(2); List<User> list = new ArrayList<User>(); list.add(user2); list.add(user1); Collections.sort(list,new Comparator< User>(){ public int compare(User arg0, User arg1) { return arg0.getOrder().compareTo(arg1.getOrder()); } }); for(User u : list){ System.out.println( u.getName()); } }}

輸出結果如下

ab

前者代碼結構簡單，但是只能根據固定的屬性排序，後者靈活，可以臨時指定排序項，但是代碼不夠簡潔

擇優用之。

常用排序算法
下面來看幾種經典排序算法的Java代碼實踐：

冒泡排序

public static void bubbleSort(int A[], int n) { int i, j; for (i = 0; i < n - 1; i ++) { for (j = 0; j < n - i - 1; j ++) { if (A[j] > A[j + 1]) { A[j] = A[j] ^ A[j + 1]; A[j + 1] = A[j] ^ A [j + 1]; A[j] = A[j] ^ A[j + 1]; } } } }

直接插入排序

public static void insertSort(int A[], int n) { int i, j, tmp; for (i = 1; i < n; i++) { tmp = A[i]; for (j = i - 1; j >= 0; j--) { if (A[j] > tmp) { A[j + 1] = A[j]; } else { break; } } A[j + 1] = tmp; } }

直接選擇排序

public static void selectSort(int A[], int n) { int i, j, loc; for (i = 0; i < n; i++) { loc = i; for (j = i + 1; j < n; j++) { if (A[j] < A[loc]) { loc = j; } } if (loc != i) { A[i] = A[i] ^ A[loc]; A[loc] = A[i] ^ A[loc]; A[i] = A[i] ^ A[loc]; } } }

堆排序

/** * 堆排序（從小到大） * * @param A * @param n */ public static void heapSort(int A[], int n) { int tmp; // 構建大根堆buildMaxHeap(A, n) ; for (int j = n - 1; j >= 1; j--) { tmp = A[0]; A[0] = A[j]; A[j] = tmp; maxheapIfy(A, 0, j); } } /** * 構建大根堆* * @param A * @param n */ private static void buildMaxHeap(int A[], int n) { for (int i = (n - 2) / 2; i >= 0; i--) { maxheapIfy(A, i, n); } } /** * 維護從下標i開始的最大堆* * @param A * @param i * @param n */ private static void maxheapIfy(int A[], int i, int n) { int left, right, loc; while (i < n) { left = 2 * i + 1; right = 2 * i + 2; loc = i; if (left < n && A[left] > A[i]) { i = left; } if (right < n && A[right] > A[i]) { i = right; } if (loc != i ) { A[i] = A[loc] ^ A[i]; A[loc] = A[loc] ^ A[i]; A[i] = A[loc] ^ A[i]; } else { break; } } }

快速排序

public static void quickSort(int A[], int bt, int ed) { if (bt < ed) { int pivot = pivotPartition(A, bt, ed); quickSort(A, bt, pivot - 1); quickSort(A , pivot + 1, ed); } } private static void swapVar(int A[], int bt, int ed) { int mid = bt + (ed - bt) / 2; if (mid != bt) { A[ bt] = A[bt] ^ A[mid]; A[mid] = A[bt] ^ A[mid]; A[bt] = A[bt] ^ A[mid]; } } private static int pivotPartition( int A[], int bt, int ed) { // 取中間值作為stand，防止數組有序出現O(n^2)情況swapVar(A, bt, ed); int stand = A[bt]; while (bt < ed) { while (bt < ed && A[ed] >= stand) { ed--; } if (bt < ed) { A[bt++] = A[ed]; } while (bt < ed && A[bt] <= stand) { bt++; } if (bt < ed) { A[ed--] = A[bt]; } } A[bt] = stand; return bt; }

歸併排序

public static void mergeSort(int A[], int bt, int ed) { if (bt < ed) { int mid = bt + (ed - bt) / 2; mergeSort(A, bt, mid); mergeSort(A, mid + 1, ed); mergeArray(A, bt, mid, ed); } } private static void mergeArray(int A[], int bt, int mid, int ed) { int i, j, k, len = ed - bt + 1; int tmp[] = new int[len]; for (i = bt, j = mid + 1, k = 0; i <= mid && j <= ed; k++) { if (A[i ] <= A[j]) { tmp[k] = A[i++]; } else { tmp[k] = A[j++]; } } while (i <= mid) { tmp[k++] = A[i++ ]; } while (j <= ed) { tmp[k++] = A[j++]; } for (i = 0; i < k; i++) { A[bt + i] = tmp[i]; } }

測試程序

來將以上算法歸納總結一下：

 import java.util.Scanner; public class JavaSort { public static void main(String args[]) { Scanner cin = new Scanner(System.in); int A[], n; while (cin.hasNext()) { n = cin.nextInt(); A = new int[n]; for (int i = 0; i < n; i++) { A[i] = cin.nextInt(); } // bubbleSort(A, n); // insertSort(A, n); // selectSort(A, n); // heapSort(A, n); // quickSort(A, 0, n - 1); mergeSort(A, 0, n - 1) ; printArr(A); } } /** * 歸併排序* * @param A * @param bt * @param ed */ public static void mergeSort(int A[], int bt, int ed) { if (bt < ed) { int mid = bt + (ed - bt) / 2; mergeSort(A, bt, mid); mergeSort(A, mid + 1, ed); mergeArray(A, bt, mid, ed); } } / ** * 合併數組* * @param A * @param bt * @param mid * @param ed */ private static void mergeArray(int A[], int bt, int mid, int ed) { int i, j, k , len = ed - bt + 1; int tmp[] = new int[len]; for (i = bt, j = mid + 1, k = 0; i <= mid && j <= ed; k++) { if (A[i] <= A[j]) { tmp[k] = A[i++]; } else { tmp[k] = A[j++]; } } while (i <= mid) { tmp[k++] = A[i++]; } while (j <= ed) { tmp[k++] = A[j++]; } for (i = 0; i < k; i++) { A[bt + i] = tmp[i] ; } } /** * 快速排序* * @param A * @param bt * @param ed */ public static void quickSort(int A[], int bt, int ed) { if (bt < ed) { int pivot = pivotPartition(A, bt, ed); quickSort(A, bt, pivot - 1); quickSort(A, pivot + 1, ed); } } private static void swapVar(int A[], int bt, int ed) { int mid = bt + (ed - bt) / 2; if (mid != bt) { A[bt] = A[bt] ^ A[mid]; A[mid] = A[bt] ^ A[mid ]; A[bt] = A[bt] ^ A[mid]; } } /** * 快排尋找基準點位置* * @param A * @param bt * @param ed * @return */ private static int pivotPartition(int A[], int bt, int ed) { // 取中間值作為stand，防止數組有序出現O(n^2)情況swapVar(A, bt, ed); int stand = A[bt] ; while (bt < ed) { while (bt < ed && A[ed] >= stand) { ed--; } if (bt < ed) { A[bt++] = A[ed]; } while (bt < ed && A[bt] <= stand) { bt++; } if (bt < ed) { A[ed--] = A[bt]; } } A[bt] = stand; return bt; } /** *堆排序（從小到大） * * @param A * @param n */ public static void heapSort(int A[], int n) { int tmp; // 構建大根堆buildMaxHeap(A, n); for (int j = n - 1; j >= 1; j--) { tmp = A[0]; A[0] = A[j]; A[j] = tmp; maxheapIfy(A, 0, j); } } /** * 構建大根堆* * @param A * @param n */ private static void buildMaxHeap(int A[], int n) { for (int i = (n - 2) / 2; i >= 0 ; i--) { maxheapIfy(A, i, n); } } /** * 維護從下標i開始的最大堆* * @param A * @param i * @param n */ private static void maxheapIfy( int A[], int i, int n) { int left, right, loc; while (i < n) { left = 2 * i + 1; right = 2 * i + 2; loc = i; if (left < n && A[left] > A[i]) { i = left; } if (right < n && A[right] > A[i]) { i = right; } if (loc != i) { A[ i] = A[loc] ^ A[i]; A[loc] = A[loc] ^ A[i]; A[i] = A[loc] ^ A[i]; } else { break; } } } /** * 直接選擇排序* * @param A * @param n */ public static void selectSort(int A[], int n) { int i, j, loc; for (i = 0; i < n; i++) { loc = i; for (j = i + 1; j < n; j++) { if (A[j] < A[loc]) { loc = j; } } if (loc != i) { A [i] = A[i] ^ A[loc]; A[loc] = A[i] ^ A[loc]; A[i] = A[i] ^ A[loc]; } } } /** * 直接插入排序* * @param A * @param n */ public static void insertSort(int A[], int n) { int i, j, tmp; for (i = 1; i < n; i++) { tmp = A[i]; for (j = i - 1; j >= 0; j--) { if (A[j] > tmp) { A[j + 1] = A[j]; } else { break ; } } A[j + 1] = tmp; } } /** * 冒泡排序* * @param A * @param n */ public static void bubbleSort(int A[], int n) { int i, j ; for (i = 0; i < n - 1; i++) { for (j = 0; j < n - i - 1; j++) { if (A[j] > A[j + 1]) { A[ j] = A[j] ^ A[j + 1]; A[j + 1] = A[j] ^ A[j + 1]; A[j] = A[j] ^ A[j + 1] ; } } } } /** * 打印數組* * @param A */ public static void printArr(int A[]) { for (int i = 0; i < A.length; i++) { if (i == A.length - 1) { System.out.printf("%d/n", A[i]); } else { System.out.printf("%d ", A[i]); } } } }