选择排序

算法步骤

设待排序的记录存储在数组r[1…n]中，首先从r[1…n]中选择一个关键词最小的记录r[k],r[k]和r[1]交换
第二趟排序，从r[2…n]中选择一个关键词最小的记录r[k],r[k]与r[2]交换
重复上述过程，经过n-1趟排序，得到有序序列

冒泡排序是两两交换，但选择排序是找到最小的和当前序列第一个元素交换

举例

原数组
12	2	16	30	28	20	16*	6	10	18

第一次
2	12	16	30	28	20	16*	6	10	18

第二次
2	6	16	30	28	20	16*	12	10	18

第三次
2	6	10	30	28	20	16*	12	16	18

第四次
2	6	10	12	28	20	16*	30	16	18

第五次
2	6	10	12	16*	20	28	30	16	18

第六次
2	6	10	12	16*	16	28	30	20	18

第七次
2	6	10	12	16*	16	18	30	20	28

第八次
2	6	10	12	16*	16	18	20	30	28

第九次
2	6	10	12	16*	16	18	20	28	30

16和16*的顺序交换了，说明这个不是稳定的排序方式
这里加一段来自算法可视化网站https://visualgo.net/zh 的gif，帮助理解

算法实现

void SimpleselectSort(int r[],int n)
{
	int i ,j,k,temp;
	for(i = 0;i<n-1;i++)
	{
		k=i;
		for(j=i+1;j<n;j++)
		{
			if(r[j]<r[k])
				k=j;	//记录最小值的下标
		}
		if(k!=i)
		{
			temp=r[i];
			r[i]=r[k];
			r[k]=temp;
		}
	}
}

算法分析

时间复杂度

简单的选择排序需要 $n-1$ 次排序，每次排序$n-i$次比较，总的比较次数为$\frac{n(n-1)}{2}$

空间复杂度

简单选择排序在交换时使用了一个辅助空间temp ，空间复杂度为 $O(1)$

稳定性

从上面的实例可以看出，16和16*的顺序交换了，说明这个不是稳定的排序方式

源码一览

#include<bits/stdc++.h>
using namespace std;
# define Maxsize 10000
int A[Maxsize];
void SimpleselectSort(int r[],int n)
{
    int i ,j,k,temp;
    for(i = 0;i<n-1;i++)
    {
        k=i;
        for(j=i+1;j<n;j++)
        {
            if(r[j]<r[k])
                k=j;	//记录最小值的下标
        }
        if(k!=i)
        {
            temp=r[i];
            r[i]=r[k];
            r[k]=temp;
        }
        cout<<"第"<<i+1<<"次简单选择排序的结果:"<<endl;
        for(int k = 0;k<n;k++)
        {
            cout<<A[k]<<" ";
        }
        cout<<endl;
    }
}
int main()
{
    int n ;
    cout<<"请输入数列中的元素个数"<<endl;
    cin>>n;
    cout<<"请依次输入数列中的元素"<<endl;
    for(int i = 0;i<n;i++)
    {
        cin>>A[i];
    }
    SimpleselectSort(A,n);
    cout<<endl;
    return 0;
}