排序算法之直接选择排序

痛定思痛。 2023-07-03 02:39 6阅读 0赞

## 选择排序 ##

基本思想：每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。

## 直接选择排序 ##

基本思想：  
1、在元素集合array\[i\] – array\[n-1\]中选择关键码最大（小）的数据元素。  
2、若它不是这组元素中的最后一个（第一个）元素，则将它与这组元素中的最后一个（第一个）元素交换，  
3、在剩余的array\[i\] – array\[n-2\]（array\[i + 1\] – array\[n - 1\]）集合中，重复上述步骤，直到集合剩余1个元素。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1pEXzAxMg_size_16_color_FFFFFF_t_70]

void Swap(int* x, int* y)
    { 
    	int tmp = *x;
    	*x = *y;
    	*y = tmp;
    }
    
    void SelectSort(int* a, int n)
    { 
    	int begin = 0;
    	int end = n - 1;
    	while (begin < end)
    	{ 
    		int min = begin;
    		int max = end;
    		for (int i = begin; i <= end; i++)
    		{ 
    			if (a[min] > a[i])
    			{ 
    				min = i;
    			}
    			if (a[max] < a[i])
    			{ 
    				max = i;
    			}
    		}
    		Swap(&a[begin], &a[min]);
    		if (begin == max)
    		{ 
    			max = min;
    		}
    		Swap(&a[end], &a[max]);
    		begin++;
    		end--;
    	}
    }

直接选择排序的特性总结：  
1、直接选择排序效率不是很好，实际中很少使用。  
2、时间复杂度：O(N^2)  
3、空间复杂度：O(1)  
4：稳定性：不稳定

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1pEXzAxMg_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200131153312558.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1pEXzAxMg==,size_16,color_FFFFFF,t_70