首页 > 代码库 > 简单选择排序

简单选择排序

图示

   

参考代码

void selectSort(int A[], int lens){    if (A == NULL || lens <=0)        return;    for (int i = 0; i < lens; ++i)    {        int minp = i;        for (int j = i+1; j < lens; ++j)        {            if (A[j] < A[minp])                minp = j;        }        swap(A[minp], A[i]);    }}

测试

#include <iostream>using namespace std;void selectSort(int A[], int lens){    if (A == NULL || lens <=0)        return;    for (int i = 0; i < lens; ++i)    {        int minp = i;        for (int j = i+1; j < lens; ++j)        {            if (A[j] < A[minp])                minp = j;        }        swap(A[minp], A[i]);    }}void tranverse(int A[], int lens){    for (int i = 0; i < lens; ++i)        cout << A[i] << " ";    cout << endl;}int main(){    int A[] = {5, 2, 9, 1, 3, 2, 2, 7};    int lens = sizeof(A) / sizeof(*A);    tranverse(A, lens);    selectSort(A, lens);    tranverse(A, lens);}
View Code

性能

空间复杂度:O(1)

时间复杂度:最好、最坏、平均统统O(n2)

稳定性

不稳定。案例:排序前2,4,4*,3。排序后2,3,4*,4.

简单选择排序