【算法】选择排序(从小到大) 排序范围(0~n-1) n为数组元素个数

ゝ一纸荒年。 2022-06-13 05:45 186阅读 0赞

开始之前，哎~数构我也是因为考研才真正接触的，不得不说，数组下标真的好晕，0和1之差，虽然核心的思想是知道的，但是，发现代码跟参考书上不一样，那种感受啊。。。以后博文我还是标上排序范围吧，免得自己乱。

今天我们就来谈谈排序算法中的简单排序算法之----选择排序

选择排序的算法思路也很简单，我们只需要在排序范围(begin,end)中选择一个**最小**的值，然后将其与排序范围中的**第一个**元素交换，如此循环往复即可。

在选择排序中，我们将指向数组最后一个元素的指针(end)保持不动，从头开始移动begin指针的位置，来逐渐缩小排序范围。

接下来就是算法的执行流程分析了，数据依然是1 3 2 8 0 6 总共6个数![20170629104551199][]

1、第一趟排序，排序范围(0,5)，其中的最小值为0，于是我们将元素0与begin指针所指向的元素1进行交换

![20170629105033732][]

2、第二趟排序，排序范围(1,5)，其中的最小值为1，于是我们将元素1与begin指针所指向的元素3进行交换

![20170629105238257][]

3、第三趟排序，排序范围(2,5)，其中的最小值为2，可以发现不用交换，其实是2元素自己交换自己(最小值位置与begin指针所在位置重合)

![20170629105507505][]

4、第四趟排序，排序范围(3,5)，其中的最小值为3，于是我们将元素3与begin指针所指向的元素8进行交换

![20170629105736400][]

5、第五趟排序，排序范围(4,5)，其中的最小值为6，于是我们将元素6与begin指针所指向的元素8进行交换

![20170629105912229][]

6、最终排序结果

![20170629110058966][]

我们可以发现，6个数的数组，进行了5次排序，根据算法执行过程分析，我们可以感觉到，选择排序要有两个模块构成，一个用于寻找待排序范围中的最小值，并进行数据交换；另外一个用于遍历，调用前面说的最小值函数。所以，我们可以得到如下选择排序的程序。

//寻找最小值，并把找到的最小值与排序范围的第一个元素进行交换
    void select(Elemtype a[] , int begin , int end)
    {
    	int i;
    	//初始化时最小值位置为起始位置
    	int minPos = begin;
    	//初始化时最小值为待排序数组的第一个元素
    	Elemtype min = a[begin];
    	//寻找最小值
    	for(i = begin ; i <= end ; i++)
    	{
    		if(a[i] < min)
    		{
    			minPos = i;
    			min = a[i];
    		}
    	}
    	//将最小值元素与待排序数组头元素进行交换
    	swap(&a[begin],&a[minPos]);
    }
    
    void sort(Elemtype a[] , int begin , int end)
    {
    	int i;
    	for(i = begin ; i <= end ; i++)
    	{
    		select(a,i,end);
    	}
    }

完整可执行程序代码如下：

#include <stdio.h>
    #define Elemtype int
    void swap(Elemtype *a , Elemtype *b);
    //寻找最小值，并把找到的最小值与排序范围的第一个元素进行交换
    void select(Elemtype a[] , int begin , int end)
    {
    	int i;
    	//初始化时最小值位置为起始位置
    	int minPos = begin;
    	//初始化时最小值为待排序数组的第一个元素
    	Elemtype min = a[begin];
    	//寻找最小值
    	for(i = begin ; i <= end ; i++)
    	{
    		if(a[i] < min)
    		{
    			minPos = i;
    			min = a[i];
    		}
    	}
    	//将最小值元素与待排序数组头元素进行交换
    	swap(&a[begin],&a[minPos]);
    }
    
    void sort(Elemtype a[] , int begin , int end)
    {
    	int i;
    	for(i = begin ; i <= end ; i++)
    	{
    		select(a,i,end);
    	}
    }
    
    void display(Elemtype a[] , int begin , int end)
    {
    	int i;
    	for(i = begin ; i < end ; i++)
    	{
    		printf("%d ",a[i]);
    	}
    	printf("\n");
    }
    
    void swap(Elemtype *a , Elemtype *b)
    {
    	Elemtype t = *a;
    	*a = *b;
    	*b = t;
    }
    
    int main()
    {
    	Elemtype a[] = {1,2,3,8,0,6};
    	printf("排序前：\n");
    	display(a,0,6);
    	sort(a,0,5);
    	printf("排序后：\n");
    	display(a,0,6);
    }

程序运行效果如下

![20170629112327522][]

选择排序算法的时间复杂度为*O(n^2)*

[20170629104551199]: /images/20220613/57badfb21dcb407985c3e0db73173e17.png
[20170629105033732]: /images/20220613/e3145bf161c54e0f9458dfe245ebb9e3.png
[20170629105238257]: /images/20220613/9229d68f886742d1873582ef7337c233.png
[20170629105507505]: /images/20220613/d43aa8ca3d464ff38c3f7d2e1ba09244.png
[20170629105736400]: /images/20220613/8b54ab5fcdf8449484db8de13f48da5a.png
[20170629105912229]: /images/20220613/a90af0fa23864d98823dbfbe9723e868.png
[20170629110058966]: /images/20220613/d1b6b81eafea4a6783d75dff55a89088.png
[20170629112327522]: /images/20220613/69c292028746481c938dc66ca2b1d2ef.png