算法一：简单选择排序（O(n^2)）

 

1. 简单选择排序

思想：对列表或者列表的一部分进行多次扫描，每次选出一个元素放在正确的位置。

适用范围：number<50

排序过程：示例

  初始关键字 [49 38 65 97 76 13 27 49]

第一趟排序后 13 [38 65 97 76 49 27 49]

第二趟排序后 13 27 [65 97 76 49 38 49]

第三趟排序后 13 27 38 [97 76 49 65 49]

第四趟排序后 13 27 38 49 [49 97 65 76]

第五趟排序后 13 27 38 49 49 [97 97 76]

第六趟排序后 13 27 38 49 49 76 [76 97]

第七趟排序后 13 27 38 49 49 76 76 [ 97]

最后排序结果 13 27 38 49 49 76 76 97

算法：

步骤1：假设a[1]最小

步骤2：用a[2]-a[10]的所有元素跟a[1]比，比a[1]小就交换

复杂度：最好：

        平均：

稳定性：稳定

程序实现（用数组）：

template <class T>

void SelectSort(T A[],int n)

{

      int small;

T temp;

      for(int i=0;i<n-1;++i)

      {

             small=i;

             for(int j=i+1;j<n;++j)

             {

                    if(A[j]<A[small]) 

                    {

                           small=j;

                    }

             }

             temp=A[i];

             A[i]=A[small];

             A[small]=temp;

      }

}