将杂乱无章的数据变得有规律。有各种各样的排序算法，看情况使用。
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 76 [97]
最后排序结果 13 27 38 49 49 65 76 97

代码：

void SelectSort(int R[])  //对R[1..N]进行直接选择排序
{
   for (int i=1;i<=n-1;i++)                   //做N - 1趟选择排序
      {
         K = I;
         For (int j=i+1;j<=n;j++)        //在当前无序区R[I..N]中选最小的元素R[K]
            {
               If (R[J] < R[K])  K = J;
           }
         If (K!=I)                                      //交换R[I]和R[K]
           { 
             Temp = R[I];
             R[I] = R[K]; 
             R[K] = Temp; 
           }
       }
} 

（时间复杂度为O（n^2）)

2.冒泡排序
（1）基本的冒泡排序
①基本思想
依次比较相邻的两个数，把大的放前面，小的放后面。即首先比较第1个数和第2个数，大数放前,小数放后。然后比较第2个数和第3个数……直到比较最后两个数。第一趟结束，最小的一定沉到最后。重复上过程,仍从第1个数开始,到最后第2个数，然后……
由于在排序过程中总是大数往前，小数往后，相当气泡上升，所以叫冒泡排序。
下面是6个元素的排序的过程
　 4 5 7 1 2 3
┗━━┛
5 4 7 1 2 3
┗━━┛
5 7 4 1 2 3
┗━━┛
5 7 4 1 2 3
┗━━┛
5 7 4 2 1 3
┗━━┛
第一趟结束

    5     7    4    2    3    ①
    ┗━━┛
    7     5    4    2    3    1
          ┗━━┛
    7     5    4    2    3    1
                ┗━━┛
    7     5    4    2    3    1
                      ┗━━┛       第二趟结束
    7     5    4    3    ②   1
       ┗━━┛
    7     5    4    3    2    1
          ┗━━┛
    7     5    4    3    2    1
                ┗━━┛              第三趟结束
    7     5    4    ③   2    1
   ┗━━┛
    7     5    4    3    2    1
          ┗━━┛                    第四趟结束
    7     5    ④    3   2    1
   ┗━━┛                           第五趟结束
    ⑦    ⑤   4    3    2    1

②算法实现

 for (int i=1;i<=n-1;i++)
             for (int j=1;j<=n-i;j++)
               if (a[j]<a[j+1])  
                  {
                     temp=a[j]; a[j]=a[j+1]; a[j+1]=temp;
                  }

（2）改进
上例中，可以发现，第二趟结束已经排好序。但是计算机此时并不知道已经排好序。所以，还需进行一次比较，如果没有发生任何数据交换，则知道已经排好序，可以不干了。因此第三趟比较还需进行，第四趟、第五趟比较则不必要。
我们设置一个布尔变量bo 来记录是否有进行交换。值为false表示本趟中进行了交换，true 则没有。代码如下:

int i=1;  
do 
{
   bo=true;
   for (int j=1;j<=n-I;j++)
     if (a[j]<a[j+1]) 
       {
          temp=a[j];    a[j]=a[j+1];   a[j+1]=temp;  
          bo=false; 
       }
　I++;
}
While (!bo);

3. 桶排序
桶排序的思想是若待排序的记录的关键字在一个明显有限范围内(整型)时，可设计有限个有序桶，每个桶装入一个值（当然也可以装入若干个值），顺序输出各桶的值，将得到有序的序列。
例：输入n个0到100之间的不相同整数，由小到大排序输出。

#include<iostream>
#include <cstring>
using namespace std;
Int main()
{
    int b[101],k,I,n;
    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]--;}    //输出排序结果
  cout<<endl;
}

