排序算法的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());
    }
  }
}

输出结果如下

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("%d\n", A[i]);
        } else {
          System.out.printf("%d ", A[i]);
        }
      }
    }
  }