简单选择排序 C语言

大家好，又见面了，我是你们的朋友全栈君。

简单选择排序

（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$)

空间复杂度

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;
}

（完）