严蔚敏数据结构内部排序所提十种方法汇总

#include 
#include 
#define MAXSIZE 100
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status;
typedef int KeyType;
typedef struct
{
	KeyType key;
}Record;
typedef Record ElemType;
typedef struct
{
	ElemType r[MAXSIZE + 1];
	int length;
}SqList;
Status EQ(KeyType key1, KeyType key2)
{
	if (key1 == key2)
		return TRUE;
	else
		return FALSE;
}
Status LT(KeyType key1, KeyType key2)
{
	if (key1 < key2)
		return TRUE;
	else
		return FALSE;
}
Status LE(KeyType key1, KeyType key2)
{
	if (key1 <= key2)
		return TRUE;
	else
		return FALSE;
}
Status MT(KeyType key1, KeyType key2)
{
	if (key1 > key2)
		return TRUE;
	else
		return FALSE;
}
Status ME(KeyType key1, KeyType key2)
{
	if (key1 >= key2)
		return TRUE;
	else
		return FALSE;
}
void InputKeyType(KeyType* key)
{
	printf("请输入关键词n");
	scanf("%d", key);
}
void InputRecord(Record* R)
{
	printf("请输入记录的数据n");
	InputKeyType(&(R->key));
}
void CreatSqList(SqList* L)
{
	printf("请输入顺序表的元素数目n");
	scanf("%d", &(L->length));
	for (int i = 1; i <= L->length; i++)
		InputRecord(&(L->r[i]));
}
void PrintRecord(Record R)
{
	printf("%d", R.key);
}
void PrintSqList(SqList L)
{
	for (int i = 1; i <= L.length; i++)
	{
		PrintRecord(L.r[i]);
		printf("t");
	}
	printf("n");
}
void KeyWordAssign(KeyType* destination, KeyType source)
{
	(*destination) = source;
}
void KeyWordPrint(KeyType key)
{
	printf("%dn", key);
}
void RecordAssign(Record* R1, Record R2)
{
	KeyWordAssign(&(R1->key), R2.key);
}


//直接插入排序
void InsertSort(SqList* L)
{
	for (int i = 2; i <= L->length; i++)
	{
		int j = i - 1;
		RecordAssign(&(L->r[0]), L->r[i]);
		while (LT(L->r[0].key, L->r[j].key))
		{
			RecordAssign(&(L->r[j + 1]), L->r[j]);
			j--;
		}
		RecordAssign(&(L->r[j + 1]), L->r[0]);
	}
}


//折半插入排序
void BInsertSort(SqList* L)
{
	for (int i = 2; i <= L->length; i++)
	{
		int low = 1, high = i - 1;
		RecordAssign(&(L->r[0]), L->r[i]);
		int mid = (low + high) / 2;
		while (low <= high)
		{
			if (LT(L->r[mid].key, L->r[0].key))
				low = mid + 1;
			else
			{
				if (MT(L->r[mid].key, L->r[0].key))
					high = mid - 1;
				else
					break;
			}
			mid = (low + high) / 2;
		}
		for (int j = i - 1; j > mid; j--)
			RecordAssign(&(L->r[j + 1]), L->r[j]);
		RecordAssign(&(L->r[mid + 1]), L->r[0]);
	}
}


//2-路插入排序n(插入排序改进）
typedef struct
{
	ElemType data;
	int cur;
}SLinkNode;
typedef struct
{
	SLinkNode node[MAXSIZE + 1];
	int length;
}SLinkList;
Status CreatSLinkList(SLinkList* L)
{
	printf("请输入链表的元素个数n");
	scanf("%d", &L->length);
	for (int i = 1; i <= L->length; i++)
	{
		InputRecord(&L->node[i].data);
		L->node[i - 1].cur = -1;
	}
	L->node[L->length].cur = -1;
	return OK;
}
Status InsertSort_TwoRoutes(SLinkList* L)
{
	L->node[0].cur = 1;
	L->node[1].cur = 0;
	for (int i = 2; i <= L->length; i++)
	{
		if (ME(L->node[i].data.key, L->node[1].data.key))
		{
			int j = L->node[1].cur, k = 1;
			while (j > 0 && MT(L->node[i].data.key, L->node[j].data.key))
			{
				k = j;
				j = L->node[j].cur;
			}
			L->node[i].cur = L->node[k].cur;
			L->node[k].cur = i;
		}
		else
		{
			int j = L->node[0].cur, k = 0;
			while (j != 1 && MT(L->node[i].data.key, L->node[j].data.key))
			{
				k = j;
				j = L->node[j].cur;
			}
			L->node[i].cur = L->node[k].cur;
			L->node[k].cur = i;
		}
	}
	return OK;
}
void Exchange_SLink(SLinkNode* L1, SLinkNode* L2)
{
	SLinkNode temp;
	temp.cur = L1->cur;
	RecordAssign(&temp.data, L1->data);
	L1->cur = L2->cur;
	RecordAssign(&L1->data, L2->data);
	L2->cur = temp.cur;
	RecordAssign(&L2->data, temp.data);
}
void Arrange(SLinkList* L)
{
	int i = L->node[0].cur, j;
	for (int count = 1; count <= L->length; count++)
	{
		while (i < count)
			i = L->node[i].cur;
		j = L->node[i].cur;
		Exchange_SLink(&L->node[count], &L->node[i]);
		L->node[count].cur = i;
		i = j;
	}
}


