一、选择排序
基本思想：
每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在待排序的数列的最前，直到全部待排序的数据元素排完。
实现步骤如下：
①读入数据存放在a数组中。
②在a[1]～a[n]中选择值最小的元素，与第1位置元素交换，则把最小值元素放入a[1]中。
③在a[2]～a[n]中选择值最小的元素，与第2位置元素交换，则把最小值元素放入a[2]中，……
④直到第n-1个元素与第n个元素比较排序为止。
程序实现方法：
用两层循环完成算法，外层循环i控制当前序列最小值存放的数组位置，内层循环j控制从i+1到n序列中选择最小的元素所在位置k。
例2.1 输入n个数，将n个数按从小到大的顺序输出(n<=10000)。
输入样例:
8
49 38 65 97 76 13 27 49
输出样例:
13 27 38 49 49 65 76 97
1. #include<bits/stdc++.h> 2. using namespace std; 3. const int MAXN=10001; 4. int main() 5. { 6. int i,j,n,a[MAXN]={0}; 7. cin>>n; 8. for(i=1;i<=n;i++) cin>>a[i]; 9. for(i=1;i<n;i++){ 10. int k=i; 11. for(j=i+1;j<=n;j++) 12. if(a[k]>a[j]) k=j; 13. swap(a[i],a[k]); 14. } 15. for(i=1;i<=n;i++) cout<<a[i]<<" "; 16. return 0; 17. }
二、冒泡排序
实现步骤如下：
①读入数据存放在a数组中。
②比较相邻的前后两个数据，如果前面数据大于后面的数据，就将两个数据交换。
③对数组的第0个数据到n-1个数据进行一次遍历后，最大的一个数据就“冒”到数组第n-1个位置。
④n=n-1，如果n不为0就重复前面二步，否则排序完成。
程序实现方法：
用两层循环完成算法，外层循环i控制每轮要进行多少次的比较，第1轮比较n-1次，第2轮比较n-2次，……，最后一轮比较1次。内层循环j控制每轮i次比较相邻两个元素是否逆序，若逆序就交换这两个元素。
1. #include<bits/stdc++.h> 2. using namespace std; 3. const int MAXN=10001; 4. int main() 5. { 6. int i,j,n,a[MAXN]={0}; 7. cin>>n; 8. for(i=1;i<=n;i++) cin>>a[i]; 9. for(i=1;i<n;i++){ 10. for(j=1;j<=n-i;j++) 11. if(a[j]>a[j+1]) swap(a[j],a[j+1]); 12. } 13. for(i=1;i<=n;i++) cout<<a[i]<<" "; 14. return 0; 15. }
改进的冒泡排序：
对于有些数据，我们发现，不一定要n-1次才能排完。例如1 5 2 3 4 6，我们发现只需一趟排序就可以将整个序列排完，于是，我们可以设置一个布尔变量，判断是否有进行交换，如果没有交换，说明已经排序完成，进而减少几趟排序。
1. #include<bits/stdc++.h> 2. using namespace std; 3. const int MAXN=10001; 4. int main() 5. { 6. int i,j,n,a[MAXN]={0}; 7. bool ok; 8. cin>>n; 9. for(i=1;i<=n;i++) cin>>a[i]; 10. for(i=1;i<n;i++){ 11. ok=true; 12. for(j=1;j<=n-i;j++) 13. if(a[j]>a[j+1]){ 14. swap(a[j],a[j+1]); 15. ok=false; 16. } 17. if(ok==true) break; 18. } 19. for(i=1;i<=n;i++) cout<<a[i]<<" "; 20. return 0; 21. }
例2.2 车厢重组
【问题描述】
在一个旧式的火车站旁边有一座桥，其桥面可以绕河中心的桥墩水平旋转。一个车站的职工发现桥的长度最多能容纳两节车厢，如果将桥旋转180度，则可以把相邻两节车厢的位置交换，用这种方法可以重新排列车厢的顺序。于是他就负责用这座桥将进站的车厢按车厢号从小到大排列。他退休后，火车站决定将这一工作自动化，其中一项重要的工作是编一个程序，输入初始的车厢顺序，计算最少用多少步就能将车厢排序。
【输入文件】
输入文件有两行数据，第一行是车厢总数N（不大于10000），第二行是N个不同的数表示初始的车厢顺序。
【输出文件】
一个数据，是最少的旋转次数。
【输入样例】
4
4 3 2 1
【输出样例】
6
【AC代码】
1. #include<stdio.h> 2. #include<iostream> 3. using namespace std; 4. int a[10001]; 5. int main() 6. { 7. int n,i,j,temp,sum=0; 8. scanf("%d",&n); 9. for(i=1;i<=n;i++) scanf("%d",&a[i]); 10. for(i=1;i<=n;i++){ 11. for(j=1;j<=n-i;j++){ 12. if(a[j]>a[j+1]){ 13. swap(a[j],a[j+1]); 14. sum++; 15. } 16. } 17. } 18. printf("%d",sum); 19. return 0; 20. }
三. 插入排序
插入排序思想：回忆一下打牌时抓牌的情景，为了方便打牌，抓牌时一般一边抓牌一边按花色和大小插入恰当的位置，当抓完所有的牌时，手中的牌便是有序的，这排序方法即插入排序。
当读入一个元素时，在已经排序好的序列中，搜寻它正确的位置，再放入读入的元素。但不该忽略一个重要的问题：在插入这个元素前，应当先将将它后面的所有元素后移一位，以保证插入位置的原元素不被覆盖。
1. //插入排序：8 36 25 48 12 65 43 20 58 2. #include<iostream> 3. using namespace std; 4. const int MAXN=10001; 5. int main() 6. { 7. int n,i,j,k; 8. float temp,a[MAXN]; 9. cin>>n; 10. for(i=1;i<=n;i++) cin>>a[i]; 11. for(i=1;i<=n;i++){ 12. for(j=i-1;j>=1;j--) 13. if(a[j]<a[i]) break; 14. if(j!=i-1){ 15. temp=a[i]; 16. for(k=i-1;k>j;k--) 17. a[k+1]=a[k]; 18. a[k+1]=temp; 19. } 20. for(j=1;j<=n;j++) cout<<a[j]<<" "; 21. cout<<endl; 22. } 23. return 0; 24. }
四. 桶排序
桶排序的思想是若待排序的值在一个明显有限范围内(整型)时，可设计有限个有序桶，待排序的值装入对应的桶（当然也可以装入若干个值），桶号就是待排序的值，顺序输出各桶的值，将得到有序的序列。
1. //桶排序：10 2 3 1 2 4 55 3 55 3 2 2. #include<iostream> 3. #include<cstring> 4. using namespace std; 5. int main() 6. { 7. int b[101],n,i,j,k; 8. memset(b,0,sizeof(b)); 9. cin>>n; 10. for(i=1;i<=n;i++) { 11. cin>>k; 12. b[k]++; 13. } 14. for(i=0;i<=100;i++){ 15. while(b[i]>0){ 16. cout<<i<<" "; 17. b[i]--; 18. } 19. } 20. cout<<endl; 21. return 0; 22. }
1. //桶排升级版 0~9号桶 从个、十、百... ...按位入桶出桶 2. #include <iostream> 3. #include <cstring> 4. using namespace std; 5. int a[50],b[10][51]; 6. int main() 7. { 8. int n,maxn=0; 9. cin>>n; 10. for(int i=1;i<=n;i++){ 11. cin>>a[i]; 12. if(a[i]>maxn) maxn=a[i]; 13. } 14. int m=0; 15. while(maxn>0){m++;maxn/=10;} 16. int t=1,tb; 17. for(int i=1;i<=m;i++){ 18. //入桶 19. memset(b,0,sizeof(b)); 20. for(int j=1;j<=n;j++){ 21. tb=a[j]/t%10; 22. b[tb][50]++; 23. b[tb][b[tb][50]]=a[j]; 24. } 25. t*=10; 26. //出桶 27. int wei=1; 28. for(int j=0;j<=9;j++){ 29. for(int k=1;k<=b[j][50];k++){ 30. a[wei++]=b[j][k]; 31. } 32. } 33. //输出过程 34. for(int j=1;j<=n;j++) 35. cout<<a[j]<<" "; 36. cout<<endl; 37. } 38. return 0; 39. }
例2.3 明明的随机数(Noip2006)
【问题描述】
明明想在学校中请一些同学一起做一项问卷调查，为了实验的客观性，他先用计算机生成了N个1到1000之间的随机整数（N≤100），对于其中重复的数字，只保留一个，把其余相同的数去掉，不同的数对应着不同的学生的学号。然后再把这些数从小到大排序，按照排好的顺序去找同学做调查。请你协助明明完成“去重”与“排序”的工作。
【输入文件】
输入文件random.in 有2行，
第1行为1个正整数，表示所生成的随机数的个数：N
第2行有N个用空格隔开的正整数，为所产生的随机数。
【输出文件】
输出文件random.out 也是2行，第1行为1个正整数M，表示不相同的随机数的个数。第2行为M个用空格隔开的正整数，为从小到大排好序的不相同的随机数。
【输入样例】
10
20 40 32 67 40 20 89 300 400 15
【输出样例】
8
15 20 32 40 67 89 300 400
1. //明明的随机数：10 20 40 32 67 40 20 89 300 400 15 2. #include<iostream> 3. #include<cstdio> 4. #include<cstring> 5. using namespace std; 6. int main() 7. { 8. int b[1001],n,i,j,m=0,x; 9. memset(b,0,sizeof(b)); 10. cin>>n; 11. for(i=1;i<=n;i++){ 12. cin>>x; 13. if(b[x]==0) m++; 14. b[x]++; 15. } 16. cout<<m<<endl; 17. for(i=0;i<=1000;i++) 18. if(b[i]>0) cout<<i<<" "; 19. cout<<endl; 20. return 0; 21. }
