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个空间就浪费了，桶排序所用时间短，但是空间浪费大。分页标题
冒泡排序
冒泡排序（Bubble Sort）是一种简单的排序算法，基本思想是在一组数据中，将一个数据与后一个相邻数据相比较，如果后面的数据比前面的数据大（小），就交换这两个数据的位置，如此进行n-1轮交换直到没有再需要交换，也就是说该数列已经排序完成。可以看出每次循环所比较的次数在逐渐减小，因为一部分值已经按照顺序排好了位置。

本文插图
这个算法的名字由来是因为比较后的元素（大或小）会经交换慢慢“浮”到数列的顶端。

# include<iostream> # include<cstdlib># include<ctime> usingnamespacestd;intmain { intn,i,j;srand(time( 0)); //设置种子cin>>n; //需要生成几个随机数字inta[n]={}; //设置数组长度for(i= 0;i<n;i++){a[i]=rand% 100;cout<<a[i]<< " ";} cout<< endl;//冒泡排序for( inti = 0; i <n -1; i++){for( intj = 0; j <n -1-i; j++){if(a[j] > a[j+ 1]){inttemp = a[j+ 1];a[j+ 1] = a[j];a[j] = temp; } } } //输出for(i= 0;i<n;i++){cout<<a[i]<< " ";} return0;} 插入排序
插入排序（Insertion-Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

本文插图
插入排序和人们打牌时所用的排序方式类似：
1、抽第一张牌，此时手上的牌只有一张，所以是有序的。
2、再抽一张牌，和手上的那张牌的大小进行比较，比它大就放在后面，否则放在前面。
3、再抽一张牌，和手上的牌进行比较，插入在合适的位置，保持手上的牌有序。
4、不断重复3 ，直到牌抽完。

本文插图
程序设计思路是进行n轮循环，从第一个数值开始，该数值可以认为已经被排序，取出下一个数值，在已经排序的数值序列中从后向前扫描，如果该数值（已排序）大于新数值，将该数值移到下一位置，重复对比直到找到已排序的数值小于或者等于新数值的位置然后将新元素插入到该位置后。

# include<iostream> # include<cstdlib># include<ctime> usingnamespacestd;intmain { intn,i,j,t,k;srand(time( 0)); //设置种子cin>>n; //需要生成几个随机数字inta[n]={}; //设置数组长度for(i= 0;i<n;i++){a[i]=rand% 100;cout<<a[i]<< " ";} cout<< endl;//插入排序for(i= 0;i<n;i++){//找到比a[i]小的数， j表示其下标for(j=i -1;j>= 0;j--){if(a[j]<a[i]) break;} if(j!=i -1){k=a[i]; //向后移for(t=i -1;t>j;t--){a[t+ 1]=a[t];} //别忘了把元素插入a[t+ 1]=k;} } //输出for(i= 0;i<n;i++){cout<<a[i]<< " ";} return0;} 今天这4种比较好理解，常用的排序方法还有好多种，在实际应用中除去看排序算法效率还有它的稳定性，对于基础类型，因为相同值没有差别，排序前后相同值的相对位置并不重要，可以选择更为高效的快速排序；而对于非基础类型，排序前后相等实例的相对位置如果改变可能造成很多问题，所以需要选择稳定的排序方式。分页标题
关于排序算法的稳定性等问题后面还会介绍，请和酷教一起提高！
声明本文部分图片来自网络，如涉及版权等问题，请及时与我们联系。
「您的每一个在看对我们都是鼓励」【coutC++入门：排序（一）】