【数据结构】常见排序算法——常见排序介绍、选择排序（直接选择排序、堆排序）交换排序（冒泡排序）-Toy模板网

这篇具有很好参考价值的文章主要介绍了【数据结构】常见排序算法——常见排序介绍、选择排序（直接选择排序、堆排序）交换排序（冒泡排序）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

1.常见排序

直接选择排序,数据结构,排序算法,数据结构

2.选择排序

选择排序是一种简单但不高效的排序算法，其基本思想是从待排序的数据中选择最小（或最大）的元素放到已排序的数据末尾。具体操作步骤如下：

（1）找到数据中最小的元素，并把它交换到第一个位置；

（2）在剩下未排序的元素中找到最小的元素，并把它交换到已排序数据的末尾；

（3）重复第2步，直到所有元素都排好序。

在选择排序的实现中，需要使用两个指针：一个指向当前扫描的区域的起始位置，另一个指向未排序区域的起始位置。通过交换找到每次扫描区域内的最小元素，能够确保每次扫描后已排序区域变大、未排序区域变小。

选择排序算法的时间复杂度为O(n^2)，不适合处理大量数据。

选择排序的基本思想：

总结：是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。

2.1直接选择排序

直接选择排序的实现思想:

（1）在元素集合array[i]–array[n-1]中选择关键码最大(小)的数据元素；

（2）若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后一个（第一个）元素交换；

（3）在剩余的array[i]–array[n-2]（array[i+1]–array[n-1]）集合中，重复上述步骤，直到集合剩余1个元素。

直接选择排序,数据结构,排序算法,数据结构

直接选择排序的实现：

算法中使用了两个指针left和right，它们分别指向当前待排序区间的左右端点。

在循环处理待排序区间的时候，算法首先在当前区间中查找最小和最大的元素，使用mini和maxi分别记录这两个位置。

然后通过交换操作，把最小元素交换到当前待排序区间的最左边，把最大元素交换到最右边。

最后通过更新left和right的位置来缩小待排序区间的范围，直到排序完成。

其中Swap函数是一个交换两个整数变量值的函数，实现了传入两个指针并利用中间变量进行交换的操作。

void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

void SelectSort(int* a, int n)
{
	int left = 0, right = n - 1;
	while (left < right)
	{
		int mini = left, maxi = left;
		for (int i = left + 1; i <= right; i++)
		{
			if (a[i] < a[mini])
			{
				mini = i;
			}

			if (a[i] > a[maxi])
			{
				maxi = i;
			}
		}

		Swap(&a[left], &a[mini]);
		if (left == maxi)
		{
			maxi = mini;
		}

		Swap(&a[right], &a[maxi]);

		left++;
		right--;
	}
}

直接选择排序的特性总结：

（1）直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用

（2）时间复杂度：O(N^2)

（3）空间复杂度：O(1)

（4）稳定性：不稳定

2.2堆排序

堆排序（Heap Sort）是一种基于堆数据结构的排序算法，它是选择排序的一种优化。堆是一种完全二叉树，分为大根堆和小根堆两种。

大根堆的定义是，每个结点的值都不大于其父节点的值，根结点是最大值。

小根堆的定义是，每个结点的值都不小于其父节点的值，根结点是最小值。

堆排序的流程如下：

（1）构建大根堆/小根堆；

（2）将堆顶元素输出，然后将堆重新调整为大根堆/小根堆；

（3）重复步骤2，直到堆中所有元素都已排序。

具体实现时，可以使用数组来表示堆，对于一个下标为i的结点，其左子节点为2i+1，右子节点为2i+2，其父节点为(i-1)/2。

堆排序的时间复杂度为O(nlogn)，其中n为待排序数组的长度。堆排序是一种原地排序算法，不需要额外的辅助空间，而且由于堆是一种数据结构，可以方便地支持动态的插入和删除操作，因此应用范围比较广泛。

堆排序的实现思想：

堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。

直接选择排序,数据结构,排序算法,数据结构

堆排序的实现：

算法中首先需要建立以数组中的元素为节点的大根堆，建堆操作的时间复杂度为O(n)。

然后，将大根堆中最后一个节点与堆顶元素交换，再重新对交换后的堆进行调整，以使其满足大根堆的性质，并将已排好序的元素一直输出至堆顶，直到所有元素都已排好序。

具体实现中，利用函数AdjustDown来对堆进行向下调整，以使得当前节点满足大根堆/小根堆的性质。此函数接受三个参数：待调整的堆，堆的长度以及需要调整的节点。在函数中，使用child标记当前节点的左孩子节点，若右孩子节点的值更大，则令child等于右孩子节点的下标；接着判断child和parent的值，若符合堆的性质，则结束调整，否则交换两个节点的值，并向下继续调整。

在堆排序算法中，最需要注意的是对于任意一个元素，它的左右子树都必须满足大根堆/小根堆的性质。

// 左右子树都是大堆/小堆
void AdjustDown(int* a, int n, int parent)
{
	int child = parent * 2 + 1;
	while (child < n)
	{
		// 选出左右孩子中大的那一个
		if (child + 1 < n && a[child + 1] > a[child])
		{
			++child;
		}

		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

void HeapSort(int* a, int n)
{
	// 建堆 -- 向下调整建堆 
	for (int i = (n - 1 - 1) / 2; i >= 0; --i)
	{
		AdjustDown(a, n, i);
	}

	int end = n - 1;
	while (end > 0)
	{
		Swap(&a[end], &a[0]);
		AdjustDown(a, end, 0);

		--end;
	}
}

堆排序的特性总结：

（1）堆排序使用堆来选数，效率就高了很多

（2）时间复杂度：O(N*logN)

（3）空间复杂度：O(1)

（4）稳定性：不稳定

3.交换排序

基本思想：所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。

3.1冒泡排序

冒泡排序（Bubble Sort）是一种简单的排序算法。

其基本思路是从待排序的第一个元素开始依次比较相邻的两个元素的大小。若前面的元素大于后面的元素，则交换两个元素的位置，这样较大的元素就会像气泡一样不断向上“浮动”，至多经过n-1次排序后就可以将最大的元素放置在最后一个位置上，从而完成第一轮冒泡排序。

然后，在进行第二轮排序时，对除了最后一个已排好序的元素之外的子序列依次进行冒泡排序，这样第二轮的冒泡排序可以把次大的元素交换到倒数第二个位置。

以此类推，直到所有元素均已排序完毕。

冒泡排序算法的平均时间复杂度为 O(n^2)，其空间复杂度为O(1)，由于其实现简单，代码易懂，因此常用于排序元素较少的列表，对于大规模的数据集，冒泡排序一般不是最优选择。

直接选择排序,数据结构,排序算法,数据结构

冒泡排序的实现：

算法中使用两重循环，外层循环j控制排序次数，内层循环i控制每一次排序中需要比较的相邻元素位置。

具体实现中，使用if语句判断相邻元素的大小顺序，并交换这两个元素的位置。

在排序过程中，待排序的序列不断地缩小，即外层循环的次数逐渐减小，因为每一轮的比较都会让本轮的待比较元素中最大的元素到达本轮的最后位置。因此，当经过n-1轮排序后，整个序列已经有序。

void BubbleSort(int* a, int n)
{
	for (int j = 0; j < n; j++)
	{
		for (int i = 1; i < n - j; i++)
		{
			if (a[i - 1] > a[i])
			{
				Swap(&a[i - 1], &a[i]);
			}
		}
	}
}