数据结构C++——选择排序（简单选择排序和堆排序）

文章目录

• 数据结构C++——选择排序（简单选择排序和堆排序）
• • 一、待排序记录的数据类型定义
  • 二、简单选择排序
  • 三、堆排序
  • 四、测试的完整代码
  • 五、总结

一、待排序记录的数据类型定义

待排序记录的数据类型

/*------------待排序记录的数据结构类型定义----------*/
#define MAXSIZE 1001//顺序表的最大长度
typedef int KeyType;//定义关键字类型为整型
typedef int InfoType;
typedef struct {
	KeyType key;//关键字项
	InfoType otherinfo;//其他数据项
}RedType;//记录类型
typedef struct {
	RedType r[MAXSIZE + 1];//r[0]闲置或用做哨兵单元
	int length;//顺序表长度
}SqList;//顺序表类型
           

二、简单选择排序

简单选择排序

选择排序的基本思想是：每一趟从待排序的记录中选出关键字最小的记录，按顺序放在已排序的记录序列的最后，直到全部排完为止。简单选择排序也称作直接选择排序。

简单选择排序的算法思路：
1：从一号单元值开始，依次从以后的单元值中找到最小的单元值分别和1、2、3.....号单元值交换
2：排完最后一个单元值后，排序结束
           

/*-------------简单选择排序----------------*/
void SelectSort(SqList& L) {
	//对顺序表L做简单选择排序
	for (int i = 1; i < L.length; i++) {
		//在L.r[i..L.length]中选择关键字最小的记录
		int k = i;
		for (int j = i + 1; j <= L.length; j++)
			if (L.r[j].key < L.r[k].key) k = j;
		if(k!=i)
		{//交换r[i]与r[k]
			RedType t = L.r[i];
			L.r[i] = L.r[k];
			L.r[k] = t;
		}
	}
}
           

三、堆排序

堆排序

堆排序是一种树形选择排序，在排序过程中，将待排序的记录 r[l…n]看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系，在当前无序的序列中选择关键字最大（或最小）的记录。

/*-------------筛选法调整堆-------------*/
void HeapAdjust(SqList& L, int s, int m) {
	//假设r[s+1...m]已经是堆，将r[s...m]调整为以r[s]为根的大根堆
	RedType rc = L.r[s];
	for (int j = s * 2; j <= m; j *= 2) {
		//沿key较大的孩子结点向下筛选
		if (j < m && L.r[j].key < L.r[j + 1].key) j++;//j为key较大的记录的下标
		if (rc.key >= L.r[j].key) break;//rc应插入在位置s上
		L.r[s] = L.r[j]; s = j;
	}
	L.r[s] = rc;//插入
}
/*------------建初堆--------------*/
void CreatHeap(SqList& L) {
	//把无序序列L.r[1..n]建成大根堆
	int n = L.length;
	for (int i = n / 2; i > 0; i--)//反复调用HeapAdjust
		HeapAdjust(L, i, n);
}
/*------------堆排序------------*/
void HeapSort(SqList& L) {
	//对顺序表L进行堆排序
	CreatHeap(L);//把无序序列L.r[1...L.length]建成大根堆
	for (int i = L.length; i > 1; i--) {
		RedType x = L.r[1];//将堆顶记录和当前未经排序子序列L.r[1..i]中最后一个记录互换
		L.r[1] = L.r[i];
		L.r[i] = x;
		HeapAdjust(L, 1, i - 1);//将L.r[1...i-1]重新调整为大根堆
	}
}
           

四、测试的完整代码

内联代码片

// An highlighted block
var foo = 'bar';
           

五、总结

以上为笔者对于选择排序的一些见解，希望初学者都能有所收获，有技术不到位的地方，还望各位大佬指正。

同时，笔者的个人主页还有数据结构其他部分的一些见解与分析，后续数据结构的相关知识还将陆续更新，欢迎大家访问且共同学习！