简单选择排序 C语言

谁践踏了优雅 2022-12-22 11:27 164阅读 0赞

### 简单选择排序 ###

（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趟，排序完成。

书上的例子：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDAyNTQ0_size_16_color_FFFFFF_t_70_pic_center]  
**时间复杂度**

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

![在这里插入图片描述][20201120122805213.png_pic_center]  
（完）

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDAyNTQ0_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/346cb53a24e54e91bc420ecf82b0b2db.png
[20201120122805213.png_pic_center]: /images/20221120/5d0da9b7ec884b41b14e56858004e0ac.png