算法导论笔记 -- Step 2 [选择排序]

**转载请注明**

习题2.2-2提到选择排序（selection sort)



原理：每次从余下的数中选择最小的 放在前边

PS: 最好最坏情况都会进入两个for循环，区别就是第二个for循环里的if会不会进。都是n^2。

C++ 代码：

#include <iostream>

using namespace std;

void SELECTION_SORT( int*, int );

int main(){
    int a[] = {5,2,4,6,1,3};

    SELECTION_SORT(a, sizeof(a)/sizeof(int));

    for (int i = 0; i < sizeof(a)/sizeof(int); i++){
        cout << a[i] << endl;
    }
    return 0;
}

void SELECTION_SORT( int* array, int len ){
    for (int i = 0; i < len-1; i++){
        int min = array[i];
        int position = i;
        for (int j = i+1; j < len; j++){
            if (array[j] < min){
                min = array[j];
                position = j;
            }
        }
        array[position] = array[i];
        array[i] = min;
    }
}

运行结果：
    （跟插入排序一样，略）

空间复杂度：
    O（1）

时间复杂度：
    O（n^2)