排序算法程序.doc

文档介绍：插入排序
// 插入排序
void InsertSort(int array[], int length)
{
int i, j, key;
for (i = 1; i < length; i++)
{
key = array[i];
// 把i之前大于array[i]的数据向后移动
for (j = i - 1; j >= 0 && array[j] > key; j--)
{
array[j + 1] = array[j];
}
// 在合适位置安放当前元素
array[j + 1] = key;
}
}
希尔排序
// shell排序
void ShellSort(int array[], int length)
{
int temp;
// 增量从数组长度的一半开始,每次减小一倍
for (int increment = length / 2; increment > 0; increment /= 2)
for (int i = increment; i < length; ++i)
{
temp = array[i];
// 对一组增量为increment的元素进行插入排序
for (int j = i; j >= increment; j -= increment)
{
// 把i之前大于array[i]的数据向后移动
if (temp < array[j - increment])
{
array[j] = array[j - increment];
}
else
{
break;
}
}
// 在合适位置安放当前元素
array[j] = temp;
}
}
堆排序
// array是待调整的堆数组,i是待调整的数组元素的位置,length是数组的长度
void HeapAdjust(int array[], int i, int nLength)
{
int nChild, nTemp;
for (nTemp = array[i]; 2 * i + 1 < nLength; i = nChild)
{
// 子结点的位置是父结点位置* 2 + 1
nChild = 2 * i + 1;
// 得到子结点中较大的结点
if (nChild != nLength - 1 && array[nChild + 1] > array[nChild])
++nChild;
// 如果较大的子结点大于父结点那么把较大的子结点往上移动,替换它的父结点
if (nTemp < array[nChild])
{
array[i] = array[nChild];
}
else // 否则退出循环
{
break;
}
}
// 最后把需要调整的元素值放到合适的位置
array[i] = nTemp;
}
// 堆排序算法
void HeapSort(int array[], int length)
{
// 调整序列的前半部分元素,调整完之后第一个元素是序列的最大的元素
for (int i =