您的位置: 首页  >  文章  >  实验九 排序算法的实现

实验九 排序算法的实现

分类: 文章 • 2025-02-24 14:48:59

 

1.实验目的

熟悉排序的方法、过程及原则。掌握插入排序、快速排序、选择排序、归并排序的算法思想及实现方法，掌握其时间复杂度的分析方法。

2.实验内容

定义待排序序列的存储结构。验证插入排序、希尔排序、冒泡排序、快速排序、简单选择排序、堆排序、归并排序中各排序方法中的一、二个排序算法。

  1. 插入类排序：直接插入排序、希尔排序
  2. 交换类排序：冒泡排序、快速排序
  3. 选择类排序：简单选择排序、堆排序
  4. 归并类排序：递归和非递归形式的归并排序
#include<stdio.h>
#define MAXSIZE 20

typedef int KeyType;//定义关键字类型为整数类型
typedef int InfoType;

typedef struct {
	KeyType key;//关键字项 
	InfoType otherinfo;//其他数据项 
}RedType;//记录类型 
typedef struct {
	RedType  r[MAXSIZE + 1];//用r[0] 做闲置或者做哨兵单元
	int length;//顺序表长度 
}SqList;//顺序表类型


void InsertSort(SqList *L)
{//对顺序表L做直接插入排序 
	int i, j;
	for (i = 2; i <= L->length; i++)
		if (L->r[i].key < L->r[i - 1].key)
		{
			L->r[0] = L->r[i];//复制为哨兵
			L->r[i] = L->r[i - 1];
			for (j = i - 2; L->r[0].key < L->r[j].key; --j)
				L->r[j + 1] = L->r[j];//记录后移 
			L->r[j + 1] = L->r[0]; //插入到正确的位置上 		
		}
}

void Show(SqList L)
{
	int i;
	for (i = 1; i <= L.length; i++)
		printf("%4d", L.r[i].key);
	printf("\n");
}

int main()
{
	SqList L;
	int i;
	printf("输入线性表的长度：");
	scanf_s("%d", &L.length);
	printf("输入线性表中的元素：");
	for (i = 1; i <= L.length; i++)
		scanf_s("%d", &L.r[i].key);
	InsertSort(&L);
	printf("直接插入的排序结果是;");
	Show(L);
	system("pause");
	return 0;
}

 

实验九 排序算法的实现

 

#include<stdio.h>

#define MAXSIZE 10
typedef int KeyType;
typedef int InfoType;
typedef struct {
	KeyType key;		//关键字项
	InfoType otherinfo;	// 其他数据项
} RedType;

typedef struct {
	RedType r[MAXSIZE + 1];//r[0]做闲置或者哨兵单元
	int length;			//顺序表长度
} SqList;				//顺序表类型

void ShellInsert(SqList *L, int dk) {
	//对顺序表L做一趟希尔插入排序，本算法
	//1.前后记录 位置的增量是dk,不是1
	//2.r[0]只是暂存单元，不是哨兵，当j<=0时 ，插入位置已经找到
	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 = j - dk)
				L->r[j + dk] = L->r[j];//记录后移，查找插入位置
			L->r[j + dk] = L->r[0];//插入
		}
}

void SellSort(SqList *L, int dlta[], int t) {
	//按增量序列dlka[0..t-1]对顺序表L做希尔排序
	int k;
	for (k = 0; k < t; k++)
		ShellInsert(L, dlta[k]);//一趟增量为dlta[k] 的插入排序
}


void Show(SqList L) {
	int i;
	for (i = 1; i <= L.length; i++)
		printf("%4d", L.r[i].key);
	printf("\n");
}



int main() {

	SqList L;
	int i;
	int dlta[3] = { 5,3,1 };
	printf("输入线性表的长度：");
	scanf_s("%d", &L.length);
	printf("输入线性表中的元素：");
	for (i = 1; i <= L.length; i++)
		scanf_s("%d", &L.r[i].key);
	SellSort(&L, dlta, 3);
	printf("希尔排序结果是;");
	Show(L);
	system("pause");
	return 0;
}

 

实验九 排序算法的实现

 

#include<stdio.h>

#define MAXSIZE 10
typedef int KeyType;
typedef int InfoType;
typedef struct {
	KeyType key;		//关键字项
	InfoType otherinfo;	// 其他数据项 
}RedType;

typedef struct {
	RedType r[MAXSIZE + 1];//r[0]做闲置或者哨兵单元
	int length;			//顺序表长度 
}SqList;				//顺序表类型

int Partition(SqList *L, int low, int high)
{//交换顺序表L中子表r[low..high]的记录，枢轴记录到位，并返回所在位置
  //此时在他之前的（后）的记录均不大（小）于他 
	int pivokey;
	L->r[0] = L->r[low];//用子表的第一个记录做枢轴记录
	pivokey = L->r[low].key; //枢轴记录关键字
	while (low < high)
	{//从表的两端交替的向中间扫描 

		while (low < high&&L->r[high].key >= pivokey)
		{
			--high;//high指针指向的元素比枢轴大，high指针就向前移动 
		}
		L->r[low] = L->r[high];//将比枢轴记录小的记录移动到底端 

		while (low < high&&L->r[low].key <= pivokey)
		{
			++low;//low指针指向的元素比枢轴小，low指针就向后移动
		}
		L->r[high] = L->r[low];//将比枢轴大的记录移动到后端 	   

	}
	L->r[low] = L->r[0];//枢轴记录到位 
	return low;
}

