首页 / 算法 / 【排序算法】——— 简单选择排序总结
【排序算法】——— 简单选择排序总结
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了【排序算法】——— 简单选择排序总结，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2906字，纯文字阅读大概需要5分钟。
内容图文
文章目录
【1】简单选择排序算法的思想
前言：爱炒股票赚钱的人，总是喜欢不断的买进卖出，想通过价差来实现盈利。
但通常这种频繁操作的人，即使失误不多，也会因为操作的手续费和税过高而获利很少。
还有一种做股票的人，他们很少出手，只是在不断的观察和判断，等到时机一到，果断买进或卖出。
他们因为冷静和沉着，以及交易的次数少，而最终收益颇丰。
前边讲的冒泡排序的思想就是不断地在交换，通过交换完成最终的排序，这和做股票短线频繁操作的人是类似的。我们可不可以像只有在时机非常明确到来时才出手的股票高手一样，就是在排序时找到合适的关键字再做交换，并且只移动一次就完成相应关键字的排序定位工作呢？这就是选择排序法的初步思想。
选择排序的基本思想是每一趟在n - i + 1 (i=1,2,…,n- 1)个记录中选取关键字最小的记录作为有序序列的第i个记录。
我们这里介绍的是简单选择排序法。
简单选择排序法(Simple Selection Sort) 就是通过n-i次关键字间的比较，从n - i + 1个记录中选出关键字最小的记录，并和第i (1 < i ≤ n) 个记录交换之。
我们来看代码
【2】代码示例
#include<iostream>
#include<stdio.h>
#include<vector>
using namespace std;
void SSSort(vector<int>&vec) //Simple Selection Sort 简单选择排序算法实现
{
int i, j, min;
for (i = 0; i < vec.size()-2; i++)
{
min = i; //将当前下标定义为最小值下标
for (j = i + 1; j <= vec.size()-1; j++) //循环i之后的数据
{
if (vec[min] > vec[j]) //如果有小于当前最小值的关键字
min = j; //将此关键字的下标赋值给min
}
if (i != min) //若min不等于i,说明找到最小值，交换vec[i]与vec[min]的值
{
swap(vec[i], vec[min]); //交换L->r[i]与L->r [min]的值
}
}
}
int main()
{
vector<int>vec;
for (int i = 0; i < 10; ++i)
{
vec.push_back(rand() % 100);
}
cout << "排序前：";
for (int val : vec)
{
cout << val << " ";
}
cout << endl;
SSSort(vec);
cout << "排序后：";
for (int val : vec)
{
cout << val << " ";
}
cout << endl;
return 0;
}
【3】过程理解
代码应该说不难理解，我们接下来根据一个例子来看具体操作
例如：待排序的关键字序列是{9,1,5,8,3,7,4,6,2}
对于 i 从1循环到8，当 i = 1时，vec [ i ]=9，min 开始是1，然后再内循环中与 j = 2到9比较vec [min]与vec[j]的大小，如果vec[min]大于vec[j]则将j赋给min，注意：这里是将下标赋给不是把vec[i]赋给。因为j=2时最小，所以min=2。最终这轮交换了vec[2]与vec[1]的值。
注意：这里比较了8次，却只交换数据操作一次。前边都是把下标操作，没有操作数据。
当i=2时，vec[ i ]=9，min开始是2，经过比较后，min=9时，vec[min]最小，所以最终交换vec[min]与vec[ i ]的值。
当i=3时，vec[ i ]=5, min开始是3，经过比较后，min=5时,，vec[min]最小，所以最终交换vec[min]与vec[ i ]的值。
后边的数据比较和交换是完全一样的。最多经过8次就可以完成全部的排序工作
【4】时间复杂度的分析
从简单选择排序的过程来看，它最大的特点就是交换移动数据次数相当少，这样也就节约了相应的时间。分析它的时间复杂度发现无论最好最差的情况，其比较次数都是一样的多，第i趟排序需要进行n-i次关键字的比较,此时需要比较n-1+n-2+…+1=n(n-1)/2 次
对于交换次数而言，当最好的时候，交换为0次，最差的时候，也就全部数据降序排列时，交换次数为n - 1次。
最终的排序时间是比较与交换的次数的总和，因此总的事件复杂度依然为O(n的平方)。
内容总结
以上是互联网集市为您收集整理的【排序算法】——— 简单选择排序总结全部内容，希望文章能够帮你解决【排序算法】——— 简单选择排序总结所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。