578-选择排序算法的思想和性能分析

桃扇骨 2022-09-11 15:22 193阅读 0赞

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

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16]  
**假如说，我们现在有一组未排序的序列**  
![在这里插入图片描述][8ae39e17e4774e85a64cd21a9c74a80f.png]  
**先定位到元素65，也就是说，从数组的0号位置开始，定位0号位置的元素**![在这里插入图片描述][dd51e7cdd4014843b5763aca34559002.png]  
**除我们定位的元素之外，在其后边的所有元素中去找一个最小值，然后和当前定位的元素进行交换。**  
**也就是说，每一次我们都要选择出来1个最小的元素放在定位的位置。  
我们是从0号位置65开始定位的。**  
![在这里插入图片描述][8bbe06b80719463c98f24a1fd46230a5.png]  
接下来，然后遍历65后面的元素，一个一个和65比，找到第一个比65小的是40，用min记录这个40，然后继续遍历40之后的元素，一个一个和40比，然后找到第一个比40小的元素：34，用min记录34这个元素，然后继续向后遍历，一个一个和34比，然后找到第一个比34小的元素：14，然后min标识这个14，然后遍历结束，这一趟中，找到的最小的元素是14  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 1]  
**然后现在要把65和14交换一下，我们得知道最小值14在数组中的位置。**  
**我们的min不仅仅记录最小值，还要记录这个最小值min在数组中的下标k。**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 2]  
**现在把65这个值和剩下的元素中找到的最小值14（下标是9）进行交换**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 3]  
**第一趟处理完之后，只能说是序列的最小值放在了数组的0号位置。**  
**0号位置后面的数据不是有序的。**

**然后进行第二趟**：以66作为开始的元素，作为定位的元素，min初始化为66，k:1然后往后找，找到第一个小于66的元素：40，更新一下min:40,k:3  
然后继续往后找，找第一个小于40的元素：34，更新一下min：34 k:7，然后继续往后找，找第一个小于34的元素，没找到。第二趟结束。找到剩下元素中最小的元素34，和起始位置66交换。  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 4]  
**同样的，以此类推下去。**  
![在这里插入图片描述][8d6da3c604154c2ebbda165cbafb4233.png]  
![在这里插入图片描述][a41e6b4d0bf44203aa2e935fedd8cace.png]

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 5]  
**每次都是取第一个元素，假设是最小的元素，作为开始比较的位置，然后往后遍历，一个一个比较，找出最小值和起始位置交换。**  
**每一趟都是期望把这一趟序列里的最小值放在开头**。

**序列有10个元素，就走10趟，但是最后一趟就剩下1个元素了，不用操作，所以我们走9趟就可以了**

## 选择排序算法代码实现 ##

//选择排序算法 O(n) * O(n) = O(n^2) 空间复杂度： O(1)   稳定性：不稳定    
    //5 5 3
    void ChoiceSort(int arr[], int size)
    {
        
    	for (int i = 0; i < size - 1; i++)//O(n) 趟数 
    	{
        
    		int min = arr[i];//min初始化为当前序列的首位置元素
    		int k = i;//当前序列的首位置初始化为当前序列的最小值的下标 
    		for (int j = i+1; j < size; j++)//O(n) 遍历当前序列 
    		{
        
    			if (arr[j] < min)
    			{
        
    				min = arr[j];//更新当前序列的最小值min 
    				k = j;//更新当前序列的最小值的下标 
    			}
    		}
    		//如果k=i，说明当前序列的首位置的元素就是最小的，就不用交换了 
    		if (k != i)//k!=i，当前序列的最小值和当前序列的首位置元素交换 
    		{
        
    			int tmp = arr[i];
    			arr[i] = arr[k];
    			arr[k] = tmp;
    		}
    	}
    }

## 选择排序算法的性能分析 ##

**选择排序之所以效率比冒泡排序高一点**，是因为选择排序，每一趟从首元素开始，都是只做比较，留下值最小的那个元素，并没有对这一趟所有的元素进行大量的交换操作，因为交换的代码比较多，耗时间。  
**但是选择排序没有办法去优化中间的步骤**，因为整个序列不一个一个比较完，是不知道哪个元素是最小的，哪怕序列是有序的**所以，选择排序没有办法让它提前结束，必须该做的全部都做完。**  
**而冒泡排序**，如果某一趟下来，没有任何两两交换的操作，就证明此时的序列是有序的，直接return了。

**选择排序算法的时间复杂度和平均时间复杂度**：O(n^2)  
因为有2个for循环，是嵌套的。  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 6]  
**这个数组在执行过程中，都是进行原地排序的，没有开辟额外的空间，栈上定义的空间是常量级的空间，不管数据量是多大，定义的变量就是这2个。所以空间复杂度是O(1)**

**选择排序算法**：不稳定性  
因为：举个例子，比如说  
![在这里插入图片描述][75b892d834fc4b37a3bd8c3eda30e5e6.png]  
在选择排序算法中，第一题，以0号位置的5作为定位，然后向后找最小值，和首位置的5交换，遍历完，找到3是这个序列中最小的值，然后把3和首位置的5交换，这样，原本在0号位置的5变到了1号位置的5的后面位置了。相同元素5的相对位置发生了改变。这样就是不稳定了！！！

![在这里插入图片描述][7b772c427f5b44b4ae818e8c69d7bc91.png]  
![在这里插入图片描述][85134839958343deaab5d87d3ca8149c.png]

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/e213011c0c434dac9a522beff6269277.png
[8ae39e17e4774e85a64cd21a9c74a80f.png]: /images/20220828/f88240ddca614c4c9ef88d85ac7c5e34.png
[dd51e7cdd4014843b5763aca34559002.png]: /images/20220828/d299e41f3c854d74945b902ead447967.png
[8bbe06b80719463c98f24a1fd46230a5.png]: /images/20220828/0f91412d5188484481146579047b2669.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/27697e229bbd4f6d9543e48aca5d70b8.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220828/9874a2d0bc6949d99b4bc6e6b3be5b70.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 3]: /images/20220828/c5e1633079f549ad8a989bf7451b42e1.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 4]: /images/20220828/2323ff0428914d7cb027fe948c06ea95.png
[8d6da3c604154c2ebbda165cbafb4233.png]: /images/20220828/10769d072a3040c593c2676a302f2b6d.png
[a41e6b4d0bf44203aa2e935fedd8cace.png]: /images/20220828/9643bb9d84a54996879a685d9627fda2.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 5]: /images/20220828/c2a4402ac4e7413a8df5911b7aff5986.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 6]: /images/20220828/779abd7f06474589b9ba3dbff9cc4a9d.png
[75b892d834fc4b37a3bd8c3eda30e5e6.png]: /images/20220828/ddc0eace4e16475fa1b438994db4a067.png
[7b772c427f5b44b4ae818e8c69d7bc91.png]: /images/20220828/5bc04d23f7434af6bae16cbc5e48f568.png
[85134839958343deaab5d87d3ca8149c.png]: /images/20220828/e5696dd3ab414bba8820d6598ec8afa4.png