排序算法的Java实现全攻略

/*** 根据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

/*** 根据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

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