大家好，又见面了，我是你们的朋友全栈君。
简单选择排序
（Simple Selection Sort）也称作直接选择排序。
算法步骤：
1） 设待排序的记录存放在数组Data[1…n]中。第一趟从Data[1]开始，通过n-1次比较，从n个记录中选出关键字最小的记录，记为Data[k]，交换Data[1]和Data[k]。
2） 第二趟从Data[2]开始，通过n- 2次比较，从n-1个记录中选出关键字最小的记录，记为Data[k]，交换Data[2]和Data[k]。
3） 依次类推，第i趟从Data[i]开始，通过 n – i 次比较，从n-i+1个记录中选出关键字最小的记录，记为Data[K]，交换Data[i]和Data[k]。
4） 经过n-1趟，排序完成。
书上的例子：
时间复杂度
O( n 2 n^2 n2)
空间复杂度
O(1)
算法特点：
1 ) 就选择排序方法本身来讲，它是一种稳定的排序 方法，但图中例子所表现出来的现象是不稳定的，这是因为上述实现选择排序的算法采用“交换记录”的策略所造成的，改变这个策略可以写出不产生“不稳定现象”的选择排序算法。
2 ) 可用于链式存储结构。
3 ) 移动记录次数较少，当每一记录占用的空间较多时，此方法比直接插人排序快。
完整代码：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXSIZE 100 //顺序表最大容量，可以自行加大
typedef struct
{
int key;//关键字项
char *otherinfo;//其他数据项
}ElemType;//记录类型
typedef struct
{
ElemType Data[MAXSIZE+1];//静态顺序表的数据域，这里Data[0]为空闲或者为哨兵单元
int length;//顺序表的长度
}SqList;//顺序表
void InitList(SqList &L)//顺序表的初始化
{
L.length = 0;//使顺序表长度归0，便是顺序表的初始化
}
void CreateList(SqList &L)//顺序表的创建
{
printf("请输入：");
while(1)//建立一个死循环，循环终止条件是按了enter键
{
L.length++;//顺序表长度加一
if(L.length>MAXSIZE)//判断是否超出最大容纳量
{
printf("顺序表已满！\n");
return ;
}
scanf("%d",&L.Data[L.length].key);//顺序表数据的输入
if(getchar() == '\n')//循环终止条件
break;
}
}
void InputList(SqList L)//顺序表的输出
{
int i;//记录次数
if(L.length == 0)//判断顺序表是否为空 ，若为空结束该函数
{
printf("顺序表是空的！\n");
return ;
}
printf("打印为：");
for(i=1;i<=L.length;i++)//利用循环打印顺序表中的数据
printf("%d ",L.Data[i].key);
}
void SelectSort(SqList &L)//简单选择排序
{
int i,j,//利用两层循环排序所有关键字
k;//k为记录剩余关键字中最小的位置
for(i=1;i<L.length;i++)//在L.Data[i…L.length]中选择关键字最小的记录
{
k = i;
for(j=i+1;j<=L.length;j++)
{
if(L.Data[k].key > L.Data[j].key)//k指向此趟排序中关键字最小的记录
k = j;
}
if(k != i)//交换Data[i]与Data[k]
{
L.Data[0] = L.Data[i];
L.Data[i] = L.Data[k];
L.Data[k] = L.Data[0];
}
}
}
int main()
{
SqList L;
InitList(L);//初始化顺序表
CreateList(L);//创建顺序表
SelectSort(L);//简单选择排序
InputList(L);//打印排序后结果
return 0;
}
（完）
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/152977.html原文链接：https://javaforall.net
