[数据结构与算法]简单选择排序、树形选择排序

1.简单选择排序

简单选择排序算法思想：

• （1）在第i趟排序过程中，通过n-i次关键字之间的比较，从剩余的n-i+1个记录中选出最小的记录，并和第i个记录交换。
• （2）对于i=1,…,n-1，执行上述过程，直至整个序列有序。

简单选择排序算法：

//5.简单选择排序
void SelectSort(SqList& L) {
	KeyType temp;
	int k;
	for (int i = 1; i < L.length; i++) {
		k = i;
		for (int j = i + 1; j <= L.length; j++) {
			if (L.r[j] < L.r[k])
				k = j;
		}
		temp = L.r[i];
		L.r[i] = L.r[k];
		L.r[k] = temp;
	}
}

2.树形选择排序

在体育比赛中的锦标赛便是一种树形选择排序。

示例：以关键字序列{49,35,66,91,74,18,22,48}为例，这个过程可以用一颗有n个叶子结点的完全二叉树表示，在8个叶子结点中依次存放排序之前的8个关键字，每个非终端结点中的关键字均等于左右孩子结点中较小的关键字，则根结点中的关键字为所有关键字中最小的。在输出最小关键字之后，若欲选出次小关键字，则需将叶子节点中最小关键字18改为比所有结点都大的值，然后从该叶子结点开始，和其左右兄弟进行比较，修改从叶子结点到根结点路径上的各结点关键字，则根结点为次小关键字。同理，可选出从小到大的所有关键字。