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()); } } }

输出结果如下

a b

第二种方法是根据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()); } } }

输出结果如下

a b

前者代码结构简单，但是只能根据固定的属性排序，后者灵活，可以临时指定排序项，但是代码不够简洁

择优用之。

常用排序算法

下面来看几种经典排序算法的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("%dn", A[i]); } else { System.out.printf("%d ", A[i]); } } } }