简单选择排序

 一、算法描述                                                     

 

假设序列中有N个元素：

第1趟找到第1到N个元素之间最小的一个，与第1个元素进行交换

第2趟找到第2到N个元素之间最小的一个，与第2个元素进行交换

第3趟找到第3到N个元素之间最小的一个，与第3个元素进行交换

。

。

第m趟找到第m到N个元素之间最小的一个，与第m个元素进行交换

。

。

第N趟（最后一趟）找到第N到N个元素之间最小的一个（即最后一个元素），与第N个元素进行交换（无需交换）

 

即每次找到剩下无序序列中元素中最小的，与无序序列最前面的元素交换，逐渐形成第一个元素有序，第一到二个元素有序，第一到三个元素有序。。。。。。。全部元素有序

 

 二、算法分析                                                     

有两层循环，共需作 n(n-1)/2 次比较，固时间复杂度为O(n^2)

且是不稳定的排序算法,空间复杂度为O(1)

无论序列怎样，都需完成N趟排序，所以最好、最坏和平均情况的执行时间是相同的

 

 三、算法实现代码                                                 

定义顺序表代码：

typedef struct list {	int Size;//大小 	int Elements[MaxSize];//用数组存放 }List;//定义顺序表

定义简单选择函数代码：

void Jiandanxuanze(List*lst){	int small;//存放最小元素下标	int i, j, temp;	for (i = 0; i
    
     Size - 1; i++)//最后一次无需执行，共执行Size-1次	{		small = i;		for (j = i + 1; j
     
      Size; j++)		{			if (lst->Elements[j]
      
       Elements[small])				small = j;//找到最小的元素的下标存在small，然后与i进行交换		}		temp = lst->Elements[i];		lst->Elements[i] = lst->Elements[small];		lst->Elements[small] = temp;//把最小的元素与最前的即i进行交换 	}}
      
     
    

 四、实例测试代码                                                 

#include 
     
      #include 
      
       #include 
       
        #define MaxSize 99typedef struct list {	int Size;//大小 	int Elements[MaxSize];//用数组存放 }List;//定义顺序表void Jiandanxuanze(List*lst);//函数声明int main(void) {	List a;	int i;	srand((unsigned)time(NULL)); //随机数种子	a.Size = 10;//定义大小为10	for ( i = 0; i<10;i++)	{		a.Elements[i] = rand() % 10;//初始化顺序表	}	printf("原表为：");	for (i = 0; i < 10;i++)	{		printf("%d  ", a.Elements[i]);	}	printf("\n");	Jiandanxuanze(&a);//调用简单选择函数，修改值需传入地址	printf("简单选择排序后为：");	for (i = 0; i < 10; i++)	{		printf("%d  ", a.Elements[i]);	}	getchar();	return 0;}void Jiandanxuanze(List*lst){	int small;//存放最小元素下标	int i, j, temp;	for (i = 0; i
        
         Size - 1; i++)	{		small = i;		for (j = i + 1; j
         
          Size; j++)		{			if (lst->Elements[j]
          
           Elements[small]) small = j;//找到最小的元素的下标存在small } temp = lst->Elements[i]; lst->Elements[i] = lst->Elements[small]; lst->Elements[small] = temp;//把最小的元素与最前的进行交换 }}