新手光能
选择排序是神马东西呀？哪位大佬能给本弱弱讲一下？
资深守护
中级光能
其实呢，选择排序就是一种最最最最最最最最最基本的一种数组排序，它的排序方式就是将数组的每一个元素逐一和后面的元素进行比较，交换，最后确定下来元素的位置。选择排序与冒泡排序，快速排序相比，它的优点在于比冒泡，快排稳定，而他的缺点则在于，他的排序速度很慢，很容易超时。比方说一个数组100个元素，用选排则比较稳定的进行排序。再比方说，一个数组100000个元素，用选排就得循环大约99999*99999以下的次数，这样就超时了，所以应该用冒排和快排进行排序。
接下来就是选择排序的具体排序流程。比方说一个数组3个元素：
1 2 3
我们需要从大到小排的话：
1 2 3（初始）
2 1 3（1<2，所以交换）
2 3 1（1<3，所以交换）
3 2 1（2<3，所以交换）
3 2 1（2>1，所以不交换）
3 2 1（3>2，所以不交换）
3 2 1（3>1，所以不交换）
以上就是选择排序的大概流程。后面三步可以不要，但在选排中除非加上优化，否则必须执行，这就是选排的缺点。
我们来看看用代码怎么实现：
for(int i=1;i<=n-1;i++)//记住，i<=n-1！！！因为i如果到了n，那就和不存在的元素n+1这个元素比较，那是不行的。
{
for(int j=i+1;j<=n;j++)//j=i+1的缘由是，每个元素要和后面的元素比较。
{
if(a[i]<a[j])//由于我们要从大到小排，所以如果前面的小于后面的，就交换，保证大的在前，小的在后
{
swap(a[i],a[j]);
}
}
}在选排中有很多需要注意的地方，“为什么这样做”我都给你标出来了，你在琢磨琢磨。
另外，你要学排序，首先得把数组学好，数组排序是整个排序篇章中最最最最最最最最最最基础的排序，以后还有结构体排序呢！！！
新手天翼
shui
初级守护
是最基础的排序
新手天翼
选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小(或最大)的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法(比如序列[5， 5， 3]第一次就将第一个[5]与[3]交换，导致第一个5挪动到第二个5后面)。
基本信息
-
中文名称
选择排序
-
外文名称
Selection sort
-
性质
不稳定的排序方法
-
代表
PERL选择排序算法
-
适用范围
数据元素
-
方法
通过比较
-
应用领域
计算机，数学
目录
3堆排序
4参考代码
排序算法即解决以下问题的算法:
折叠输入
n个数的序列<a1,a2,a3,...,an>。
折叠输出
原序列的一个重排<a1*,a2*,a3*,...,an*>;，使得a1*<=a2*<=a3*<=...<=an*
排序算法有很多，包括插入排序，冒泡排序，堆排序，归并排序，选择排序，计数排序，基数排序，桶排序，快速排序等。插入排序，堆排序，选择排序，归并排序和快速排序，冒泡排序都是比较排序，它们通过对数组中的元素进行比较来实现排序，其他排序算法则是利用非比较的其他方法来获得有关输入数组的排序信息。
折叠思想
n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果:
①初始状态:无序区为R[1..n]，有序区为空。
②第1趟排序
在无序区R[1..n]中选出关键字最小的记录R[k]，将它与无序区的第1个记录R[1]交换，使R[1..1]和R[2..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。
……
③第i趟排序
第i趟排序开始时，当前有序区和无序区分别为R[1..i-1]和R(i..n)。该趟排序从当前无序区中选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。
折叠通俗的解释
对比数组中前一个元素跟后一个元素的大小，如果后面的元素比前面的元素小则用一个变量k来记住他的位置，接着第二次比较，前面"后一个元素"现变成了"前一个元素"，继续跟他的"后一个元素"进行比较如果后面的元素比他要小则用变量k记住它在数组中的位置(下标)，等到循环结束的时候，我们应该找到了最小的那个数的下标了，然后进行判断，如果这个元素的下标不是第一个元素的下标，就让第一个元素跟他交换一下值，这样就找到整个数组中最小的数了。然后找到数组中第二小的数，让他跟数组中第二个元素交换一下值，以此类推。
1.时间复杂度
排序算法复杂度对比 lgn = log2n选择排序的交换操作介于 0 和 (n - 1) 次之间。选择排序的比较操作为 n (n - 1) / 2 次之间。选择排序的赋值操作介于 0 和 3 (n - 1) 次之间。
比较次数O(n^2)，比较次数与关键字的初始状态无关，总的比较次数N=(n-1)+(n-2)+...+1=n*(n-1)/2。交换次数O(n)，最好情况是，已经有序，交换0次;最坏情况交换n-1次，逆序交换n/2次。交换次数比冒泡排序少多了，由于交换所需CPU时间比比较所需的CPU时间多，n值较小时，选择排序比冒泡排序快。
其他排序算法的复杂度如右图所示。
2.稳定性
选择排序是给每个位置选择当前元素最小的，比如给第一个位置选择最小的，在剩余元素里面给第二个元素选择第二小的，依次类推，直到第n-1个元素，第n个元素不用选择了，因为只剩下它一个最大的元素了。那么，在一趟选择，如果一个元素比当前元素小，而该小的元素又出现在一个和当前元素相等的元素后面，那么交换后稳定性就被破坏了。比较拗口，举个例子，序列5 8 5 2 9，我们知道第一遍选择第1个元素5会和2交换，那么原序列中两个5的相对前后顺序就被破坏了，所以选择排序是一个不稳定的排序算法。
折叠输入输出
输入输出与基本选择排序相同。
折叠思想
利用满二叉树的性质，将输入的数据存放到满二叉树的叶节点，通过比较树中剩余可用节点(从底层的叶节点开始)的大小，每次选择最小的数值(比较复制到二叉树的顶端)，并且把最小数值赋给排序数组的前端，把最小数值原来叶节点的位置设置为不可用;依次循环直至最后一个可用叶节点。
堆分为大根堆和小根堆，是完全二叉树。大根堆的要求是每个节点的值都不大于其父节点的值，即A[PARENT[i]] >= A[i]。在数组的非降序排序中，需要使用的就是大根堆，因为根据大根堆的要求可知，最大的值一定在堆顶。
既然是堆排序，自然需要先建立一个堆，而建堆的核心内容是调整堆，使二叉树满足堆的定义(每个节点的值都不大于其父节点的值)。接下来就是调堆和循环调堆，具体参见堆排序。
折叠c++
选择排序法的第一层循环从起始元素开始选到倒数第二个元素，主要是在每次进入的第二层循环之前，将外层循环的下标赋值给临时变量，接下来的第二层循环中，如果发现有比这个最小位置处的元素更小的元素，则将那个更小的元素的下标赋给临时变量，最后，在二层循环退出后，如果临时变量改变，则说明，有比当前外层循环位置更小的元素，需要将这两个元素交换.
c++参考代码：
int a[1000],n;
cin>>n;
for(int i=0;i<n;i++)
cin>>a[i];
for(int i=0;i<n-1;i++)
for(int j=i+1;j<n;j++)
if(a[i]<a[j])
{
int t=a[i];
a[i]=a[j];
a[j]=t;
}
for(int i=0;i<n;i++)
{
cout<<a[i]<<" ";
}
修练者
选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小(或最大)的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法(比如序列[5， 5， 3]第一次就将第一个[5]与[3]交换，导致第一个5挪动到第二个5后面)。
初始序列:{49 27 65 97 76 12 38}
第1趟:12与49交换:12{27 65 97 76 49 38}
第2趟:27不动 :12 27{65 97 76 49 38}
第3趟:65与38交换:12 27 38{97 76 49 65}
第4趟:97与49交换:12 27 38 49{76 97 65}
第5趟:76与65交换:12 27 38 49 65{97 76}
第6趟:97与76交换:12 27 38 49 65 76 97 完成
简单选择排序的算法具体描述如下:
c++代码
int a[1000],n;
cin>>n;
for(int i=0;i<n;i++)
cin>>a[i];
for(int i=0;i<n-1;i++)
for(int j=i+1;j<n;j++)
if(a[i]<a[j])
{
swap（a[i],a[j]）;
}
for(int i=0;i<n;i++)
{
cout<<a[i]<<" ";
}
修练者
选择排序法 是对 定位比较交换法（也就是冒泡排序法） 的一种改进。选择排序的基本思想是：每一趟在n-i+1（i=1，2，…n-1）个记录中选取关键字最小的记录作为有序序列中第i个记录。基于此思想的算法主要有简单选择排序、树型选择排序和堆排序。
简单选择排序的基本思想：第1趟，在待排序记录r[1]~r[n]中选出最小的记录，将它与r[1]交换；第2趟，在待排序记录r[2]~r[n]中选出最小的记录，将它与r[2]交换；以此类推，第i趟在待排序记录r[i]~r[n]中选出最小的记录，将它与r[i]交换，使有序序列不断增长直到全部排序完毕。
中文名
选择排序法
外文名
Selection sort
类 型
编程逻辑
分 类
简单选择排序，树型选择排序
选择排序的基本思想是：每一趟在n-i+1（i=1，2，…n-1）个记录中选取关键字最小的记录作为有序序列中第i个记录。基于此思想的算法主要有简单选择排序、树型选择排序和堆排序。 [1]
选择排序，从第一个数组元素开始，把第一个元素分别与后面元素比较，谁比第一个元素小，就和第一个元素交换位置，然后再以这个交换过的元素跟后面的比，直到最后一个元素，比完之后呢，现在数组的第一个元素肯定是全数组最小的，然后再从第二个元素开始以之前的方法跟后面的比，完成后第二个元素就是全数组第二小的，一直这样比到最后，就是从小到大的选择排序法
资深守护
选择排序是排序的一种，首先，给一个模板代码
for(int i=1;i<=n;i++)
for(int j=1;j<i;j++)
if(a[i]>a[j])
swap(a[i],a[j]);
这个是从大到小，从小到大那if(a[i]>a[j])改成if(a[i]<a[j])就可以了
我的代码可能与别人写的不太一样
别人写的第二重循环应该是从i+1到n，但是那样如果要从小到大排序就是if(a[i]>a[j])，反之亦反
根据个人习惯来
解释一下代码：
第一重循环变量i是遍历数组
第二重循环变量j是找数字
i=1执行结束之后，就会选出最大/最小的数，排在第一个
以3 5 4 1从小到大排列为例
我还是不用自己个人习惯的吧，不好解释
用第二重循环从i+1到n的
执行过程如下
3 5 4 1
3<5 不变
3 5 4 1
3<4 不变
3 5 4 1
3>1 换顺序
1 5 4 3
第一重循环为1结束，发现最小的1排在最前面
然后是第一重循环为2
第一个定是最小，不管
同上，后面三个再次选出最小的放在前面
以此类推······
就是这样
啊啊啊w(ﾟДﾟ)w
打字累死我了
给个采纳···
不要举报
打这么多字真的很累
张梓沫在2019-01-12 21:27:53追加了内容
没有从网上复制，纯手工打字！累死人！
中级光能
新手天翼
选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法。
