coutC++入门：排序（一） |for|数值|ctime|

北京联盟_本文原题：C++入门：排序（一）
人生是一场旅行，途中会遇到各种不同的人不同的事，在心理课上，我们常做一个游戏“人生的五样” 。选出你人生中最重要的五样，可以是人可以是物可以是爱好习惯等，然后一样一样的删除，看看最后剩下的是什么？这就是一种排序。

本文插图

选择排序
排序是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列调整为“有序”的记录序列。比如下面这个小学数学题目，首先理解数字需要从大往小排列，那么一般做法是选出最大数，填写到第一个括号内，然后，再从剩余未排序数字中继续寻找最大数，然后放到已排序数字的后面，以此类推，直到所有数字均排序完毕。

本文插图

那么在程序设计时，这种排序方式叫选择排序(Selection-sort) ，是一种简单直观的排序算法，理论上讲，选择排序可能是平时排序一般人想到的最多的排序方法，因为无论什么数据进去都是O(n2)的时间复杂度，所以用到它的时候，数据规模越小越好，选择排序唯一的好处就是不占用额外的内存空间。

本文插图

# include<iostream> # include<cstdlib># include<ctime> usingnamespacestd;intmain { intn,i,j,k;srand(time( 0)); //设置种子cin>>n; //需要生成几个随机数字inta[n]={}; //设置数组长度for(i= 0;i<n;i++){a[i]=rand% 1000;cout<<a[i]<< " ";} cout<< endl;for(i= 0;i<n;i++ ) {k=i; for(j=i+ 1;j<n;j++) {if(a[j]<a[k]){k=j;} } if( k != i ) {inttemp;temp= a[k]; a[k] = a[i]; a[i] = temp; } } for(i= 0;i<n;i++){cout<<a[i]<< " ";} return0;}

本文插图

桶排序
桶排序 (Bucket sort)是计数排序的升级版。计数排序其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中，要求输入的数据必须是有确定范围的整数。下图为计数排序的演示。

本文插图

桶排序的工作的原理方法比较简单粗暴，假设输入数据服从均匀分布，先设置一个定量的数组当作空桶，然后遍历输入数据，并且把数据一个一个放到对应的桶里去，然后对每个不是空的桶进行排序，从不是空的桶里把排好序的数据拼接起来。
直接看例子可能更好理解。

# include<iostream> # include<cstdlib># include<ctime> usingnamespacestd;intmain { intn,i,k;srand(time( 0)); //设置种子cin>>n; //需要生成几个随机数字inta[ 100]={}; //假设最大值为100 ，设置100个空桶//随机生成数并放入桶内for(i= 0;i<n;i++){k= rand% 100; //最大值要小于100a[k]++; //如果有重复的数对应的下标值就加一个cout<<k<< " ";} cout<< endl;//输出for(i= 0;i< 100;i++){while(a[i]> 0){ //说明存有元素,相同的整数，要重复输出 cout<<i<< " "; //注意这里是“i” ， a[i]代表的是剩余个数 a[i]--; } } return0;} 桶排序虽然理解简单，但是有一个缺点，比如已知数据有5个，但最大数是100 ，那么就需要准备100个“桶” ，那么有95个空间就浪费了，桶排序所用时间短，但是空间浪费大。