排序

1. 选择排序

（1） 基本思想：每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在待排序的数列的最前，直到全部待排序的数据元素排完。
（2）排序过程：

【示例】：

初 始 关键字 [49 38 65 97 76 13 27 49]
第一趟排序后 13［38 65 97 76 49 27 49］
第二趟排序后 13 27［65 97 76 49 38 49］
第三趟排序后 13 27 38 [97 76 49 65 49]
第四趟排序后 13 27 38 49 [76 97 65 49]
第五趟排序后 13 27 38 49 49 [97 65 76]
第六趟排序后 13 27 38 49 49 65 [97 76]
第七趟排序后 13 27 38 49 49 65 76 [97]
最后排序结果 13 27 38 49 49 65 76  97

例2.1  输入n个数，将n个数按从小到大的顺序输出(n<=10000)。

输入样例:

       8

       49 38 65 97 76 13 27 49

输出样例:

       13 27 38 49 49 65 76 97

归纳上述排序过程，具体实现步骤如下：

       ①读入数据存放在a数组中。

       ②在a[1]～a[n]中选择值最小的元素，与第1位置元素交换，则把最小值元素放入a[1]中。

       ③在a[2]～a[n]中选择值最小的元素，与第2位置元素交换，则把最小值元素放入a[2]中，……

       ④直到第n-1个元素与第n个元素比较排序为止。

       程序实现方法：用两层循环完成算法，外层循环i控制当前序列最小值存放的数组位置，内层循环j控制从i+1到n序列中选择最小的元素所在位置k。

程序如下：

#include<iostream>
 using namespace std;
 const int MAXN=10001;
 int main()
 {    int n,k,i,j;
      float temp,a[MAXN];
      cin>>n;
      for (i=0;i<n;i++)
          cin>>a[i];                //输入n个数 
      for (i=0;i<n;i++)           //i控制当前序列中最小值存放的数据位置 
      {
          k=i;
          for (j=i+1;j<n;j++)    //在当前无序区a[i..n]中选最小的元素a[k]
             if (a[j]<a[k])  k=j;
          if (k!=i)               //交换a[i]和a[k]，将当前最小值放到a[i]位置 
          {
        temp=a[i];a[i]=a[k];a[k]=temp;
          }
      }
      for (i=0;i<n;i++)  
         cout<<a[i]<<" ";
      return 0; 
 }

2.冒泡排序

       冒泡排序的思想：以n个人站队为例，从第1个开始，依次比较相邻的两个是否逆序对(高在前，矮在后)，若逆序就交换这两人，即第1个和第2个比，若逆序就交换两人，接着第2个和第3个比，若逆序就交换两人，接着第3个和第4个比，若逆序就交换两人，……，直到n-1和n比较，经过一轮比较后，则把最高的人排到最后，即将最高的人像冒泡一样逐步冒到相应的位置。原n个人的排序问题，转换为n-1个人的排序问题。第二轮从第1个开始，依次比较相邻的两个人是否逆序对，若逆序就交换两人，直到n-2和n-1比较。如此，进行n-1轮后，队列为有序的队列。

       从上述分析中可以看出，每进行一轮的比较之后，n个数的排序规模就转化为n-1个数的排序规模。

归纳上述排序过程，具体实现步骤如下：

    ①读入数据存放在a数组中。

    ②比较相邻的前后两个数据，如果前面数据大于后面的数据，就将两个数据交换。

    ③对数组的第0个数据到n-1个数据进行一次遍历后，最大的一个数据就“冒”到数组第n-1个位置。

    ④n=n-1，如果n不为0就重复前面二步，否则排序完成。

    程序实现方法：用两层循环完成算法，外层循环i控制每轮要进行多少次的比较，第1轮比较n-1次，第2轮比较n-2次，……，最后一轮比较1次。内层循环j控制每轮i次比较相邻两个元素是否逆序，若逆序就交换这两个元素。

【程序实现】

#include<iostream>
 using namespace std;
 const int MAXN=10001;
 int main()
 {
     int n,i,j;
     float temp,a[MAXN];
     cin>>n;
     for (i=0;i<n;i++)
       cin>>a[i];                //输入n个数 
     for(i=n-1; i>=1; i--)       //进行n-1轮冒泡
     { 
        for(j=0; j<=i; j++)      //每轮进行i次的比较
        {
           if(a[j]>a[j+1])       //相邻两个元素比较，若逆序就交换
             swap(a[j], a[j+1]); //交换
        }
     }
     for (i=0;i<n;i++)           //输出排序结果
       cout<<a[i]<<" ";
     return 0; 
 }

改进的冒泡排序:
    对于有些数据，我们发现，不一定要n-1次才能排完。例如1 5 2 3 4 6，我们发现只需一趟排序就可以将整个序列排完，于是，我们可以设置一个布尔变量，判断是否有进行交换，如果没有交换，说明已经排序完成，进而减少几趟排序。
