十大经典排序算法————选择排序及其优化（C语言版）

我会带着你远行 2024-03-24 10:59 62阅读 0赞

### 一、概念 ###

选择排序法是一种不稳定的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后，再从剩余未排序元素中继续寻找（大）元素，然后放到已排序序列的末尾。以此类推，将全部待排序的数据元素排完。主要分为直接选择排序、树形选择排序以及堆排序。本期内容介绍直接选择排序。

### 二、代码实现 ###

void Select(int* arr, int len)//原方案，升序
    {
    	for(int i=0;i<len;i++)
    		for (int j = i + 1; j < len; j++)
    		{
    			if (arr[i] < arr[j])
    			{
    				int temp = 0;
    				temp = arr[i];
    				arr[i] = arr[j];
    				arr[j] = temp;
    			}
    
    		}
    }

此处定义了一个长度为len的数组，采用两个简单的嵌套循环。但不难发现，会有多次重复交换。

### 三、优化方案 ###

void SelectPlus(int* arr, int len)//优化方案
    {
    	for (int i = 0; i < len-1; i++)
    	{
    		int minpos = i;
    		for (int j = i + 1; j < len; j++)
    		{
    			if (arr[j] < arr[minpos])
    			{
    				minpos = j;
    
    			}
    
    		}
    		if (minpos != i)
    		{
    			arr[minpos] = arr[minpos] + arr[i];
    			arr[i] = arr[minpos] - arr[i];
    			arr[minpos] = arr[minpos] - arr[i];
    		}
    	}
    }

此处优化方法为交换最小下标，以降低交换次数。（（后续会补充其他方案）。

### 四、完整代码 ###

#include <stdio.h>
    #include <stdlib.h>
    #include <time.h>
    void Select(int* arr, int len)//原方案
    {
    	for(int i=0;i<len;i++)
    		for (int j = i + 1; j < len; j++)
    		{
    			if (arr[i] < arr[j])
    			{
    				int temp = 0;
    				temp = arr[i];
    				arr[i] = arr[j];
    				arr[j] = temp;
    			}
    
    		}
    }
    void SelectPlus(int* arr, int len)//优化方案
    {
    	for (int i = 0; i < len-1; i++)
    	{
    		int minpos = i;
    		for (int j = i + 1; j < len; j++)
    		{
    			if (arr[j] < arr[minpos])
    			{
    				minpos = j;
    
    			}
    
    		}
    		if (minpos != i)
    		{
    			arr[minpos] = arr[minpos] + arr[i];
    			arr[i] = arr[minpos] - arr[i];
    			arr[minpos] = arr[minpos] - arr[i];
    		}
    	}
    }
    int main()
    {
    	int* arr = (int*)malloc(sizeof(int) * 50);
    	srand(time(0));
    	for (int i = 0; i < 20; i++)
    	{
    		arr[i] = rand();
    	}
    	// SelectPlus(arr, 20);
    	Select(arr, 20);
    
    	for (int i = 0; i < 20; i++)
    	{
    		printf("%d\12", arr[i]);
    	}
    	 
    	return 0;
    }

补充：用time（）为srand（）生成一个随机种子，作为rand参数一生成一个随机数。

水平有限，欢迎留言！