Java 选择排序

 Java 常见例子

选择排序的思想是在未排序数组中查找最小或最大元素，并将其放置在已排序数组中的正确位置。这将导致每次迭代后将已排序数组的长度增加 1，并将未排序数组的长度减少 1。

示例:

为了理解选择排序，让我们考虑一下未排序的数组 [1, 10, 23, -2] 并讨论按升序对数组进行排序所采取的每个步骤。在每次遍历中，都会在未排序的数组中找到最小的元素，并与未排序的数组的第一个元素交换。

第一遍:整个数组未排序数组，(-2) 是数组中最小的数字。找到(-2)作为最小数字后，将其与数组的第一个元素交换。

第二遍: 在此示例中，左侧数组是排序数组，并且该数组的长度在每次迭代后增加一。第一次传递后，排序数组的长度为 1。数组的其余部分是未排序的数组。 (1) 是未排序数组中的最小数字，与未排序数组的第一个元素交换。交换后，排序数组和未排序数组的长度将为 2。

第三遍: (10)是未排序数组中的最小数字，并与未排序数组的第一个元素交换。

第四遍: (23) 是未排序数组中唯一位于正确位置的数字。

选择排序的实现

public class MyClass {
  //选择排序函数
  static void selectionsort(int Array[]) {
    int n = Array.length;
    int temp;

    for(int i=0; i<n; i++) {
      int min_idx = i;
      for(int j=i+1; j<n; j++) {
        if(Array[j] < Array[min_idx])
        {min_idx = j;}
      }

      temp = Array[min_idx];
      Array[min_idx] = Array[i];
      Array[i] = temp;
    }
  }

  //打印数组的函数
  static void PrintArray(int Array[]) { 
    int n = Array.length; 
    for (int i=0; i<n; i++) 
      System.out.print(Array[i] + " "); 
    System.out.println(); 
  } 

  //测试代码
  public static void main(String[] args) {
    int[] MyArray = {1, 10, 23, 50, 4, 9, -4};
    System.out.println("原始数组");
    PrintArray(MyArray);

    selectionsort(MyArray);
    System.out.println("\n排序数组");
    PrintArray(MyArray);  
  }
} 

上面的代码将给出以下输出:

原始数组
1 10 23 50 4 9 -4 

排序数组
-4 1 4 9 10 23 50 

时间复杂度:

即使整个数组已排序，选择排序的时间复杂度在所有情况下都是θ(N²)，因为整个数组需要对每个元素进行迭代，并且它包含两个嵌套。