当前位置：首页 > article >正文

每日回顾：简单用C写选择排序、堆排序

article 2024/10/22 1:24:09

选择排序

直接选择排序（Selection Sort）是一种简单的排序算法。它的基本思想是每次从未排序的部分中选择最小（或最大）的元素，将其放到已排序部分的末尾。

版本一：

//直接选择排序1
void SelectSort_1(int* a, int n) {
	for (int j = n; j > 1; j--) {	//逐渐缩小未排序范围，剩一个元素时不用再进循环
		int max = 0;
		for (int i = 1; i < j; i++) {
			if (a[i] > a[max]) {
				max = i;
			}
		}
		//找到最大的元素，交换到末尾
		int tmp = a[j - 1];
		a[j - 1] = a[max];
		a[max] = tmp;
	}
}

版本二：

//直接选择排序2
void SelectSort_2(int* a, int n) {
	int left = 0;
	int right = n - 1;
	while (left < right) {
		int maxi = left;
		int mini = right;
		for (int i = left; i <= right; i++) {	//每次循环，找出一个最大一个最小值
			if (a[i] < a[mini]) {
				mini = i;
			}
			else if(a[i] > a[maxi]) {
				maxi = i;
			}
		}
		//最大最小值分别与首尾交换，左右下标指针向中间收缩
		int tmp = a[left];
		a[left] = a[mini];
		a[mini] = tmp;

		//可能会出现 mini/maxi 在 left/right 位置上
		//交换一次后，mini/maxi 的位置会改变
		//修正
		if (maxi == left) {
			maxi = mini;
		}

		tmp = a[right];
		a[right] = a[maxi];
		a[maxi] = tmp;

		left++;
		right--;
	}
}

版本区别

版本二从首尾开始，向中间收缩；消耗的时间减少一半，虽然并没什么用......

时间复杂度

两个循环嵌套，O(n^2)

空间复杂度

原地修改，O(1)

稳定性

存在元素的交换，不稳定

堆排序

堆排序（Heap Sort）是一种基于选择 or 比较的排序算法，它利用了二叉堆数据结构。堆排序分为两个主要的步骤：构建大堆（或小堆）和执行排序。

大致思想：

先建堆、如果升序，就建大堆；

接着对大堆执行排序：首尾元素交换（此时尾元素最大）、将尾元素视作堆之外的元素，将刚刚的首元素向下调整以保证大堆性质；

之后重复上一步操作，即可

//向下调整
void AdjustDown(int* a, int n, int parent) {
	int child = parent * 2 + 1;	//左孩子
	while (child < n) {
		//找出较大的孩子、和父节点对比-->是否需要交换
		if (child < n - 1 && a[child] < a[child + 1]) {
			child++;
		}

		if (a[child] > a[parent]) {	//建立大堆
			int tmp = a[child];
			a[child] = a[parent];
			a[parent] = tmp;

			parent = child;
			child = parent * 2 + 1;
		}
		else {
			break;
		}
	}
}

//堆排序
void HeapSort(int* a, int n) {
	//循环来调整每个子树、以建立大堆
	for (int i = (n - 1 - 1) / 2; i >= 0; i--) {	//(n-1-1)/2 为最后一个节点的父节点，因为 n-1 是数组最后一个下标
		AdjustDown(a, n, i);
	}
	//对大堆进行操作，以完成升序
	for (int i = n - 1; i > 0; i--) {
		//首尾交换
		int tmp = a[0];
		a[0] = a[i];
		a[i] = tmp;
		//首元素向下调整
		AdjustDown(a, i, 0);
	}
	//此时数组已为升序
}