在学习数据结构时，总感觉讲的排序太多了 ，一直都记不住，现在来总结一下。
下面都假设是从小到大排序：
1、插入排序
这算是比较简单的排序，类似于我们打牌时插牌的方法。
从第二个元素开始，拿他跟他前面的元素比较，如果遇到比他大的 ， 就互相交换，遇到比他小的就推出。
这个算法比较简单，就不过多的说了。
代码：
#include <iostream>
using namespace std;
template<typename T>//这里运用了模版
void stright_insert_sort(T a[100] , int n)
{
int i , j;
for(i = 2; i <= n; i++)
{
a[0] = a[i];//把比较那个元素先存储在a[0] ， 中
for(j = i-1; a[0]<a[j]; j--)
a[j+1] = a[j];
a[j+1] = a[0];
}
}
int main()
{
int a[100];
int n;
cin>>n;
int i;
for(i = 1; i <= n; i++)
cin>>a[i];
return 0;
}
时间复杂度：最好是O（n） ， 最坏是O（n^2）
这个算法还有一种优化的方法：在进行比较时，我们可以用二分查找的方法，来进行查找，这样就省掉了比较的操作，可以直接进行移动。
2、希尔排序
希尔排序又叫缩小增量排序。
算法思想：先取一个小于n的整数d1作为第一个增量，把数组中的记录分成d1个组，所有距离（在数组中的位置）对d1余数相同的放在同一个小组，然后再对这些小组分别进行插入排序。然后再去第二个增量d2，d2<d1 ， 重复上面的操作。直到所取的增量为1，注意最后一个增量必须为1。
代码：
//希尔排序
#include <iostream>
#include <stdio.h>
using namespace std;
int a[100];
void stright_insert_sort(int n , int f , int delta)
{
int i , j;
for(i = f; i <= n; i += delta)
{
a[0] = a[i];
for(j = i-delta; j >= 1 && a[0]<a[j]; j -= delta)
a[j+delta] = a[j];
a[j+delta] = a[0];
}
}
int main()
{
int n , i , delta;
cin>>n;
for(i = 1; i <= n; i++)
cin>>a[i];
for(delta = n/3; delta > 3; delta /= 3)
{
for(i = 1; i <= delta; i++)
stright_insert_sort(n , i , delta);
}
stright_insert_sort(n , 1 , 1);
for(i = 1; i <= n; i++)
cout<<a[i]<<" ";
cout<<endl;
return 0;
}
3、归并排序
归并排序类似于分治法，归并排序分2路归并和多路归并，我们只分析2路归并。
对于一个序列，我们从中间把它分开，得到两个序列，重复这样的操作，直到某段序列只剩下一个元素时。每段序列排好序之后，我们再把这两端序列合并成一段序列，这就是归并。
因此归并排序分两种实现：1、递归归并 2、非递归归并。 我们只介绍递归归并
代码：
//2路归并排序
//用递归实现的归并排序
#include <iostream>
#include <stdio.h>
using namespace std;
int a[100];
int n;
void merge_sort_merge(int front , int rear , int mid);
void merge_sort(int front , int rear )
{
if(front >= rear) return ;
int mid = (front+rear)/2;
merge_sort(front , mid);
merge_sort(mid+1 , rear);
merge_sort_merge(front , rear , mid);
}
void merge_sort_merge(int front , int rear , int mid)
{
int i , j , k = front;
int temparray[100];
for(i = front; i <= rear; i++)
temparray[i] = a[i];
for(i = front , j = mid+1; i<=mid && j <= rear; )
{
if(temparray[i] < temparray[j])
{
a[k++] = temparray[i++];
}
else
{
a[k++] = temparray[j++];
}
}
if(i <= mid)
{
for( ; i <= mid; i++)
a[k++] = temparray[i];
}
else
{
for( ; j <= rear; j++)
a[k++] = temparray[j];
}
}
int main()
{
cin>>n;
int i;
for(i = 0; i < n; i++)
cin>>a[i];
merge_sort(0 , n-1);
for(i = 0; i < n; i++)
cout<<a[i]<<" ";
cout<<endl;
return 0;
}
还有效率比较很的快排和堆排 ， 下次再介绍。
原文：http://blog.csdn.net/zengchen__acmer/article/details/23946205