//希尔排序（增量序列有许多取法，但最后一个增量值必须为1）
void ShellInsert(SqList* L, int dk)
{
	for (int i = dk + 1; i <= L->length; i++)
	{
		RecordAssign(&L->r[0], L->r[i]);
		int j;
		for (j = i; j >= dk + 1; j -= dk)
		{
			if (LT(L->r[0].key, L->r[j - dk].key))
				RecordAssign(&L->r[j], L->r[j - dk]);
			else
				break;
		}
		RecordAssign(&L->r[j], L->r[0]);
	}
}
void ShellSort(SqList* L)                       //增量按指数方式递减
{
	for (int i = L->length / 2; i; i = i / 2)
		ShellInsert(L, i);
}


//冒泡排序
void Exchange_SqListNode(ElemType* e1, ElemType* e2)
{
	ElemType temp;
	RecordAssign(&temp, *e1);
	RecordAssign(e1, *e2);
	RecordAssign(e2, temp);
}
void BubbleSort(SqList* L)
{
	int tag;
	for (int i = 1; i <= L->length - 1; i++)
	{
		tag = 0;
		for (int j = 1; j <= L->length - i; j++)
		{
			if (MT(L->r[j].key, L->r[j + 1].key))
			{
				Exchange_SqListNode(&L->r[j], &L->r[j + 1]);
				tag = 1;
			}
		}
		if (tag == 0)
			break;
	}
}


//快速排序
int Partition(SqList* L, int low, int high)
{
	int pivotpos = low;
	RecordAssign(&L->r[0], L->r[low]);
	while (low < high)
	{
		while (ME(L->r[high].key, L->r[0].key) && low < high)
			high--;
		pivotpos = high;
		RecordAssign(&L->r[low], L->r[high]);
		while (LE(L->r[low].key, L->r[0].key) && low < high)
			low++;
		pivotpos = low;
		RecordAssign(&L->r[high], L->r[low]);
	}
	RecordAssign(&L->r[pivotpos], L->r[0]);
	return pivotpos;
}
void QuickSort(SqList* L, int low, int high)
{
	int pivotpos;
	if (low < high)
	{
		pivotpos = Partition(L, low, high);
		QuickSort(L, low, pivotpos - 1);
		QuickSort(L, pivotpos + 1, high);
	}
}


//简单选择排序
int SelectMin(SqList* L, int i)
{
	KeyType minkey;
	KeyWordAssign(&minkey, L->r[i].key);
	int min = i;
	while (i <= L->length)
	{
		if (LT(L->r[i].key, L->r[min].key))
		{
			min = i;
			KeyWordAssign(&minkey, L->r[i].key);
		}
		i++;
	}
	return min;
}
void SelectSort(SqList* L)
{
	for (int i = 1; i <= L->length; i++)
	{
		int j = SelectMin(L, i);
		Exchange_SqListNode(&L->r[j], &L->r[i]);
	}
}


//堆排序
typedef SqList Heap;
void HeapAdjust(Heap* H, int root, int end)
{
	int left = 2 * root, right = left + 1;
	if (left <= end && LT(H->r[root].key, H->r[left].key))
	{
		Exchange_SqListNode(&H->r[root], &H->r[left]);
		HeapAdjust(H, left, end);
	}
	if (right <= end && LT(H->r[root].key, H->r[right].key))
	{
		Exchange_SqListNode(&H->r[root], &H->r[right]);
		HeapAdjust(H, right, end);
	}
}
void HeapSort(Heap* H)
{
	for (int i = H->length / 2; i; i--)
		HeapAdjust(H, i, H->length);
	for (int i = H->length; i; i--)
	{
		Exchange_SqListNode(&H->r[1], &H->r[i]);
		HeapAdjust(H, 1, i - 1);
	}
}


