排序算法的Java实现全攻略

Collections.sort()

Java的排序可以用Collections.sort() 排序函数实现。
用Collections.sort方法对list排序有两种方法：
第一种是list中的对象实现Comparable接口，如下：

public class User implements 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 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 list = new ArrayList();
    //此处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重载方法来实现，例如：

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 list = new ArrayList();
    list.add(user2);
    list.add(user1);
    
    Collections.sort(list,new Comparator(){
      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]; 
      } 
    } 
  } 

堆排序

   
  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); 
    } 
  } 
   
   
  private static void buildMaxHeap(int A[], int n) { 
    for (int i = (n - 2) / 2; i >= 0; i--) { 
      maxheapIfy(A, i, 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); 
      } 
    } 
   
     
    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]; 
      } 
    } 
   
     
    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 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); 
      } 
    } 
   
     
    private static void buildMaxHeap(int A[], int n) { 
      for (int i = (n - 2) / 2; i >= 0; i--) { 
 maxheapIfy(A, i, 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 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]; 
 } 
      } 
    } 
   
     
    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 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 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]); 
 } 
      } 
    } 
  }