排序算法有很多种，这里在复习和分析的基础上，做一个自己的总结；
首先要知道有哪些排序算法，google一下，有云C语言7大经典排序算法（也有8大）。主要包括冒泡排序，快速排序，选择排序，插入排序，希尔排序，归并排序，堆排序，8大的还有基数排序。各有各的版本，代码写法也各不相同。所以这里以整理思路为先，代码只是作为自己的一个备份。
搞清楚的概念：稳定排序和不稳定排序，就看序列中两个值相等的数，排完序之后的相对位置是否改变，如果改变了就不稳定。
内部排序和外部排序，只用到内存即可完成排序的就叫内部排序，外部排序因为序列比较长，用到了外部存储。
算法好坏标准：时间复杂度和空间复杂度。分析T(n)=O(f(n))为主，这个还是比较简单的理解一下就行，因为这种方法本身也是一种统计估计。
针对3中存储结构，1、以一组连续的地址单元作为存储结构；2、以链表作为存储结构；3、和1一样存储，但是通过建立辅助表来进行排序。
插入类排序：直接插入排序，希尔排序；
第一个算法，直接插入算法，很简单，假如我们的数组是R[n+1]，第一个作为交换时用的中间变量；那么R[1]作为最初的有序区，从i=2开始不断插入R[i]，插入时跟有序区中的R[j]进行比较；R[0]在while循环中可以作为监视哨，以防下标变量j越界，避免了while循环检测j是否越界，测试循环条件的时间可以减少一半。
算法的时间复杂度为O(n2)；排序中最坏情况就是全逆序，最好情况，全正序；根据这样的两种情况来判断。
希尔排序，多了一个增量数组，有选择规则（使得增量值没有除1之外的公因子）如5.3.1；按照增量的值进行多轮排序，使得序列趋于正序列和交换次数较少的序列；希尔排序其实就是插入排序的改进版本。
算法复杂度O（nlgn）
交换类排序：冒泡排序和快速排序
冒泡排序，想法很简单，相邻两个元素比较，大的放后面，一趟一趟比，最后完成排序。快速排序就是对这一过程进行了优化；还有双向冒泡法，改进算法，这里不深入了。冒泡排序算法复杂度O(n2)
快速排序，这里首先要选取一个基准，一般都是一上来就吧R[0]作为基准，大的放在右边，小的放在左边，形成两个子序列，然后R[0]在中间，对两个子序列继续重复上一过程，直到序列里面的个数为1；从而可以看出，这个算法可以用递归。 算法复杂度O(n2)；但是他是目前基于比较的内部排序方法中平均性能最好的。但是快读排序不稳定。
选择类排序：直接选择排序，和直接插入排序作比较，其实差不多，不过这里是选择最小的一个作为有序列的R[1]，进行n-1趟排序。也是不稳定的，算法复杂度O(n2)
归并排序：顾名思义，是合并，将一些较小的有序的序列进行合并从而成为整个有序序列。他是稳定的排序，复杂度为O(nlgn)，一般应用时先采用直接插入排序得到几个有序序列，然后再进行归并，这样仍然是稳定的。
完了之后就是要把思路转化为程序。毕竟写出程序的能力才是最终要有的。
#include <stdio.h>
#include <stdlib.h>
#define n 8
typedef struct
{
int key;
}rectype;
rectype R[n+1];
void insertsort(rectype R[])
{
int i,j;
for(i=2;i<=n;i++)
{
if(R[i].key<R[i-1].key)
{
R[0]=R[i];
j=i-1;
while(R[0].key<R[j].key)
{
R[j+1]=R[j--];//jiang guanjianzi dayu R[i].key de jilu houyi
}
R[j+1]=R[0];
}
}
}
void shellsort(rectype R[],int d[],int t)
{
int i,j,k;
for(k=0;k<t;k++)
for(i=d[k]+1;i<=n;i++)
if(R[i].key<R[i-d[k]].key)
{
R[0]=R[i];
j=i-d[k];
while(j>0&&R[0].key<R[j].key)
{
R[j+d[k]]=R[i];
j=j-d[k];
R[j-d[k]]=R[0];
}
}
}
void bubblesort(rectype R[])
{
int i,j,swap;
for(i=1;i<n;i++)
{
swap=0;
for(j=n;j>i;j--)
if(R[j-1].key>R[j].key)
{
R[0]=R[j-1];
R[j-1]=R[j];
R[j]=R[0];
swap=1;
}
if(!swap) break;
}
}
int partition(rectype R[],int low,int high)
{
rectype pivot=R[low];
while(low<high)
{
while(low<high&&R[high].key>=pivot.key)
high--;
if(low<high)
R[low++]=R[high];
while(low<high&&R[low].key<=pivot.key)
low++;
if(low<high)
R[high--]=R[low];
}
R[low]=pivot;
return low;
}
void quicksort(rectype R[],int s,int t)
{
int i;
if(s<t)
{
i=partition(R,s,t);
quicksort(R,s,i-1);
quicksort(R,i+1,t);
}
}
void selectsort(rectype R[],int m)
{
int i,j,k;
rectype temp;
for(i=1;i<m;i++)
{
k=i;
for(j=i+1;j<=m;j++)
if(R[j].key<R[k].key)
k=j;
if(k!=i)
{
temp=R[i];
R[i]=R[k];
R[k]=temp;
}
}
}
void merge(rectype R[],int low,int mid,int high)
{
int i,j,k;
i=low;j=mid+1;k=0;
rectype *R1=(rectype*)malloc((high-low+1)*sizeof(rectype));
if(!R1){printf("failed");exit(0);}
while((i<=mid)&&(j<=high))
{
if(R[i].key<=R[j].key)
R1[k++]=R[i++];
else
R1[k++]=R[j++];
}
while(i<=mid) R1[k++]=R[i++];
while(j<=high) R1[k++]=R[j++];
for(k=0,i=low;i<high;k++,i++)
R[i]=R1[k];
}
void mergepass(rectype R[],int length)
{
int i=1;
while(i+2*length-1<=n)
{
merge(R,i,i+length-1,i+2*length-1);
i=i+2*length;
}
if((i+length-1)<n)
{
merge(R,i,i+length-1,n-1);
}
}
void mergesort(rectype R[])
{
int length;
for(length=1;length<n;length*=2)
mergepass(R,length);
}
int main()
{
int i;
int d[]={5,3,1};
rectype R[]={{0},{12},{16},{23},{58},{68},{2},{7},{9}};
insertsort(R);
for(i=1;i<=n;i++)
printf("%d ",R[i].key);
printf("\n");
shellsort(R,d,2);
for(i=1;i<=n;i++)
printf("%d ",R[i].key);
printf("\n");
bubblesort(R);
for(i=1;i<=n;i++)
printf("%d ",R[i].key);
printf("\n");
quicksort(R,1,8);
for(i=1;i<=n;i++)
printf("%d ",R[i].key);
printf("\n");
selectsort(R,8);
for(i=1;i<=n;i++)
printf("%d ",R[i].key);
printf("\n");
mergesort(R);
for(i=1;i<=n;i++)
printf("%d ",R[i].key);
printf("\n");
}