4. 插入排序
插入排序是一种简单的排序方法，其算法的基本思想是：
假设待排序的数据存放在数组R[1..n]中，增加一个哨兵结点x。
(1) R[1]自成1个有序区，无序区为R[2..n];(2) 从i=2起直至i=n为止，将R[i]放在恰当的位置，使R[1..i]数据序列有序;
① x:=R[i];
② 将x与前i-1个数比较 , j:=i-1; while x<a[j] do j:=j-1;
③ 将R数组的元素从j位置开始向后移动: for k:=i downto j do a[k]:=a[k-1];
④ R[j]=x;
(3) 生成包含n个数据的有序区。.
例如:设n=8，数组R中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
第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]

代码：

void insertsort(int r[])  
                                                   //对r[1..n]按递增序进行插入排序，x是监视哨
{
 for (i=2;i<=n;i++)                       //依次插入r[2],...,r[n]
      {
        x=r[i]; 
        j= i-1;
        While (x< r[j])                     //查找r[i]的插入位置//
           {
              r[j+1] =r[j];                     //将大于r[i]的元素后移//
              j--;
           }
        r[j+1] = x;                             //插入r[I] //
     }
} 

5.快速排序
快速排序是对冒泡排序的一种改进。它的基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
假设待排序的序列为{a[L],a[L+1],a[L+2],……,a[R]}，首先任意选取一个记录（通常可选中间一个记作为枢轴或支点），然后重新排列其余记录，将所有关键字小于它的记录都放在左子序列中，所有关键字大于它的记录都放在右子序列中。由此可以将该“支点”记录所在的位置mid作分界线，将序列分割成两个子序列和。这个过程称作一趟快速排序（或一次划分）。
一趟快速排序的具体做法是：附设两个指针i和j，它们的初值分别为L和R，设枢轴记录取mid，则首先从j所指位置起向前搜索找到第一个关键字小于的mid的记录，然后从i所指位置起向后搜索，找到第一个关键字大于mid的记录，将它们互相交换，重复这两步直至i>j为止。
快速排序的时间的复杂性是O(nlog2n)，速度快,但它是不稳定的排序方法。就平均时间而言，快速排序是目前被认为是最好的一种内部排序方法
由以上讨论可知，从时间上看，快速排序的平均性能优于前面讨论过的各种排序方法，但快速排序需一个栈空间来实现递归。若每一趟排序都将记录序列均匀地分割成长度相接近的两个子序列，则栈的最大深度为log(n+1)。
代码：

