本网页所有文字内容由 imapbox邮箱云存储,邮箱网盘, iurlBox网页地址收藏管理器 下载并得到。
ImapBox 邮箱网盘 工具地址: https://www.imapbox.com/download/ImapBox.5.5.1_Build20141205_CHS_Bit32.exe
PC6下载站地址：PC6下载站分流下载
本网页所有视频内容由 imoviebox边看边下-网页视频下载, iurlBox网页地址收藏管理器 下载并得到。
ImovieBox 网页视频 工具地址: https://www.imapbox.com/download/ImovieBox4.7.0_Build20141115_CHS.exe
本文章由: imapbox邮箱云存储,邮箱网盘,ImageBox 图片批量下载器,网页图片批量下载专家,网页图片批量下载器,获取到文章图片,imoviebox网页视频批量下载器,下载视频内容,为您提供.
选择排序是一种蛮力法解决排序问题的算法。对其可简单描述为：对一个数列进行升序（降序）排列时，每次从剩余的序列中挑选出最小(最大)的数字，放到它的最终位置，以此类推，直到数列的所有数字都已经放到最终位置为止。可以简单的记忆为：选择最小(或最大)，放到最终位置。
1.算法描述
2.实例
使用选择排序法将下面数列按升序排序：
8 3 4 2 6 5
第一次在六个数字中找到最小的数字2，和数列的第一个数字交换位置，数列如下：
2 3 4 8 6 5
第二次在剩下的五个数字中找到最小的数字3，和数列的第二个数字交换位置，因为3本来的位置就是数列的第二个数字，数列顺序没有发生变化：
2 3 4 8 6 5
第三次在剩余的四个数字中找最小的数字4，和第二次情况一样，数列位置依然没有发生变化，如下：
2 3 4 8 6 5
第四次在剩余的三个数字中找最小的数字5，和数列的第四个数字交换位置，数列如下：
2 3 4 5 6 8
第五次在剩余的两个数字中找最小的数字6，和第二、三次情况一样，数列位置依然没有发生变化，如下：
2 3 4 5 6 8
第六次在剩余的一个数字中找最小的数字8，和第五次情况一样，数列如下：
2 3 4 5 6 8
最终排序后的数列也就出来了：
2 3 4 5 6 8
3.代码
void selection_sort::selection_sort_with_array(int nums[],int nums_count) { if(nums == nullptr || nums_count==0) return; int a = 0; for(unsigned int i = 0; i< nums_count; i++) { a = i; for(unsigned int j = i+1; j< nums_count; j++) { if(nums[a]>nums[j]) a = j; } if(a != i) { int temp = nums[a]; nums[a] = nums[i]; nums[i] = temp; } } }
4.算法分析
在“3.代码“中我们可以看出，选择排序算法的基本操作就是比较和替换，那我们来计算一下它的时间复杂度：
从上面的内容中我们可以看出，比较的次数只和数组中数字的个数相关，假设一个长度为n的数组，分析如下：
选择第一个最小数，需要比较n-1次
选择第二个最小数，需要比较n-2次
选择第三个最小数，需要比较n-3次
…………… …….. ……… ….
选择地n个最小数，需要比较0次
根据上面的分析，对一个长度为n的数组进行排序，比较次数为：
C(n)=(n-1)+(n-2)+(n-3)+….+0 = n*(n-1)/2;(等差公式：Sn=n*a1+n*(n-1)*d/2)
在最坏情况下，替换次数为：n-1
因此选择排序的时间复杂度为：O(n^2)；
阅读和此文章类似的: 程序员专区
官方软件产品操作指南 (170)
