各种排序算法综合(3)

都是算法程序

ext = 0;
for(i = 2; i <= len; i++)
{
//每次跟头结点比。头结点指向最小关键字结点。
for(pos = 0; (SL.r[pos].next != 0) && (SL.r[i].rc > SL.r[SL.r[pos].next].rc); pos = SL.r[pos].next)
;
tmp = SL.r[pos].next;
SL.r[pos].next = i;
SL.r[i].next = tmp;
}

//根据next值重排记录
for(tmp = SL.r[0].next, i = 1; i <= len; i++)
{
memcpy(&tmpNode, &SL.r[i], sizeof(SLNode));
pos = tmp;
while(pos < i)
pos = SL.r[pos].next;
if(pos == i)
{
tmp = SL.r[pos].next;//备份下一pos
continue;
}
SL.r[i].rc = SL.r[pos].rc;
SL.r[i].next = pos;//为使不断链(表此位置元素已移至pos处)
tmp = SL.r[pos].next;//备份下一pos
memcpy(&SL.r[pos], &tmpNode, sizeof(SLNode));
}

//根据静态链表赋值原数组使之有序
for(i = 0; i < len; i++)
a[i] = SL.r[i+1].rc;
}

//2.1. 起泡排序
void BubbleSort(int *a, int len)
{
int i, j, exchange = 1, tmp;
for(i = 0; (i < len-1) && exchange; i++)
{
exchange = 0;
for(j = 1; j < len - i; j++)
{
if (a[j] < a[j-1])
{
exchange = 1;
tmp = a[j-1];
a[j-1] = a[j];
a[j] = tmp;
}
}
}
}

//2.2. 快速排序
void QuickSort(int *a, int len)
{
int low = 0, high = len - 1;
QSort(a, low, high);
}

void QSort(int *a, int low, int high)
{
int pivot;
if(low >= high) return;
pivot = Partition(a, low, high);
QSort(a, low, pivot - 1);
QSort(a, pivot + 1, high);
}

int Partition(int *a, int low, int high)
{
int pivot = a[low];
while(low < high)
{
while((low < high) && (a[high] >= pivot)) high--;
a[low] = a[high];
while((low < high) && (a[low] <= pivot)) low++;
a[high] = a[low];
}
a[low] = pivot;
return low;
}

//3.1. 简单选择排序
void SimpleSelectSort(int *a, int len)
{
int i, j, k, tmp;

for(i = 0; i < len - 1; i++)
{
k = i;
for(j = i + 1; j < len; j++)
{ if(a[j] < a[k])
k = j;
}
if(k != i)
{
tmp = a[k];
a[k] = a[i];
a[i] = tmp;
}
}
}

//3.2. 树形选择排序
//将完全二叉树存在一静态数组中
//此树没有度为1的结点，故共有2n-1个结点(n为叶子数)
void TreeSelectSort(int *a, int len)
{
TreeNode *tree = (TreeNode *)malloc(2*len*sizeof(TreeNode));//0号结点不用，故多申请一个空间
int i, stime = 0, f;

memse
t(tree, 0, 2*len*sizeof(TreeNode));
for(i = len; i < 2*len; i++)
tree[i].rc = a[i - len];
//第一次建树，根为最小数
for(i = len - 1; i > 0; i--)