void qsort(int l,int r)
{   int i,j,mid,p;
   i=l;
   j=r; 
   mid=a[(l+r) / 2];                  //将当前序列在中间位置的数定义为分隔数
   do
   {
      while (a[i]<mid) i++;       //在左半部分寻找比中间数大的数
      while (a[j]>mid) j--;      //在右半部分寻找比中间数小的数
      if (i<=j) 
         {                                //若找到一组与排序目标不一致的数对则交换它们
            p=a[i];
           a[i]=a[j];
           a[j]=p;
           i++;
           j--;                            //继续找
         }
   }
   while (i<=j);                                  //注意这里不能有等号
   if (l<j)  qsort(l,j);              //若未到两个数的边界，则递归搜索左右区间
   if (i<r)  qsort(i,r);
end;

6.归并排序
归并排序(Merge sort)就是利用归并操作把一个无序表排列成一个有序表的过程。二路归并排序的过程是首先把待排序区间（即无序表）中的每一个元素都看作为一个有序表，则n个元素构成n个有序表，接着两两归并（即第一个表同第二个表归并，第三个表同第四个表归并，…），得到[n/2]个长度为2的有序表（最后一个表的长度可能小于2），称此为一趟归并，然后再两两有序表归并，得到[[n/2]/2]个长度为4的有序表（最后一个表的长度可能小于4），如此进行下去，直到归并第[log2n]趟后得到一个长度为n的有序表为止。
归并排序算法我们用递归实现，先把待排序区间[s,t]以中点二分，接着把左边子区间排序，再把右边子区间排序，最后把左区间和右区间用一次归并操作合并成有序的区间[s,t]。对左右子区间的排序与原问题一样，所以我们可以调用同样的子程序，只是区间大小不一样。
代码：
归并简洁版

#include<iostream>
using namespace std;
void Merge_sort(int *a,int x,int y,int *t){
    if(y-x>1){
       int m=x+(y-x)/2;
       int p=x,q=m,i=x;  
       Merge_sort(a,x,m,t);
       Merge_sort(a,m,y,t);
       while(p<m||q<y){
        if(q>=y||(p<m&&a[p]<=a[q])) t[i++]=a[p++];
        else t[i++]=a[q++];
       }
       for(i=x;i<y;i++) a[i]=t[i];
    }
}
int main(){
    int a[100],t[100];
    int  i,n;
    cin>>n;
    for(i=0;i<n;i++)  cin>>a[i];
    Merge_sort(a,0,n,t);
    for(i=0;i<n;i++) cout<<t[i]<<' ';
}

归并排序完全版：

#include<iostream>
using namespace std;
int n;
void Merge(int (&a)[100],int low,int mid,int high){
    int i,j,k;
    int r[100]={0};
    i=low; j=mid+1; k=low;
    while(i<=mid&&j<=high){
        if(a[i]<=a[j]){
            r[k]=a[i];
            i++;
            k++;
        }
        if(a[j]<a[i]){
            r[k]=a[j];
            j++;
            k++;
        }
    }
    for(;i<=mid;i++){
        r[k]=a[i];
        k++;
    }
    for(;j<=high;j++){
        r[k]=a[i];
        k++;
    }
    for(i=low;i<=high;i++){
        a[i]=r[i];
    }
}
//拆分数组 
void MergeSort(int (&a)[100],int low,int high){
    int mid;
    int low1=low;
    int high1=high;
    if(low<high){
        mid=(low+high)/2; 
        MergeSort(a,low1,mid);
        MergeSort(a,mid+1,high1);
        Merge(a,low1,mid,high1);
    }
}
int main(){
    int a[100];
    int i;
    cin>>n;
    for(i=1;i<=n;i++){
        cin>>a[i];
    }
    MergeSort(a,1,n);
    for(i=1;i<=n;i++){
        cout<<a[i]<<' ';
    }
    cout<<endl;
    return(0);
}           

7.c++标准模板库STL（sort版）
使用排序算法必须包含 algorithm 头文件
　　　自带排序算法的一般形式为：

//将数组arr的下标为m的元素到下标为n-1的元素进行从小到大排序
　　　sort(arr+m,arr+n);       
　　　sort(arr+m,arr+n,comp);   //与sort(arr+m,arr+n); 相比，这个                             //写法可以自己定义排序的规则
　　　             //其中，comp为自定义的函数

对于sort(arr+m,arr+n) 我们举个简单的例子：

　　　//这个程序实现从键盘读入10个数，然后从小到大输出的功能
　　　#include<iostream>
　　　#include<algorithm>
　　　using namespace std;
　　　int a[10];
　　　int main()
　　　{
　　　 for (int i=0;i<10;++i) cin>>a[i];
　　　 sort(a+0,a+10);
　　　 for (int i=0;i<10;++i) cout<<a[i]<<' ';
　　　 cout<<endl;
　　　 return 0;
　　　}

当然，有时我们需要从大到小的进行排序。那么我们可以用 sort(arr+n,arr+m,comp)进行排序。
不过，在调用sort(arr+n,arr+m,comp) 之前我们需要自己写个 comp函数。

　　　从大到小排序的comp函数可以这样写：
　　　

int my_comp(const int & a,const int & b)  
　　　{
　　　return a>b;      //在两元素相同时一定要返回 0 或者 false
　　　}  //comp函数的名字是由我们自己决定的      

代码：

　　　#include<iostream>
　　　#include<algorithm>
　　　using namespace std;
　　　int a[10];
　　　int my_comp(const int & a,const int & b)
　　　{
　　　 return a>b;     //如果a>b 则返回1 ，否则返回 0
　　　}
　　　int main()
　　　{
　　　 for (int i=0;i<10;++i) cin>>a[i];
　　　 sort(a+0,a+10,my_comp);
　　　 for (int i=0;i<10;++i) cout<<a[i]<<' ';
　　　 cout<<endl;
　　　 return 0; 
        }

　　　在更多情况下，我们不仅对一个特征进行排序，而是多个特征。例如将学生的成绩进行排序，当然用上面的做法是行不通的。这时，我们就想到了结构体这种数据类型。当我们采用sort()函数的默认规则排序结构体时，sort()默认结构体中的第一个成员为第一关键字，第二个成员为第二关键字，……，第N个元素为第N关键字，然后从小到大排序。
　　　例如我们要将学生的成绩从大到小排序，当成绩相同时，根据姓名字典序小的优先的规则排进行序。显然我们无法采用默认规则进行排序。

　　　这时我们可以定义这样的comp:
　　　

int score_comp(const student & a,const student & b)
　　　{
　　　 if (a.score>b.score) return 1;
　　　 if (a.score<b.score) return 0;
　　　 if (a.name<b.name) return 1;
　　　 return 0;
　　　}

8.c++标准模板库STL（优先队列版）
自己参悟吧……道理同7

#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
struct node
{
    string name;
    int sumscore;
    int mathscore; 
}p[1001];
struct cmp
{
    bool operator()(const node &a,const node &b)
    {
        if(a.sumscore>b.sumscore) return true;
//      if(a.sumscore<b.sumscore) return false;
//      if(a.mathscore>b.mathscore) return true;
        return false;
    }
//  bool operator()(const node &a,const node &b)
//  {
//      
//  }
};
int main()
{
    int n;cin>>n;
    priority_queue<node,vector<node>,cmp> q;
    for(int i=1;i<=n;i++)
    {
        cin>>p[i].name;
        cin>>p[i].sumscore>>p[i].mathscore;
        q.push(p[i]);
    }
    for(int i=1;i<=n;i++)
    {
        cout<<q.top().name<<" ";
        q.pop();
    }
}    

9.各种排序算法的比较
1.稳定性比较
插入排序、冒泡排序、二叉树排序、二路归并排序及其他线形排序是稳定的。
选择排序、希尔排序、快速排序、堆排序是不稳定的。
2.时间复杂性比较
插入排序、冒泡排序、选择排序的时间复杂性为O(n2)；快速排序、堆排序、归并排序的时间复杂性为O(nlog2n)；桶排序的时间复杂性为O(n);
若从最好情况考虑，则直接插入排序和冒泡排序的时间复杂度最好，为O(n)，其它算法的最好情况同平均情况相同；若从最坏情况考虑，则快速排序的时间复杂度为O(n2)，直接插入排序和冒泡排序虽然平均情况相同，但系数大约增加一倍，所以运行速度将降低一半，最坏情况对直接选择排序、堆排序和归并排序影响不大。
由此可知，在最好情况下，直接插入排序和冒泡排序最快；在平均情况下，快速排序最快；在最坏情况下，堆排序和归并排序最快。
3.辅助空间的比较
  桶排序、二路归并排序的辅助空间为O(n)，快速排序的辅助空间为O(log2n)，最坏情况为O(n)，其它排序的辅助空间为O(1);
4.其它比较
插入、冒泡排序的速度较慢，但参加排序的序列局部或整体有序时，这种排序能达到较快的速度。反而在这种情况下，快速排序反而慢了。
当n较小时，对稳定性不作要求时宜用选择排序，对稳定性有要求时宜用插入或冒泡排序。
若待排序的记录的关键字在一个明显有限范围内时,且空间允许是用桶排序。
当n较大时，关键字元素比较随机，对稳定性没要求宜用快速排序。
当n较大时，关键字元素可能出现本身是有序的，对稳定性没有要求时宜用堆排序
　 快速排序是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短；
堆排序所需的辅助空间少于快速排序，并且不会出现快速排序可能出现的最坏情况。这两种排序都是不稳定的。