3.选择排序

3.选择排序

3.1选择排序的思想和复杂度

选择排序思想

选择排序可以说是最简单的排序方法，通过对一个长度为N的数组扫描N次来完成排序。第一次扫描找到最小值，替换到数组的第一个下标处；第二次找到次小值，替换到数组的第二个下标处。

时间和空间复杂度

时间复杂度如表所示

算法	平均情况	最好情况	最差情况
冒泡	O(N^2)	O(N^2)	O(N^2)

空间复杂度：O(1)

3.2选择排序的操作

假设有这样一个数组vec：

下标	0	1	2	3	4	5	6	7	8	9
数组	4	3	5	2	1	9	8	6	0	7

对这个数组进行选择排序，同样需要一外层循环和内层循环来完成。
内层循环的目的是在每一轮扫描中找到当前轮次中的最小值。
外层循环的目的是找到数组的最小值，次小值，再次小值...直到次大值，最大值。

内层循环(i<=j<vec.size(), j++)

可以通过下表理解内层循环寻找当前轮次中的最小值：

指针	i
原始数组	4	3	5	2	1	9	8	6	0	7
指针	i&j&min
原始数组	4	3	5	2	1	9	8	6	0	7
指针	i	j&min
原始数组	4	3	5	2	1	9	8	6	0	7
指针	i		j
原始数组	4	3	5	2	1	9	8	6	0	7
指针	i			j&min
原始数组	4	3	5	2	1	9	8	6	0	7
指针	i				j&min
原始数组	4	3	5	2	1	9	8	6	0	7
指针	i					j
原始数组	4	3	5	2	1	9	8	6	0	7
指针	i						j
原始数组	4	3	5	2	1	9	8	6	0	7
指针	i							j
原始数组	4	3	5	2	1	9	8	6	0	7
指针	i								j&min
原始数组	4	3	5	2	1	9	8	6	0	7
指针	i									j
原始数组	0	3	5	2	1	9	8	6	4	7

外层循环(0<i<vec.size() ,i++)

可以通过下表理解外层循环的交换：

指针	i
原始数组	4
指针		i
更新数组	0	1
指针			i
更新数组	0	1	2
指针				i
更新数组	0	1	2	3
...
指针										i
更新数组	0	1	2	3	4	5	6	7	8	9

OK, 可以上代码了。

3.3 C++代码

#include <iostream>
#include <vector>
using namespace std;

class Sort
{
public:
    void select(vector<int> &vec)
    {
        int number=vec.size();
        vector<int> nullvec;
        if(number==0)return;
        int min=vec[0];
        for(int i=0;i<number;i++)
        {
            min=i;
            for(int j=i;j<number;j++)
            {
                if(vec[j]<vec[min])min=j;
            }
            if(i!=min)exch(vec,i,min);

            show(vec);
        }
    }
    void show(vector<int> &vec)
    {
        for(int i=0;i<vec.size();i++)
        {
            cout << vec[i] << " ";
        }
        cout << endl;
    }
    vector<int> init()
    {
        vector<int> vec;
        int arr[10]={4,3,5,2,1,9,8,6,0,7};
//        int arr[10]={9,8,7,6,5,4,3,2,1,0};
        vec.insert(vec.begin(),arr,arr+10);
        cout <<"ori:"<<endl;
        show(vec);
        cout <<"-------------------"<<endl;
        return vec;
    }
    bool checkorder(vector<int> &vec)
    {
        for(int i=0;i<vec.size()-1;i++)
        {
            if(vec[i]>vec[i+1])return false;
        }
        return true;
    }
private:
    void exch(vector<int> &vec,int a,int b)
    {
        int tmp;
        tmp=vec[a];
        vec[a]=vec[b];
        vec[b]=tmp;
    }
};

int main()
{
    Sort sortob;
    vector<int> mvec=sortob.init();
    sortob.select(mvec);
    cout <<"------result-------"<<endl;
    if(sortob.checkorder(mvec))
        sortob.show(mvec);
    else
    {   cout << sortob.checkorder(mvec);
    }
    return 0;
}

输出结果：

image.png