插入排序
1.直接插入排序
原理：将数组分为无序区和有序区两个区，然后不断将无序区的第一个元素按大小顺序插入到有序区中去，最终将所有无序区元素都移动到有序区完成排序。
要点：设立哨兵，作为临时存储和判断数组边界之用。
实现：
void InsertSort(Nodetype p[],int length) { int i,j;//分别为有序区和无序区指针 for(i=1;i<length;i++)//逐步扩大有序区 { j=i+1; if(p[j]<p[i]) { p[0]=p[j];//存储待排序元素 while(p[0]<p[i])//查找在有序区中的插入位置，同时移动元素 { p[i+1]=p[i];//移动 i--; } p[i+1]=p[0];//将元素插入 } i=j-1;//还原有序区指针 } }
2.希尔排序
原理：又称增量缩小排序。先将序列按增量划分为元素个数相同的若干组，使用直接插入排序法进行排序，然后不断缩小增量直至为1，最后使用直接插入排序完成排序。
要点：增量的选择以及排序最终以1为增量进行排序结束。
实现：
void ShellSort(Nodetype p[],int d) { while(d>=1)//直到增量缩小为1 { Shell(p,d); d=d/2;//缩小增量 } } void Shell(Nodetype p[],int d) { int i,j; int length=strlen(p); for(i=d+1;i<length) { if(p[i]<p[i-d]) { p[0]=p[i]; j=i-d; while(j>0&&p[j]>p[0]) { p[j+d]=p[j]; j=j-d; } p[j+d]=p[0]; } } }
交换排序
1.冒泡排序
原理：将序列划分为无序和有序区，不断通过交换较大元素至无序区尾完成排序。
要点：设计交换判断条件，提前结束以排好序的序列循环。
实现:
void BubbleSort(Nodetype p[]) { int i,j; int ischanged;//设计跳出条件 for(j=n-1;j<0;j--) { ischanged=0; for(i=0;i<j;i++) { if(p[i]>p[i+1])//如果发现较重元素就向后移动 { int temp=p[i]; p[i]=p[i+1]; p[i+1]=temp; ischanged=1; } } if(!ischanged)//若没有移动则说明序列已经有序，直接跳出 break; } }
2.快速排序
原理：不断寻找一个序列的中点，然后对中点左右的序列递归的进行排序，直至全部序列排序完成，使用了分治的思想。
要点：递归、分治
基本思想：
1．先从数列中取出一个数作为基准数。
2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
3．再对左右区间重复第二步，直到各区间只有一个数。
选择排序
1.直接选择排序
原理：将序列划分为无序和有序区，寻找无序区中的最小值和无序区的首元素交换，有序区扩大一个，循环最终完成全部排序。
要点：
实现：
void SelectSort(Nodetype p[],int length) { int i,j,k;//分别为有序区，无序区，无序区最小元素指针 for(i=0;i<length;i++) { k=i; for(j=i+1;j<length;j++) if(p[j]<p[k]) k=j; if(k!=i)//若发现最小元素，则移动到有序区 { int tmp=p[k]; p[k]=p[i]; p[i]=tmp; } } }
2.堆排序
原理：利用大根堆或小根堆思想，首先建立堆，然后将堆首与堆尾交换，堆尾之后为有序区。
要点：建堆、交换、调整堆
操作过程如下：
1)初始化堆：将R[1..n]构造为堆；
2)将当前无序区的堆顶元素R[1]同该区间的最后一个记录交换，然后将新的无序区调整为新的堆。
因此对于堆排序，最重要的两个操作就是构造初始堆和调整堆，其实构造初始堆事实上也是调整堆的过程，只不过构造初始堆是对所有的非叶节点都进行调整。
下面举例说明：
给定一个整形数组a[]={16,7,3,20,17,8}，对其进行堆排序。
首先根据该数组元素构建一个完全二叉树，得到
20和16交换后导致16不满足堆的性质，因此需重新调整
(初始堆)
这样就得到了初始堆。即每次调整都是从父节点、左孩子节点、右孩子节点三者中选择最大者跟父节点进行交换(交换之后可能造成被交换的孩子节点不满足堆的性质，因此每次交换之后要重新对被交换的孩子节点进行调整)。
有了初始堆之后就可以进行排序了
此时3位于堆顶不满堆的性质，则需调整继续调整
接下来和倒数第二个元素交换，再调整
归并排序
原理：将原序列划分为有序的两个序列，然后利用归并算法进行合并，合并之后即为有序序列。
要点：归并、分治
实现：
Void MergeSort(Node L[],int m,int n)
{
Int k;
If(m<n)
{
K=(m+n)/2;
MergeSort(L,m,k);
MergeSort(L,k+1,n);
Merge(L,m,k,n);
}
}
基数排序
原理：将数字按位数划分出n个关键字，每次针对一个关键字进行排序，然后针对排序后的序列进行下一个关键字的排序，循环至所有关键字都使用过则排序完成。
要点：对关键字的选取，元素分配收集。
实现：
Void RadixSort(Node L[],length,maxradix)
{
Int m,n,k,lsp;
k=1;m=1;
Int temp[10][length-1];
Empty(temp); //清空临时空间
While(k<maxradix) //遍历所有关键字
{
For(int i=0;i<length;i++) //分配过程
{
If(L[i]<m)
Temp[0][n]=L[i];
Else
Lsp=(L[i]/m)%10; //确定关键字
Temp[lsp][n]=L[i];
n++;
}
CollectElement(L,Temp); //收集
n=0;
m=m*10;
k++;
}
}