学步园

表插入排序的基础知识参考：插入排序（内部排序）

#include <stdio.h>

#define INIT_MAX 65535						//表头结点data最大值
#define SIZE 10								// 静态链表容量
typedef struct 
{											// 表结点类型
	int data;								// 记录项
    int next;								// 指针项
}SLNode;

typedef struct
{											// 静态链表类型
	SLNode r[SIZE + 1];						//0号单元为表头结点
	int length;								//链表当前长度
}SLinkListType;

void TableInsert(SLinkListType &SL, int D[], int n)			//由数组D建立n个元素的表插入排序的静态链表SL
{
	int p, q;
	SL.r[0].data = INIT_MAX;
	SL.r[0].next = 0;										// next域为0表示表尾(现为空表，初始化)
	for(int i = 0; i < n; i++)
	{
		SL.r[i+1].data = D[i];								// 将数组D的值赋给静态链表SL
		p = SL.r[0].next;
		q = 0;   
		while (SL.r[p].data < SL.r[i+1].data)
		{													// 静态链表向后移
			q = p;  
			p = SL.r[p].next;
		}
		
		SL.r[i+1].next = p;									//将当前记录插入静态链表
		SL.r[q].next = i + 1;
	}
	SL.length = n;

	return;
}

void Arrange(SLinkListType &SL)			//根据静态链表SL中各结点的指针值调整记录位置，使得SL中记录按关键字非递减有序顺序排列 
{											
	int p, q, temp;
	p = SL.r[0].next;					// p指示第一个记录的当前位置
	for(int i = 1; i < SL.length; i++)
	{									// SL.r[1..i-1]中记录已按关键字有序排列,第i个记录在SL中的当前位置应不小于i
		while(p < i) 
		{
			p = SL.r[p].next;			// 找到第i个记录，并用p指示其在SL中当前位置
		}
		q = SL.r[p].next;					//q指示尚未调整的表尾
		
		if (p != i)
		{ 
			temp = SL.r[p].data;
			SL.r[p].data = SL.r[i].data;
			SL.r[i].data = temp;			//交换记录，使第i个记录到位
			SL.r[p].next = SL.r[i].next;
			SL.r[i].next = p;				//指向被移走的记录，使得以后可由while循环找回
		}
		p = q;								//p指示尚未调整的表尾，为找第i+1个记录作准备
	}

	return;
}

int main(void)
{
	SLinkListType SL;
	int D[] = {10, 9, 8, 7, 6, 5};
	
	TableInsert(SL, D, 6);
	Arrange(SL);

	for (int i = 0; i < SL.length; i++)
	{
		printf("%d ", SL.r[i + 1].data);
	}
	printf("\n");

	return 0;
}