void QSort(SqList *L, int low, int high)
{//对顺序表L中的子序列 L.r[low..high]做快速排序 
	int pivotloc;
	if (low < high)
	{
		pivotloc = Partition(L, low, high);//将L一分为二 
		QSort(L, low, pivotloc - 1);//对低子表递归排序，pivotloc是枢轴位置
		QSort(L, pivotloc + 1, high);//对高子表递归排序 		
	}
}

void QuickSort(SqList *L)
{//对顺序表L进行快速排序 
	QSort(L, 1, L->length);
}

void Show(SqList L)
{
	int i;
	for (i = 1; i <= L.length; i++)
		printf("%4d", L.r[i].key);
	printf("\n");
}

int main()
{
	SqList L;
	int i;
	printf("输入线性表的长度：");
	scanf_s("%d", &L.length);
	printf("输入线性表中的元素：");
	for (i = 1; i <= L.length; i++)
		scanf_s("%d", &L.r[i].key);
	QuickSort(&L);
	printf("快速排序结果是;");
	Show(L);
	system("pause");
	return 0;
}

 

实验九 排序算法的实现

 

#include<stdio.h>
#define MAX 10000
#define MAXSIZE 10
typedef int KeyType;
typedef int InfoType;
typedef struct {
	KeyType key;		//关键字项
	InfoType otherinfo;	// 其他数据项
} RedType;

typedef struct {
	RedType r[MAXSIZE + 1];//r[0]做闲置或者哨兵单元
	int length;			//顺序表长度
} SqList;				//顺序表类型


int SelectMiniKey(SqList L, int i) {
	int minik;
	int mini = MAX;
	for (i; i <= L.length; i++) {
		if (L.r[i].key < mini) {
			mini = L.r[i].key;
			minik = i;
		}
	}
	return minik;
}
void SelectSort(SqList *L) {
	//对顺序表进行简单选择排序

	int i, j, temp;
	for (i = 1; i <= L->length; i++) { //选择第i小记录，并交换到位
		j = SelectMiniKey(*L, i);//在L.r[i..L.length]中选择Key最小的记录
		if (i != j) {
			temp = L->r[i].key;
			L->r[i].key = L->r[j].key;
			L->r[j].key = temp;
		}
	}
}

void Show(SqList L) {
	int i;
	for (i = 1; i <= L.length; i++)
		printf("%4d", L.r[i].key);
	printf("\n");
}


int main() {

	SqList L;
	int i;
	printf("输入线性表的长度：");
	scanf_s("%d", &L.length);
	printf("输入线性表中的元素：");
	for (i = 1; i <= L.length; i++)
		scanf_s("%d", &L.r[i].key);
	SelectSort(&L);
	printf("简单选择排序结果是;");
	Show(L);
	system("pause");
	return 0;
}

 

实验九 排序算法的实现

 

#include<stdio.h>
#define MAX 10000
#define MAXSIZE 10
typedef int KeyType;
typedef int InfoType;

typedef struct {
	KeyType key;		//关键字项
	InfoType otherinfo;	// 其他数据项
} RedType;

typedef struct {
	RedType r[MAXSIZE + 1];//r[0]做闲置或者哨兵单元
	int length;			//顺序表长度
} SqList;				//顺序表类型
typedef SqList HeapType;//堆排序用顺序表存储表示 
void HeapAdjust(HeapType *H, int s, int m)
{
	//已知H.r[s..m]中记录的关键字除H.r[s].key之外均满足堆的定义，
	//本函数调整H.r[s] 的关键字，使H.r[s..m]成为一个大顶堆（对其中记录的关键字而言）
	RedType rc;
	int j;
	rc = H->r[s];
	for (j = 2 * s; j <= m; j = j * 2)
	{//沿着key较大的孩子结点向下筛选
		if (j < m && (H->r[j].key < H->r[j + 1].key))
			j++;//j为key较大的记录的下标
		if (!(rc.key < H->r[j].key))
			break;
		H->r[s] = H->r[j];
		s = j;
	}
	H->r[s] = rc;//插入 
}

void HeapSort(HeapType *H)
{//对顺序表H进行堆排序 
	RedType temp;
	int i;
	for (i = H->length / 2; i > 0; --i)//把H.r[1..H.length] 建成大顶堆
		HeapAdjust(H, i, H->length);
	for (i = H->length; i > 1; --i)
	{
		temp = H->r[1];
		H->r[1] = H->r[i];
		H->r[i] = temp;//将堆顶记录和当前未经排序的子序列H.r[1..i]中最后一个记录相互交换
		HeapAdjust(H, 1, i - 1);//将H.r[1..i-1]重新调整为大顶堆 
	}
}

void Show(SqList L)
{
	int i;
	for (i = 1; i <= L.length; i++)
		printf("%4d", L.r[i].key);
	printf("\n");
}

int main()
{
	HeapType H;
	int i;
	printf("输入线性表的长度：");
	scanf_s("%d", &H.length);
	printf("输入线性表中的元素：");
	for (i = 1; i <= H.length; i++)
		scanf_s("%d", &H.r[i].key);

	HeapSort(&H);
	printf("堆排序结果是;");
	Show(H);
	system("pause");
	return 0;
}

实验九 排序算法的实现 

 

相关推荐