选择排序(简单选择排序，堆排序)

学习时间2022.12.17

选择排序

基本概念

简单选择排序

• 第1次，遍历整个数组，找到最小的数字，将其与第一位进行调换；第2次，遍历除以排序好的第1个数，遍历后面所有数字，找到最小的，与第2位进行调换...以此类推

堆排序

• 要理解堆排序，可以看看这个代码菜鸟教程堆排序和这个动画演示David Galles Computer Science University of San Francisco-Data Structure Visualizations-Heap Sort
• 以下来自wikipedia-heapsort
• 堆排序（英语：Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆的性质：即子节点的键值或索引总是小于（或者大于）它的父节点。
• 若以升序排序说明，把数组转换成最大堆（Max-Heap Heap），这是一种满足最大堆性质（Max-Heap Property）的二叉树：对于除了根之外的每个节点i, A[parent(i)] ≥ A[i]。
• 重复从最大堆取出数值最大的结点（把根结点和最后一个结点交换，把交换后的最后一个结点移出堆），并让残余的堆维持最大堆性质。

代码实现

基本数据结构

typedef int ElemType;

typedef struct {
	ElemType* elem;//整型指针
	int TableLen;//动态数组元素个数
}SSTable;

基本函数实现

void ST_init(SSTable& ST, int len) {
	ST.TableLen = len;
	//ST.elem = (ElemType*)malloc(sizeof(ElemType) * ST.TableLen);
	ST.elem = (ElemType*)calloc(ST.TableLen, sizeof(ElemType));
	//初始化随机数发生器
	srand(time(NULL));
	//输出0-100的ST.TableLen个随机数
	for (int i = 0; i < ST.TableLen; i++)
	{
		ST.elem[i] = rand() % 100;
	}
}

void swap(ElemType& a, ElemType& b) {
	int temp;
	temp = a;
	a = b;
	b = temp;
}

void ST_print(SSTable ST) {
	for (int i = 0; i < ST.TableLen; i++) {
		printf("%3d", ST.elem[i]);
	}
	printf("\n");
}

简单选择排序和对应main函数

//简单选择排序
void SelectSort(ElemType A[], int n) {
	int i, j, min;
	for (i = 0; i < n - 1; i++)
	{
		min = i;
		for (j = i + 1; j < n; j++)
		{
			if (A[min] > A[j])
			{
				min = j;
			}
		}
		swap(A[i], A[min]);
	}
}

int main() {
	SSTable ST;
	ST_init(ST, 10);
	ElemType A[] = { 32,45,11,324,32,59,90,85,1,49 };
	//memcpy(ST.elem, A, sizeof(A));
	ST_print(ST);
	SelectSort(ST.elem, 10);
	ST_print(ST);
}

堆排序和对应main函数

//最大堆积
void MaxHeapify(ElemType A[], int begin, int end) {
	int parent, child;
	parent = begin;
	child = parent * 2 + 1;
	while (child <= end)
	{
		if (child + 1 <= end && A[child] < A[child + 1])
		{
			child += 1;
		}
		if (A[child] > A[parent])
		{
			swap(A[child], A[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			return;
		}
	}
}

//堆排序
void HeapSort(ElemType A[], int n) {
	for (int i = n / 2 - 1; i >= 0; i--)
	{
		MaxHeapify(A, i, n - 1);
	}
	for (int j = n - 1; j > 0; j--)
	{
		swap(A[0], A[j]);
		MaxHeapify(A, 0, j - 1);
	}
}

int main() {
	SSTable ST;
	ST_init(ST, 10);
	ElemType A[] = { 32,45,11,324,32,59,90,85,1,49 };
	//memcpy(ST.elem, A, sizeof(A));
	ST_print(ST);
	HeapSort(ST.elem, 10);
	ST_print(ST);
}