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

冒泡排序
冒泡排序（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种比较好理解，常用的排序方法还有好多种，在实际应用中除去看排序算法效率还有它的稳定性，对于基础类型，因为相同值没有差别，排序前后相同值的相对位置并不重要，可以选择更为高效的快速排序；而对于非基础类型，排序前后相等实例的相对位置如果改变可能造成很多问题，所以需要选择稳定的排序方式。