【程序实现】

bool ok;
for(int i=n-1; i>=1; i--)
{
    ok=true;                  //判断是否有交换
    for(int j=1; j<=i; j++)
    {
        if(a[j]>a[j+1]) 
        {
            swap(a[j],a[j+1]);
            ok=false;
        }
    }
    if(ok==true) break;     //没有交换就退出
}

例2.2  车厢重组
【问题描述】
    在一个旧式的火车站旁边有一座桥，其桥面可以绕河中心的桥墩水平旋转。一个车站的职工发现桥的长度最多能容纳两节车厢，如果将桥旋转180度，则可以把相邻两节车厢的位置交换，用这种方法可以重新排列车厢的顺序。于是他就负责用这座桥将进站的车厢按车厢号从小到大排列。他退休后，火车站决定将这一工作自动化，其中一项重要的工作是编一个程序，输入初始的车厢顺序，计算最少用多少步就能将车厢排序。
【输入文件】
    输入文件有两行数据，第一行是车厢总数N（不大于10000），第二行是N个不同的数表示初始的车厢顺序。
【输出文件】
    一个数据，是最少的旋转次数。
【输入样例】
    4
    4 3 2 1
【输出样例】
    6

程序如下：

#include<iostream>
 #include<cstdio>
 using namespace std;
 long n,i,j,t,s,a[10000];
 int main()
 {
    cin>>n;
    for (i=1; i<=n; i++)
      cin>>a[i];                 //输入n个车厢号
    for (i=1; i<=n-1; i++)       //冒泡排序另一种写法
      for (j=1; j<=n-i; j++)
       if (a[j]>a[j+1])          //判断车厢号是否逆序
       {
    swap(a[j],a[j+1]);
    s++;              //统计车厢旋转的次数
     };
    cout<<s;                     //最少的旋转次数
    return 0;    
 }

3. 插入排序

         插入排序思想：回忆一下打牌时抓牌的情景，为了方便打牌，抓牌时一般一边抓牌一边按花色和大小插入恰当的位置，当抓完所有的牌时，手中的牌便是有序的，这排序方法即插入排序。

       当读入一个元素时，在已经排序好的序列中，搜寻它正确的位置，再放入读入的元素。但不该忽略一个重要的问题：在插入这个元素前，应当先将将它后面的所有元素后移一位，以保证插入位置的原元素不被覆盖。

       例如:设n=8，数组a中8个元素是: 36,25,48,12,65,43,20,58，执行插入排序程序后，其数据变动情况：

第0步:[36] 25 48 12 65 43 20 58
第1步:[25 36] 48 12 65 43 20 58
第2步:[25 36 48] 12 65 43 20 58
第3步:[12 25 36 48] 65 43 20 58
第4步:[12 25 36 48 65] 43 20 58
第5步:[12 25 36 43 48 65] 20 58
第6步:[12 20 25 36 43 48 65] 58
第7步:[12 20 25 36 43 48 58 65]

程序如下：

#include<iostream>
using namespace std;
const int MAXN=10001;
int main()
{
      int n,i,j,k;  
      float temp,a[MAXN];
      cin>>n;
      for (i=0;i<n;i++)
         cin>>a[i];                      //输入n个数 
    for(i=0; i<n; i++)
    { 
       for(j=i-1; j>=0; j--)          //在前面有序区间中为a[i]找合适的插入位置 
         if (a[j]<a[i]) break;        //找到比a[i]小的位置就退出,插入其后 
       if (j!=i-1)
       {
          temp=a[i];                   //将比a[i]大的数据向后移 
          for(k=i-1;k>j;k--)
             a[k+1]=a[k];              //将a[i]放在正确位置上 
          a[k+1]=temp;
       }
    }
    for (i=0;i<n;i++)
        cout<<a[i]<<" ";            //输出排序的结果 
   return 0; 
}

4. 桶排序

        桶排序的思想是若待排序的值在一个明显有限范围内(整型)时，可设计有限个有序桶，待排序的值装入对应的桶（当然也可以装入若干个值），桶号就是待排序的值，顺序输出各桶的值，将得到有序的序列。

例：输入n个0到100之间的整数，由小到大排序输出。

【程序实现】

#include<iostream>
#include <cstring>
using namespace std;
int main()
     int b[101],n,i,j,k;
     memset(b,0,sizeof(b));             //初始化
     cin>>n;
     for (i=1;i<=n;i++)
     {
         cin>>k; b[k]++;                     //将等于k的值全部装入第k桶中
     }
     for (i=0;i<=100;i++)                  //输出排序结果
       while (b[i]>0)                          //相同的整数，要重复输出
       {
           cout<<i<<" "; b[i]--;             //输出一个整数后，个数减1
        }
      cout<<endl;    
}