各种排序算法综合(4)

都是算法程序

{
tree[i].rc = (tree[2*i].rc < tree[2*i + 1].rc) ? tree[2*i].rc : tree[2*i+1].rc;
tree[i].child = (tree[2*i].rc < tree[2*i + 1].rc) ? (2*i) : (2*i+1);
if (tree[tree[i].child].child)//如果孩子不是叶子结点
tree[i].child = tree[tree[i].child].child;
}
//共选择len次次小数
while(stime < len)
{
//输出根
a[stime++] = tree[1].rc;
tree[tree[1].child].rc = MAX;
//选次小的
for(f = tree[1].child/2; f > 0; f/=2)
{
tree[f].rc = (tree[2*f].rc < tree[2*f + 1].rc) ? tree[2*f].rc : tree[2*f+1].rc;
tree[f].child = (tree[2*f].rc < tree[2*f + 1].rc) ? (2*f) : (2*f+1);
if (tree[tree[f].child].child)//如果孩子不是叶子结点
tree[f].child = tree[tree[f].child].child;
}
}
free(tree);
}

//3.3. 堆排序
void HeapSort(int *a, int len)
{
//为使算法清晰，重分配数组使下标从1开始
int *b = (int *)malloc((len+1)*sizeof(int));
int i, tmp;
memcpy(b+1, a, len*sizeof(int));
//第一次建大顶堆
for(i = len/2; i > 0; i--)
HeapAdjust(b, i, len);
//选len-1次根出来
for(i = 1; i < len; i++)
{
tmp = b[1]; b[1] = b[len - i + 1]; b[len - i + 1] = tmp;
HeapAdjust(b, 1, len-i);
}

memcpy(a, b+1, len*sizeof(int));
free(b);
}

//完全二叉树中，除a[s]外，a[s+1..len]符合堆定义
//调整树，使得a[s..len]符合堆定义。
void HeapAdjust(int *a, int s, int len)
{
int rc = a[s];
int i;
for(i = s*2; i <= len; i*=2)
{
if((i < len) && (a[i] < a[i+1])) i++;
if (rc > a[i])//不需要调整，已经是堆了
break;
a[s] = a[i];
s = i;
}
a[s] = rc;
}

//4.1. 归并排序
void MergeSort(int *a, int len)
{
MSort(a, 0, len-1);
}
//将a[s..n]归并为t[s..n]
void MSort(int *a, int s, int n)
{
int m = (s + n)/2;
if(s == n) return;
else
{
MSort(a, s, m);
MSort(a, m+1, n);
Merge(a, s, m, n);
}
}

void Merge(int *a, int i, int m, int n)
{
int *b = (int *)malloc((n+1)*(sizeof(int)));
int k = i, j = m+1, ii = i;
for(; (i<=m) && (j<=n); k++)
{
if (a[j] < a[i]) b[k] = a[j++];
else
b[k] = a[i++];
}
while (k<=n && i<=m) b[k++] = a[i++];
while (k<=n && j<=n) b[k++] = a[j++];
memcpy(a+ii, b+ii, (n-ii+1)*(sizeof(int)));
free(b);
}
--------------------------------
//4.1. 基数排序
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define NUM_OF_KEY 3//譬如一个数是几位数，这里假设是3位数
#define NUM 1
0//有几个数要排序
#define RADIX 10
#define MAX_SPACE 100

typedef struct
{
char keys[NUM_OF_KEY];
int n