简单选择排序C/C++代码实现

- 日理万妓 2023-02-23 12:20 13阅读 0赞

## 举例： ##

选择排序的基本思想是：每一趟从待排序的记录中选出关键字最小的记录，按顺序放在已排序的记录序列的最后，直到全部排完为止。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx_size_16_color_FFFFFF_t_70]  
括号内为已排完序的，每一趟结束待排序记录的个数就少一个。

## 算法属性： ##

时间复杂度为O(n^2)  
空间复杂度为O(1)  
根据“交换记录” 的策略不同可是稳定的排序，也可能是不稳定的排序。  
移动记录次数较少，当每一记录占用的空间较多时，此方法比直接插入排序快。

另外：简单选择排序和堆选择排序不受初始序列顺序影响。

## 代码如下： ##

#include<stdio.h>
    
    #define MAXSIZE 20
    typedef int KeyType;
    typedef int InfoType;
    //记录类型
    typedef struct {
        
    	KeyType key;
    	InfoType otherinfo;
    }RedType;
    //顺序表类型
    typedef struct {
        
    	RedType r[MAXSIZE + 1];  //r[0]闲置或作哨兵
    	int length;	  			 //顺序表长度
    }SqList;
    
    
    //简单选择排序
    void SelectSort(SqList &L)
    {
        
    	int i, j, k;
    	RedType t;
    
    	for (i = 1; i < L.length; i++)			//大循环控制趟数，只剩一个记录时不用再继续比较故<
    	{
        
    		k = i;								 //k为最小值的索引，初始为i
    		for (j = i + 1; j <= L.length; j++)	 //从i+1处开始向后比较，最后一个记录也要比较到故<=
    		{
        
    			if (L.r[j].key<L.r[k].key)
    			{
        
    				k = j;
    			}
    		}
    
    		//把最小值交换到前面
    		if (k != i)
    		{
        
    			t = L.r[i];
    			L.r[i] = L.r[k];
    			L.r[k] = t;
    		}
    	}
    }
    
    
    //打印排序结果
    void println(SqList L)
    {
        
    	for (int i = 1; i <= L.length; i++)
    	{
        
    		printf("%d, ", L.r[i].key);
    	}
    	printf("\n");
    }
    
    int main()
    {
        
    	SqList L;
    	L.r[1].key = 5;
    	L.r[2].key = 8;
    	L.r[3].key = 1;
    	L.r[4].key = 4;
    	L.r[5].key = 3;
    	L.length = 5;
    
    	SelectSort(L);
    	println(L);
    }

## 运行结果： ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx_size_16_color_FFFFFF_t_70 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200707162618348.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200707162903650.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx,size_16,color_FFFFFF,t_70