Java List排序

在Java中，List是一種十分常見的數據結構，它可以存儲多個元素。但是，在某些情況下，我們需要對這些元素進行排序，以滿足不同的需求。那麼，在Java中，如何對List進行排序呢？本文將從多個方面進行闡述。

一、選擇排序

選擇排序是一種簡單的排序演算法，它的實現思想是：每次從待排序的數據中選擇最小（或最大）的一個元素，放到已排序的數據的末尾。這個過程不斷重複，直到所有元素都排序完畢。

下面是一個使用選擇排序對List進行排序的示例代碼：

public static void selectionSort(List<Integer> list) {
  int minIndex, temp;
  for (int i = 0; i < list.size() - 1; i++) {
    minIndex = i;
    for (int j = i + 1; j < list.size(); j++) {
      if (list.get(j) < list.get(minIndex)) {
        minIndex = j;
      }
    }
    if (minIndex != i) {
      temp = list.get(i);
      list.set(i, list.get(minIndex));
      list.set(minIndex, temp);
    }
  }
}

該方法接受一個List<Integer>類型的參數，使用選擇排序演算法進行排序。在選擇排序中，需要依次遍歷未排序的元素，找到其中的最小值，並將其放到已排序的元素末尾。在上述代碼中，我們使用兩個嵌套的for循環來實現這個過程。

二、快速排序

快速排序是一種常用的排序演算法，它的實現思想是：通過一趟排序將待排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的小，然後再按此方法對這兩部分數據分別進行快速排序。

下面是一個使用快速排序對List進行排序的示例代碼：

public static void quickSort(List<Integer> list) {
  if (list.size() <= 1) {
    return;
  }
  int pivot = list.get(0);
  List<Integer> low = new ArrayList<>();
  List<Integer> high = new ArrayList<>();
  for (int i = 1; i < list.size(); i++) {
    if (list.get(i) < pivot) {
      low.add(list.get(i));
    } else {
      high.add(list.get(i));
    }
  }
  quickSort(low);
  quickSort(high);
  list.clear();
  list.addAll(low);
  list.add(pivot);
  list.addAll(high);
}

該方法接受一個List<Integer>類型的參數，使用快速排序演算法進行排序。在快速排序中，需要選擇一個基準元素（pivot）作為分割點，將小於它的元素放入一個序列中，大於它的元素放入另一個序列中，然後分別對這兩個序列進行排序。在上述代碼中，我們使用遞歸的方式對low和high序列進行快速排序，並將它們合併到原始的list中。

三、歸併排序

歸併排序是一種基於分治思想的排序演算法，它的實現思想是：將待排序的數據分成兩部分，對這兩部分數據分別進行歸併排序，然後將排序好的兩部分數據歸併到一起。

下面是一個使用歸併排序對List進行排序的示例代碼：

public static void mergeSort(List<Integer> list) {
  if (list.size() <= 1) {
    return;
  }
  int middle = list.size() / 2;
  List<Integer> left = new ArrayList<>();
  List<Integer> right = new ArrayList<>();
  for (int i = 0; i < middle; i++) {
    left.add(list.get(i));
  }
  for (int i = middle; i < list.size(); i++) {
    right.add(list.get(i));
  }
  mergeSort(left);
  mergeSort(right);
  merge(left, right, list);
}

private static void merge(List<Integer> left, List<Integer> right, List<Integer> result) {
  int i = 0;
  int j = 0;
  while (i < left.size() && j < right.size()) {
    if (left.get(i) < right.get(j)) {
      result.set(i + j, left.get(i));
      i++;
    } else {
      result.set(i + j, right.get(j));
      j++;
    }
  }
  while (i < left.size()) {
    result.set(i + j, left.get(i));
    i++;
  }
  while (j < right.size()) {
    result.set(i + j, right.get(j));
    j++;
  }
}

該方法接受一個List<Integer>類型的參數，使用歸併排序演算法進行排序。在歸併排序中，需要將待排序的數據分成兩部分，對這兩部分數據分別進行排序，然後將排序好的兩部分數據歸併到一起。在上述代碼中，我們使用遞歸的方式對左右兩個子序列進行歸併排序，並在歸併過程中將它們合併到原始的list中。