各种排序算法综合(2)

都是算法程序

tmp = a[i];
for(j = i - 1; (tmp < a[j]) && (j >= 0); j--)
a[j+1] = a[j];
a[j+1] = tmp;
}
}

//1.2.折半插入排序
void InsertSortB(int *a, int len)
{
int i, j, tmp, low, mid, high;
for(i = 1; i < len; i++)
{
tmp = a[i];
low = 0; high = i - 1;
while (low <= high)
{
mid = (low + high)/2;
if(a[i] < a[mid])
high = mid - 1;
else
low = mid + 1;
}
for(j = i - 1; j > high; j--)
a[j+1] = a[j];
a[low] = tmp;
}
}

//1.3. 2-路插入排序
void InsertSort2path(int *a, int len)
{
int i, j, first, final, low, mid, high;
int *d = (int *)malloc(len*sizeof(int));
memset(d, 0, len*sizeof(int));
first = len;//后半有序表开始的下标值，以后每插入则-1
final = 0;//前半有序表最后一个下标志，以后每插入则+1
d[0] = a[0];

for(i = 1; i < len; i++)
{
if(a[i] < a[0])//插入到后半的有序表中
{
//使用折半查找在后半的有序表中
low = first; high = len - 1;
while (low <= high)
{
mid = (low + high)/2;
if(a[i] < d[mid])
high = mid - 1;
else
low = mid + 1;
}
for(j = first; j < low; j++)
d[j-1] = d[j];
d[high] = a[i];
first--;
}
else
{
//使用折半查找在前半的有序表中
low = 0; high = final;
while (low <= high)
{
mid = (low + high)/2;
if(a[i] < d[mid])
high = mid - 1;
else
low = mid + 1;
}
for(j = final; j > high; j--)
d[j+1] = d[j];
d[low] = a[i];
final++;
}
}

for(i = 0; i < len; i++)
a[i] = d[(first + i)%len];
free(d);
}

//1.4. SHELL排序
void InsertSortShell(int *a, int len)
{
int i = 0;
int d[3] = { 5, 3, 1 };
for(; i < 3; i++)
ShellOnce(a, d[i], len);
}

//以增量d进行一遍shell
void ShellOnce(int *a, int d, int len)
{
int i, tmp, j;
for(i = d; i < len; i++)
{
tmp = a[i];
for(j = i - d; (j >= 0) && (a[j] > tmp); j -= d)
a[j+d] = a[j];
a[j+d] = tmp;
}
}

//1.5. 表插入排序
void InsertSortSTbl(int *a, int len)
{
SLinkListType SL;
int i = 0, pos, tmp;
SLNode tmpNode;

memset(&SL, 0, sizeof(SLinkLis
tType));
//用原数组初始化静态链表。下标为0的结点做头结点。
for(; i < len; i++)
SL.r[i+1].rc = a[i];
SL.length = len+1;

//令成循环链表
SL.r[0].next = 1;
SL.r[1].n