98-对选择排序算法的实现和分析

向右看齐 2022-12-29 00:14 82阅读 0赞

***选择排序算法的思想***

1.在待排序数据序列中找到当前的最大值，将最大值与当前最后一个元素进行交换  
2.循环此过程，每次都会少一个数据

首先书写需要用到的辅助函数

#include<stdio.h>
    
    /*辅助函数：
        1.打印数据
    	2.判断整个数据序列是否已经有序
    	3.交互两个数据swap方法
    */
    
    void Show(int *arr,int len)//打印数据
    {
        
    	for(int i=0;i<len;++i)
    	{
        
    		printf("%d  ",arr[i]);
    	}
    	printf("\n");
    }
    
    bool IsSort(int *arr,int len)//判断整个数据序列是否已经有序
    {
        
    	for(int i=0;i<len-1;++i)
    	{
        
    		if(arr[i]>arr[i+1])
    		{
        
    			return false;
    		}
    	}
    	return true;
    }
    
    void SwapValue(int *a,int *b)//交互两个数据swap方法
    {
        
    	int tmp=*a;
    	*a=*b;
    	*b=tmp; 
    }

接下来实现 选择排序算法的函数

void SelectSort(int *arr,int len)
    {
        
    	for(int j=0;j<len-1;++j)//趟数 
    	{
        
    		int max_index=0;//定义当前最大值的下标 
    		for(int i=0;i<len-j;++i)
    		{
        
    			if(arr[i]>arr[max_index])
    			{
        
    				max_index=i;
    			}
    		}
    		SwapValue(&arr[max_index],&arr[len-1-j]);//交换 
    	}
    }

最后完成主函数的编写

int main()
    {
        
    	int arr[]={
        7,87,29,75,41,50,62,92,69,22,76,77,35};
    	Show(arr,sizeof(arr)/sizeof(arr[0]));
    	SelectSort(arr,sizeof(arr)/sizeof(arr[0]));
    	Show(arr,sizeof(arr)/sizeof(arr[0])); 
    	return 0;
    	
    }

运行截图如下  
![在这里插入图片描述][20201218124651620.png_pic_center]

***选择排序算法的分析***

时间复杂度：O(n^2)  
空间复杂度：O(1)  
稳定性：不稳定(有跳跃数字)

[20201218124651620.png_pic_center]: /images/20221120/5f74dea00d904807aa5c82e1ee3b0d98.png