1.复杂度与稳定性文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25223.html
算法时间复杂度文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25223.html
最坏情况:O(n^2)文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25223.html
最好情况:O(1) //即不需要排序,本身已是正序文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25223.html
平均情况:O(n^2)文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25223.html
空间复杂度:S(n)=O(1)文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25223.html
稳定性:不稳定排序 文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25223.html
2.过程介绍(以顺序为例)文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25223.html
1.我们设置两个记录i和j,i自数组第一个元素开始,j自i+1个元素开始。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25223.html
2.接着j遍历整个数组,选出整个数组最小的值,并让这个最小的值和i的位置交换(如果i选择的元素是最小的则不需要交换),我们称这个过程为一趟选择排序。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25223.html
3.i选中下一个元素(i++),重复进行每一趟选择排序。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25223.html
4.持续上述步骤,使得i到达n-1处,即完成排序 。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25223.html
3.图示过程:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25223.html
以数据{2,10,9,4,8,1,6,5}为例文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25223.html
开始数据 | 2 | 10 | 9 | 4 | 8 | 1 | 6 | 5 |
第一趟 | 1 | 10 | 9 | 4 | 8 | 2 | 6 | 5 |
第二趟 | 1 | 2 | 9 | 4 | 8 | 10 | 6 | 5 |
第三趟 | 1 | 2 | 4 | 9 | 8 | 10 | 6 | 5 |
第四趟 | 1 | 2 | 4 | 5 | 8 | 10 | 6 | 9 |
第五趟 | 1 | 2 | 4 | 5 | 6 | 10 | 8 | 9 |
第六趟 | 1 | 2 | 4 | 5 | 6 | 8 | 10 | 9 |
第七趟 | 1 | 2 | 4 | 5 | 6 | 8 | 9 | 10 |
如图所使,每次交换的数据使用红颜色标记出,已经排好序的数据使用蓝底标注,文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25223.html
每一趟从待排序的数据元素中选出最小的一个元素,顺序放在已排好序的数列的最后,直到全部待排序的数据元素排完,我们只需要进行n-1趟排序即可,因为最后剩下的一个数据一定是整体数据中最大的数据。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25223.html
4.代码实现:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25223.html
#include<iostream> using namespace std; void select_sort( int a[], int n){ int temp; for ( int i=0;i<n-1;i++){ temp=i; //利用一个中间变量temp来记录需要交换元素的位置 for ( int j=i+1;j<n;j++){ if (a[temp]>a[j]){ //选出待排数据中的最小值 temp=j; } } swap(a[i],a[temp]); //交换函数 } } int main(){ int a[8]={2,10,9,4,8,1,6,5}; int n=8; select_sort(a,n); for ( int i=0;i<n;i++){ cout<<a[i]<< ' ' ; } return 0; } |
相比冒泡排序的不断交换,简单选择排序(simple selection sort)是等到合适的关键字出现后再进行交换,并且移动(交换)一次就可以达到一次冒泡的效果。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25223.html