4、堆排序法
堆的定义：堆是一个完全二叉树，树中每个结点对应于原始数据的一个记录，并且每个结点应满足以下条件：非叶结点的数据大于或等于其左、右孩子结点的数据（若是按从大到小的顺序排序，则要求非叶结点的数据小于或等于其左、右孩子结点的数据）。
步骤：1、构成堆
（1）将无序数据放入完全二叉树的各结点。
（2）由二叉树的下层向上层逐层对父子结点的数据进行比较，使用一种称为“筛”的运算进行结点数据的调整，直到使结点最后满足堆的条件为止。
2、利用堆排序
（1）取堆的根结点（最大值），将其放到数组的最后。
（2）重新执行构成堆的方法，对堆进行重新构成。此时，应将最后一个结点排除在外。
（3）重复上述过程，逐步从根结点取出最大值，放入到数组的后面，再对剩下的结点重新构成堆，直到只剩下一个结点，即可得到有序的数据。
源码：
#include <stdio.h>
#include <stdlib.h>
#define ARRAYLEN 10
void HeapAdjust(int a[], int s, int n) //构成堆
{
int j,t;
while(2*s+1 < n) //第s个结点有右子树
{
j = 2*s+1;
if((j+1) < n)
{
if(a[j] < a[j+1]) //左子树小于右子树，则需要比较右子树
j++; //序号增加1，指向右子树
}
if(a[s] < a[j]) //比较s与j为序号的数据
{
t = a[s]; //交换数据
a[s] = a[j];
a[j] = t;
s = j; //堆被破坏，需要重新调整
}
else //不再需要调整
break; //退出循环
}
}
void HeapSort(int a[], int n) //堆排序
{
int t,i,j;
for(i = n/2 - 1; i >= 0; i--) //将a[0]至a[n-1]构成堆
HeapAdjust(a,i,n);
for(i = n - 1; i > 0; i--) //取根结点与末结点交换
{
t = a[0]; //与第i个记录交换
a[0] = a[i];
a[i] = t;
HeapAdjust(a,0,i); //将a[0]至a[i]重新调整
}
}
int main()
{
int i,a[ARRAYLEN] = {23,32,14,76,2,98,65,34,23,10}; //定义数组
HeapSort(a,ARRAYLEN);
printf("排序后：");
for(i = 0; i < ARRAYLEN; i++) //输出排序后的结果
printf("%d ",a[i]);
printf("\n");
system("pause");
return 0;
}
5、直接插入排序
算法描述：
（1）对于第一个元素，因为没有比较，将其作为已经有序的序列。
（2）从数组中获取下一个元素，在已经排序的元素序列中从后向前扫描，并进行判断。
（3）若排序序列的元素大于新元素，则将该元素移到下一位置
（4）重复步骤（3），直到找到已排序的元素小于或者等于新元素的位置
（5）将新元素插入到该位置
（6）重复步骤（2）~步骤（5），直到将数组中的数据处理完
源码：
#include <stdio.h>
#include <stdlib.h>
#define ARRAYLEN 10
void InsertSort(int a[], int n) //直接插入排序
{
int i,j,t;
for(i = 1; i < n; i++)
{
t = a[i]; //取出一个未排序的数据
for(j=i - 1; j >= 0 && t<a[j];j--) //在排序序列中查找位置
a[j+1] = a[j]; //向后移动数据
a[j+1] = t; //插入数据到序列
}
}
int main()
{
int i,a[ARRAYLEN] = {23,32,14,76,2,98,65,34,23,10}; //定义数组
InsertSort(a,ARRAYLEN); //调用插入排序函数
printf("排序后：");
for(i = 0; i < ARRAYLEN; i++)
printf("%d ",a[i]);
system("pause");
return 0;
}