Selection Sort

Selection sort is a sorting algorithm, specifically an
in-place comparison sort. It has O(n2) time complexity,
making it inefficient on large lists, and generally
performs worse than the similar insertion sort.
Selection sort is noted for its simplicity, and it has
performance advantages over more complicated algorithms
in certain situations, particularly where auxiliary
memory is limited.

Complexity

References

• trekhleb/javascript-algorithms
• Wikipedia

直接选择排序

选择排序(Selection Sort)的基本思想是：每一趟从待排序的记录中选出关键字最小的记录，顺序放在已排好序的子文件的最后，直到全部记录排序完毕。常用的选择排序方法有直接选择排序和堆排序。

本节介绍第一种选择排序：直接选择排序。

直接选择排序的基本思想
n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果：

初始状态：无序区为 R[1..n]，有序区为空。
第 1 趟排序：在无序区 R[1..n]中选出关键字最小的记录 R[k]，将它与无序区的第 1 个记录 R[1]交换，使 R[1..i]和 R[2..n]分别变为记录个数增加 1 个的新有序区和记录个数减少 1 个的新无序区。 ……
第 i 趟排序：第i趟排序开始时，当前有序区和无序区分别为 R[1..i-1]和 R[i..n][1≤i≤n-1]。该趟排序从当前无序区中选出关键字最小的记录 R[k]，将它与无序区的第 i 个记录 R[i]交换，使 R[1..i]和 R[i+1..n]分别变为记录个数增加 1 个的新有序区和记录个数减少 1 个的新无序区。
这样，n 个记录的文件的直接选择排序可经过 n-1 趟直接选择排序得到有序结果。

void SelectSort(SeqList R)  
{  
  int i，j，k；  
  for(i=1;i<n;i++){//做第i趟排序(1≤i≤n-1)  
    k=i；  
    for(j=i+1;j<=n;j++) //在当前无序区R[i..n]中选key最小的记录R[k]  
      if(R[j].key<R[k].key)  
        k=j; //k记下目前找到的最小关键字所在的位置  
      if(k!=i){ //交换R[i]和R[k]  
        R[0]=R[i]；R[i]=R[k]；R[k]=R[0]； //R[0]作暂存单元  
       } //endif  
    } //endfor  
 } //SeleetSort