这篇文章展示了如何用Java编写Selection排序程序。

选择排序也是类似于气泡排序的就地排序算法，该算法通过比较和交换每个遍历中的元素来工作。

选择排序算法

选择排序的工作方式如下：

• 从最左侧的元素(索引0)开始，然后将其与右侧的元素进行比较，以查看是否有任何元素小于该元素。如果是，则此新元素将成为该迭代中进行进一步比较的最低元素。
• 在迭代结束时，我们将获得最低元素的索引。
• 用最低的元素交换最低的元素。因此，在第一遍结束时，我们将在最低位置拥有最低的元素。
• 在下一个过程中，从索引1开始，然后再次执行相同的过程。

例如，如果array为{5，4，7，1，8}，则从索引0处的元素开始，并将其与相邻元素进行比较。

第一次通过后，我们将获得最低元素的索引，然后将其与索引为0的元素交换。这将结束第一遍。

在第二遍中，从4(索引1的元素)开始，然后再次比较元素。

选择排序Java程序

public class SelectionSort {
  public static void main(String[] args) {
    int[] arr = {25, 34, 10, 7, 15, 92, 53, 72, 39, 45};
    System.out.println("Original array- " + Arrays.toString(arr));
    int[] sortedArray = selectionSort(arr);
    System.out.println("Sorted array- " + Arrays.toString(sortedArray));
  }
	
  private static int[] selectionSort(int[] arr){
    int index;
    for(int i = 0; i < arr.length - 1; i++){
      index = i;
      for(int j = i+1; j < arr.length; j++){
        //if lower than the current lowest assign this index
        if(arr[j] < arr[index]){
          index = j;
        }
      }
      // swap so that smallest element in this pass
      // is at its proper place
      swapElements(i, index, arr);
    }
    return arr;
  }
    
  private static void swapElements(int index, int lowest, int[] arr){
    int temp = arr[index];
    arr[index] = arr[lowest];
    arr[lowest] = temp;
  }
}

输出：

Original array- [25, 34, 10, 7, 15, 92, 53, 72, 39, 45]
Sorted array- [7, 10, 15, 25, 34, 39, 45, 53, 72, 92]

选择排序空间和时间复杂度

选择排序的时间复杂度为O(N2)，与冒泡排序的时间复杂度相同，但选择排序所需的交换次数比冒泡排序的次数少。

不需要额外的空间，因此Selection排序的空间复杂度为O(1)。