//归并排序
void Merge(SqList *L1, SqList* L2, int st1, int en1, int st2, int en2)
{
	int i = st1, j = st2;
	int k = st1;
	while (i <= en1 && j <= en2)
	{
		if (LE(L1->r[i].key, L1->r[j].key))
		{
			RecordAssign(&L2->r[k], L1->r[i]);
			i++; k++;
		}
		else
		{
			RecordAssign(&L2->r[k], L1->r[j]);
			j++; k++;
		}
	}
	if (i <= en1)
	{
		RecordAssign(&L2->r[k], L1->r[i]);
		i++; k++;
	}
	if (j <= en2)
	{
		RecordAssign(&L2->r[k], L1->r[j]);
		j++; k++;
	}
	for (int i = st1; i <= en2; i++)
		RecordAssign(&L1->r[i], L2->r[i]);
}
void MergeSort(SqList* L1, SqList* L2, int st, int en)
{
	if (st == en)
		RecordAssign(&L2->r[st], L1->r[st]);
	else
	{
		int m = (st + en) / 2;
		MergeSort(L1, L2, st, m);
		MergeSort(L1, L2, m + 1, en);
		Merge(L1, L2, st, m, m + 1, en);
	}
}


//基数排序
#define MAX_NUM_OF_KEY 8
#define RADIX 10
#define MAX_SPACE 10000
typedef char KeysType;
typedef struct
{
	KeysType keys[MAX_NUM_OF_KEY];
	int cur;
}SLCell;
typedef struct
{
	SLCell r[MAX_SPACE + 1];
	int keynum;
	int recnum;
}SLList;
void CreatSLList(SLList* L)
{
	printf("请依次输入静态链表的关键字数目与记录数目n");
	scanf("%d%d", &L->keynum, &L->recnum);
	getchar();
	for (int i = 1; i <= L->recnum; i++)
	{
		printf("请输入第%d个元素的关键字值n", i);
		gets(L->r[i].keys);
		L->r[i - 1].cur = i;
	}
	L->r[L->recnum].cur = 0;
}
void PrintSLList_KeyWord(SLList L)
{
	printf("链表元素值为：n");
	int i = L.r[0].cur;
	while (i)
	{
		puts(L.r[i].keys);
		i = L.r[i].cur;
	}
}
int Convert(char ch)
{
	int i = (int)ch - 48;
	return i;
}
void Distribute(SLList* L, int bitpos, int* st, int* en)
{
	int m = L->r[0].cur;
	while (m)
	{
		int digit = Convert(L->r[m].keys[bitpos]);
		if (!st[digit])
			st[digit] = m;
		else
			L->r[en[digit]].cur = m;
		en[digit] = m;
		m = L->r[m].cur;
	}
}
void Collect(SLList* L, int* st, int* en)
{
	int tail = 0, head;
	for (int i = 0; i < RADIX; i++)
	{
		if (st[i])
		{
			head = st[i];
			L->r[tail].cur = head;
			tail = en[i];
		}
	}
	L->r[tail].cur = 0;
}
void RadixSort(SLList* L)
{
	int* st, * en;
	st = (int*)malloc(sizeof(int) * (RADIX));
	if (!st) exit(OVERFLOW);
	en = (int*)malloc(sizeof(int) * (RADIX));
	if (!en) exit(OVERFLOW);
	for (int i = L->keynum - 1; i >= 0; i--)
	{
		for (int j = 0; j < RADIX; j++)
		{
			st[j] = 0;
			en[j] = 0;
		}
		Distribute(L, i, st, en);
		Collect(L, st, en);
	}
	free(st);
	free(en);
}

1.选二路归并排序为主函数进行检测：

//2-路归并排序主函数
int main()
{
	SLinkList L;
	CreatSLinkList(&L);
	InsertSort_TwoRoutes(&L);
	Arrange(&L);
	for (int i = 1; i <= L.length; i++)
		printf("%dt", L.node[i].data.key);
	return 0;
}

输入：

8
49
38
65
97
76
13
27
52

输出：

2.选基数排序为主函数进行验证：

int main()
{
	SLList L;
	CreatSLList(&L);
	PrintSLList_KeyWord(L);
	RadixSort(&L);
	PrintSLList_KeyWord(L);
}

输入：

3 10
278
109
063
930
589
184
505
269
008
083

输出：（上面为原来顺序，下面为排序后的顺序）