选择排序是一种排序算法，它在每次迭代中从未排序列表中选择最小的元素并将该元素放在未排序列表的开头。

算法的图解

将第一个元素设置为minimum。 | | | —- | | 选择第一个元素作为最小值 |

将minimum与第二个元素进行比较。如果第二个元素小于minimum，则将第二个元素指定为minimum。与第三个元素进行比较minimum。同样，如果第三个元素较小，则分配minimum给第三个元素，否则什么都不做。这个过程一直持续到最后一个元素。 | | | —- | | 将最小值与其余元素进行比较 |

每次迭代后，minimum都放在未排序列表的前面。 | | | —- | | 用最小值交换第一个 |

对于每次迭代，索引从第一个未排序的元素开始。重复步骤 1 到 3，直到所有元素都放置在正确的位置。 | | | —- | | 第1次迭代 |


第2次迭代


第3次迭代


第4次迭代

算法的伪码

selectionSort(array, size)
  repeat (size - 1) times
  set the first unsorted element as the minimum
  for each of the unsorted elements
    if element < currentMinimum
      set element as new minimum
  swap minimum with first unsorted position
end selectionSort

算法的实现

选择排序中有两个嵌套循环
- 外循环运行N次迭代，每次迭代更改未排序区域的下限
- 内循环每次迭代会找出未排序区域中的最大值或最小值
选择排序会在排序过程中分割成两个区域，已排序区域，未排序区域
选择排序每一轮内层排序都会筛选出未排序区域中的最大值或最小值

// Selection sort in Java
import java.util.Arrays;
class SelectionSort {
  void selectionSort(int array[]) {
    int size = array.length;
    for (int step = 0; step < size - 1; step++) {
      int min_idx = step;
      for (int i = step + 1; i < size; i++) {
        // To sort in descending order, change > to < in this line.
        // Select the minimum element in each loop.
        if (array[i] < array[min_idx]) {
          min_idx = i;
        }
      }
      // put min at the correct position
      int temp = array[step];
      array[step] = array[min_idx];
      array[min_idx] = temp;
    }
  }
  // driver code
  public static void main(String args[]) {
    int[] data = { 20, 12, 10, 15, 2 };
    SelectionSort ss = new SelectionSort();
    ss.selectionSort(data);
    System.out.println("Sorted Array in Ascending Order: ");
    System.out.println(Arrays.toString(data));
  }
}

第[1]轮选择
[5]    [4]    [3]    [2]    [1]    
 ^                 ^    
[1]    [4]    [3]    [2]    [5]    
第[2]轮选择
[1]    [4]    [3]    [2]    [5]    
     ^         ^    
[1]    [2]    [3]    [4]    [5]    
第[3]轮选择
[1]    [2]    [3]    [4]    [5]    
         ^     ^    
[1]    [2]    [3]    [4]    [5]    
第[4]轮选择
[1]    [2]    [3]    [4]    [5]    
             ^     ^    
[1]    [2]    [3]    [4]    [5]    
[1]    [2]    [3]    [4]    [5]

算法复杂度

Time Complexity
Best	O(n2)
Worst	O(n2)
Average	O(n2)
Space Complexity	O(1)
Stability	No

比较次数：(n - 1) + (n - 2) + (n - 3) + ….. + 1 = n * (n - 1) / 2 几乎等于 n2

复杂性=O(n**2**)

此外，我们可以通过简单地观察循环次数来分析复杂性。有 2 个循环，所以复杂度是 n * n = n2，选择排序的时间复杂度在所有情况下都是相同的，在每一步，你都必须找到最小元素并将其放在正确的位置，直到到达数组末尾时才知道最小元素。

时间复杂度

最坏时间复杂度：如果想按升序排序，而输入的数组是降序排列，那么最坏的情况就会发生。时间负责度为：O(n2)
最佳时间复杂度：当数组已经排序时。时间负责度为：O(n2)
平均时间复杂度：当数组的元素处于混乱的顺序（既不升也不降）时，就会发生这种情况。时间负责度为：O(n2)

空间复杂度

空间复杂度是O(1)，因为使用了额外的变量temp。

算法的应用

在以下情况下使用计数排序：

一个小列表要排序
交换成本无关紧要
检查所有元素是强制性的
写入内存的成本很重要，就像在闪存中一样

相近的算法

冒泡排序
快速排序
插入排序
归并排序

数据结构与算法

选择排序（Selection Sort）