101. 简单排序

基本思想

将初始序列(A[0] ~ A[n-1])作为待排序序列，第一趟在待排序序列(A[0] ~ A[n-1])中找最小值元素，与该序列中第一个元素A[0]交换，这样子序列(A[0])有序，下一趟排序在待排序子序列(A[1] ~A[n-1])中进行。
第i趟排序在待排序子序列(A[i-1] ~ A[n-1])中找最小值元素，与该子序列中第一个元素A[i-1]交换。
经过n-1汤排序，初始序列有序。

解题之法

template <class T>
void SelectSort(T A[], int n){

    int small;
    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;
}
        Swap(A[i], A[small]);
}
}

复杂度

O(n*n) 且不稳定