选择排序之C语言实现

柔情只为你懂 2022-04-25 03:16 198阅读 0赞

### 基本版的选择排序 ###

*  具体代码
 *  过程分析
 *  性能分析

# 具体代码 #

#include<stdio.h>
    
       //输入数组名字和数组内的元素个数
       void SelectionSort(int* R, int n)
       {
        
       	int pos;		//表示每轮交换的起始位置
       	int find;		//用来遍历寻找最小的
       	int flag;		//标记每轮中的最小元素
       	int temp;		//用于交换
       	
       	//控制外层循环：从0号位置开始
       	for(pos=0;pos<n-1;pos++)  
       	{
        
       		//默认将最小值设置为开始的位置
       		flag = pos;
       		
       		//从本数字后面开始逐个寻找比他小的 
       		for(find = pos+1;find<n;find++)   
       		{
        
       			if(R[find]<R[flag])
       			{
        
       				flag = find;      //利用flag来标记最小值出现的位置 
       			} 
       		}
       		
       		//将找到的最小的与pos执行交换
       		temp = R[pos];
       		R[pos] = R[flag]; 	 
       		R[flag] = temp;			
       	}
       } 
       
       int main()
       {
        
       		int M[6] = {
        1,5,3,7,8,2};
       		SelectionSort(M,6);
       		for(int i=0;i<6;i++)
       		{
        
       			printf("%d  ", M[i]);	
       		}
       }

# 过程分析 #

选择排序的根本原理是每次从无序数列中选择出最小的数，放到有序数列中（有序数列其实就是从最左边开始，逐渐扩大，而右边的无序数列逐渐减少，整个排序过程就是无序数列变成0个的过程）。  
每一轮需要一个指针来代表无序数列的开始位置，也就是POS变量。POS变量就是无序数列的开始位置。所以每次通过一个叫find的变量遍历每个数字，与POS的值对比大小，每轮筛选出一个最小值，POS增大一次，逐渐使有序数列扩张。（但是一共只需要n-1次就可以了，因为最后无序数列剩下的那个数一定是最大的）

例如我们对1，6，2，5，4，7排序。

![在这里插入图片描述][20190430204847756.png]  
第一轮：因为一开始没有有序数列所以POS=0；最小值的FLAG默认在POS处（如果后面没找到比POS小的就直接是POS了）。FIND则从1的位置开始寻找最小值，若找到，就与POS交换。不过第一轮并没有在后面找到最小值。第一轮结束。  
![在这里插入图片描述][20190430205242724.png]  
第二轮：POS变为1（物理位置），FIND中找到比POS小的数字2，于是乎交换，本轮结束。  
![在这里插入图片描述][20190430205332930.png]  
第三轮：POS变为2（物理位置），FIND中找到比POS小的数字4，交换。  
（讲一下那个FLAG变量的动作：一来FLAG指向数字5，但是后面，4比5小，遂FLAG指向4，然后到数字7，7大于4，所以FLAG不动。遍历结束，FLAG指向数字4，数字4和POS指向的数字6交换）  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzOTQ4NTgz_size_16_color_FFFFFF_t_70]  
第四轮：POS变成3（物理位置），FIND里没找到最小的，本轮结束。

现在其实数列已经有序了，所以再来一轮（因为剩下一个数时必是最大的）的时候，程序就结束了，排序完成。

# 性能分析 #

为了避免像冒泡排序那样的多次交换，这里采用了运用FLAG变量标出最小值，在一轮完后确定下了最小值的位置才进行交换。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzOTQ4NTgz_size_16_color_FFFFFF_t_70 1]

[20190430204847756.png]: /images/20220210/386dd3672fac4055b2e14ea843bacaf5.png
[20190430205242724.png]: /images/20220210/dc3a798a24dd441a89510b401477b48a.png
[20190430205332930.png]: /images/20220210/774f4024addf41e99b6b682a8cb13dab.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzOTQ4NTgz_size_16_color_FFFFFF_t_70]: /images/20220210/49c6329a09e046f0b50b00bf363abce1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzOTQ4NTgz_size_16_color_FFFFFF_t_70 1]: /images/20220210/02a8abbcaf164b5f96817a28726fee3e.png