一组关键字序列{29,18,25,47,58,12,51,10}，
算法思想：
选择排序的基本思想是依次从待排序记录序列中选择出关键字值最小（或最大）的记录、关键字值次之的记录、……，并分别将它们交换到序列的第1个位置、第2个位置、……，从而使记录成为按关键字值由小到大（或由大到小）顺序排列。
希尔排序的基本思想(1)将待排序的记录划分成若干个子序列，分别进行直接插入排序(2)再划分几个大的子序列，进行直接插入排序；反复进行几遍 (3)最后作为一个完整的序列，实施直接插入排序*

#include<stdio.h>//蓝多多算法实验八
#define MAXSIZE 20
typedef int KeyType;
typedef struct {
	KeyType key;
}RedType;
typedef struct {
	RedType r[MAXSIZE + 1];
	int length;
}SqList;
void ShellInsert(SqList& L, int dk);//希尔插入
void ShellSort(SqList& L);//希尔排序
void SelectSort(SqList& L);//直接选择排序
int main()
{
	SqList L;
	int i;
	printf_s("input 8 elements:");
	for (i = 1; i <= 8; i++)
		scanf_s("%d", &L.r[i].key);
	L.length = 8;
	ShellSort(L);
	printf_s("input the ordList(ShellSort):\n");
	for (i = 1; i <= 8; i++)
		printf_s("%5d", L.r[i].key);
	printf_s("\n");
	SelectSort(L);
	printf_s("input the ordList(SelectSort):\n");
	for (i = 1; i <= 8; i++)
		printf_s("%5d", L.r[i].key);
	return 0;
}
void ShellInsert(SqList& L, int dk)//希尔插入
{
	int i, j;
	for (i = dk + 1; i <= L.length; ++i)
		if (L.r[i].key < L.r[i - dk].key) {
			L.r[0] = L.r[i];
			for (j = i - dk; j > 0 && (L.r[0].key < L.r[j].key); j -= dk)
				L.r[j + dk] = L.r[j];
			L.r[j + dk] = L.r[0];
		}
}
void ShellSort(SqList& L)//希尔排序
{
	int k;
	int dlta[4] = { 4,3,2,1 };
	for (k = 0; k < 4; ++k)
		ShellInsert(L, dlta[k]);
}
void SelectSort(SqList& L)//直接选择排序
{
	int i, j, t;
	for (i = 1; i < L.length; ++i) {
		for (j = i + 1; j < L.length + 1; ++j)
			if (L.r[i].key > L.r[j].key) {
				t = L.r[i].key;
				L.r[i].key = L.r[j].key;
				L.r[j].key = t;
			}
	}
}

运行结果：略 （VS2019 自己去运行吧）

ITPub博客

一组关键字序列，分别给出用希尔排序、直接选择排序算法从小到大排序结果

最新文章