选择排序：直接选择排序、堆排序

目录

直接选择排序

1.选择排序的基本思想

2.直接选择排序的基本思想

3.直接插入排序的代码思路步骤

4.直接选择排序代码

5.直接选择排序的特性总结

堆排序

一、排升序，建大堆

1.利用向上调整函数建大堆

1.1.建立大堆的思路

1.2.以下是具体步骤：

1.3.代码

2.利用向下调整函数建大堆

2.1.建立大堆的思路

2.2.代码思路步骤

2.3.利用向下调函数建大堆的案例 

2.4.代码 

3.建大堆排升序的思路

2.利用向上调整函数或者向下调整函数建大堆排升序

二、排降序，建小堆

​1.利用向上调整函数建小堆

1.1.建立小堆的思路

1.2.以下是具体步骤：

1.3.代码

2.利用向下调整函数建小堆

2.1.建立大堆的思路

2.2.代码思路步骤

2.3.利用向下调函数建小堆的案例 

​编辑

2.4.代码 

3.建大堆排升序的思路

​2.利用向上调整函数或者向下调整函数建小堆排升序

三、堆排序的时间复杂度

1.利用向上调整函数建堆的时间复杂度

(1)对利用向上调整函数建大堆的时间复杂度是O(N*logN)进行解析

(2)分析向上调整函数AdjustUp建堆的时间复杂度是O(N*logN )的原因

2.利用向下调整函数建堆的时间复杂度

(1)对利用方式二的向下调整函数建堆的时间复杂度是O(N)进行分析

(2)分析利用向下调整函数AdjustDown建堆的时间复杂度是O(N)的原因

3.堆排序的时间复杂度和空间复杂度

3.1.时间复杂度：O(N*logN)

(1)建立大堆过程的时间复杂度计算

(2)排序过程的时间复杂度计算

(3)对堆排序算法的时间复杂度是O(N*logN)的总结

3.2.空间复杂度：O(1)

3.3.稳定性：不稳定

直接选择排序

注意：下面都是以排升序为例进行说明的。

1.选择排序的基本思想

每一次从待排序的数据元素中选出最小的一个元素存放在序列的起始位置后待排序的数据就减少1个，然后重复上面步骤直到全部待排序的数据元素排完 。

图形解析：

2.直接选择排序的基本思想

注意：直接选择排序是对选择排序的优化。

每一次从待排序的数据元素中选出最小和最大的元素后，把最小元素存放在序列的起始位置而把最大元素存放到序列的末尾位置后待排序的数据就减少2个，重复上面步骤直到全部待排序的数据元素排完 。

3.直接插入排序的代码思路步骤

(1) 初始化两个指针，begin 指向待排序序列的起始位置，end 指向待排序序列的末尾位置。

(2) 在当前未排序的元素集合 a[begin] 到 a[end] 中，确定最小元素的索引 mini 和最大元素的索引 maxi。

(3) 将找到的最小元素 a[mini] 与 a[begin] 位置的元素进行交换。

(4) 在执行了步骤(3)的交换操作后，需要检查最大元素的索引 maxi 是否受到了影响：

  • 如果最大元素的原始位置是 begin，而在步骤(3)的交换后，最大元素被移动到了 mini 位置，则需要将 maxi 更新为 mini。然后，将位于 maxi（现在等于 mini）的最大元素与 a[end] 位置的元素进行交换。
  • 如果最大元素原本就不在 begin 位置，那么直接将 a[maxi] 与 a[end] 位置的元素进行交换。

(5) 将 begin 指针向后移动一位（begin++），将 end 指针向前移动一位（end–），以此来缩小待排序数据元素集合的范围，并排除已经排序的元素。

(6) 重复步骤(2)至(5)，直到 begin 大于或等于 end，此时表明所有元素都已按顺序排列。

注意：步骤(4)中的检查是必要的，因为在将最小元素与 a[begin] 位置的元素交换后，如果最大元素原本在 begin 位置，它会被交换到 mini 位置。因此，在交换最大元素之前，必须确保 maxi 指向正确的元素。

这个排序算法是一种双向选择排序的变种，它在每次迭代中同时找到最小和最大的元素，并将它们放置在正确的位置，然后缩小排序范围。

4.直接选择排序代码

//交换函数
void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}


void SelectSort(int* a, int n)
{
	//1.初始化区间[begin，end]的范围
	int begin = 0, end = n - 1;

	//2.这个while (begin < end)循环的作用是：不断重复缩小区间[begin,end]的范围后再去找区间[begin,end]的最小值放到区间的最左边begin位置和找区间[begin,end]的最大值放到区间的最右边end位置这个操作，直到区间[begin,end]中的begin = end为止。
	while (begin < end)//注意：当begin = 
	{
		//3.一开始假设区间下标begin位置的元素即使最大值也是最小值，并用mini和maxi记录区间下标begin位置
		int mini = begin, maxi = begin;

		//4.在区间[begin,end]中从头到尾找出区间中的最大值和最小值，并用maxi和mini分别记录最大值和最小值的下标
		for (int i = begin + 1; i <= end; ++i)
		{
			//4.1.在区间[begin，end]中找出最小值
			if (a[i] < a[mini])
			{
				mini = i;
			}

			//4.2.在区间[begin,end]中找出最大值
			if (a[i] > a[maxi])
			{
				maxi = i;
			}
		}

		//写法1：
		//5.把区间[begin，end]中的最小值放到区间的最左边begin位置，而把区间中的最大值放到区间最右边end位置。
		//5.1.把区间[begin，end]最小值放到区间最左边begin位置
		Swap(&a[begin], &a[mini]);

		//注意：这个if (maxi == begin)语句的目的是为了防止区间最左边begin位置的元素是区间中的最大值，但是在通过Swap(&a[begin], &a[mini])函数把区间最小值元素放到区间最左边后进而使得此时
		//下标mini位置的元素才是区间中的最大值，所以此时必须更新maxi的值使得maxi可以指向此时位于mini位置的区间的最大值。
		if (maxi == begin)
			maxi = mini;

		//5.2.把区间[begin，end]最大值放大区间最右边end位置
		Swap(&a[end], &a[maxi]);


		//写法2：
		/*Swap(&a[end], &a[maxi]);

		//这个if(mini == end)语句的作用是为了防止区间最右边end位置是区间最小值，而Swap(&a[end], &a[maxi]函数把区间最大值元素放到区间最右边后进而使得此时
		//下标maxi位置的元素才是区间中的最小值，所以此时必须更新mini的值使得mini可以指向此时位于maxi位置的区间的最小值
		if (mini == end)
			mini = maxi;

		Swap(&a[begin], &a[mini]);*/


		//6.更新区间[beign,end]的范围即缩小区间[beign,end]的范围。
		++begin;
		--end;
	}
}

注意事项：

如果在代码中使用局部变量 max 和 min 来存放待排序序列中的最大元素和最小元素的值，而不是使用 maxi 和 mini 来存放它们的下标，将会导致以下问题：

  1. 无法正确交换元素：在找到最小和最大元素后，代码需要将它们放置到正确的位置。如果只有元素的值而没有它们在数组中的位置，就无法进行交换操作。因为交换需要知道元素在数组中的具体位置。

  2. 无法处理最大值或最小值重复的情况：如果最大值或最小值在数组中出现多次，仅记录值无法确定应该与哪个位置的元素进行交换。

  3. 代码逻辑不完整：原代码依赖于 maxi 和 mini 来更新元素的位置，如果只记录值，那么在交换最小值后，原本最大值的位置可能发生变化（如果最小值原本在最大值的位置），这种情况下需要更新最大值的下标。如果没有下标，就无法进行这种更新。

5.直接选择排序的特性总结

(1) 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
(2) 时间复杂度：O(N^2)
(3)空间复杂度：O(1)
(4)稳定性：不稳定

(5)直接选择排序是所有排序算法中最差劲的算法。虽然直接选择排序算法和直接插入排序算法的时间复杂度一样，但是与直接选择排序算法相比反而是直接插入排序更好。直接插入排序算法的时间复杂度的多少和整个序列中数据的分布即是由局部有序或者近似有序有关。

分析：

①直接插入排序的适应性很强。若同时用直接插入排序算法和直接选择排序算法对局部有序或者近似有序的序列分别进行排序时，直接插入排序算法的效率更高且此时直接插入排序算法的时间复杂度一定小于O(N^2)。

②在任何情况下(即哪怕是对有序序列进行排序时)，直接选择排序的时间复杂度都是O(N^2)。

堆排序

一、排升序，建大堆

1.利用向上调整函数建大堆

1.1.建立大堆的思路

步骤1：初始化堆

  • 将给定的数据序列（例如：数组）看作是一个完全二叉树，但该数据序列暂时不满足堆的性质。

步骤2：向上调整函数

  • 从完全二叉树根结点的第一个孩子结点开始按照从左至右且从上往下的顺序对完全二叉树每个结点执行向上调整操作直到完全二叉树最后一个结点完成向上调整操作为止，最终使其整个数据序列满足大堆的性质。
1.2.以下是具体步骤：

步骤1：找到根结点的第一个孩子结点

  • 在一个完全二叉树中，根结点的第一个孩子结点的位置是 child = 1，其中 n 是结点的总数。

步骤2：执行向上调整

  • 从完全二叉树根结点的第一个孩子结点开始，依次向后遍历完全二叉树的每个结点。
  • 对于每个结点，执行以下操作：
    • 比较当前结点(即孩子结点)与其双亲结点的值。
    • 如果当前结点(即孩子结点)的值大于其双亲结点的值，则交换当前结点(即孩子结点)与其双亲结点的值，然后对交换后位于双亲结点位置的孩子结点继续执行向上调整操作。

步骤3：重复步骤2直到完全二叉树最后一个结点完成向上调整操作

  • 继续向后遍历完全二叉树并对每个结点执行向上调整，直到最后一个结点完成向上调整操作为止。
1.3.代码
//(利用向上调整函数建大堆。
int child = 0;
for (child = 1; child < n; child++)
	AdjustUp1(a, child);

2.利用向下调整函数建大堆

2.1.建立大堆的思路

(1)初始化堆：将给定的数据序列(例如：数组)看作是一个完全二叉树，但该数据序列暂时不满足堆的性质。

(1)向下调整函数：从最后一个孩子结点的双亲结点开始按照从右往左且从下往上的顺序对完全二叉树的每个结点执行向下调整操作直到完全二叉树的根结点完成向下调整操作为止，最终使其整个数据序列满足大堆的性质。

2.2.代码思路步骤

步骤1：找到最后一个孩子结点的双亲结点的位置

  • 在一个完全二叉树中，最后一个孩子结点的双亲结点的位置是parent = (n-1-1)/2，其中 n 是结点的总数。

步骤2：执行向下调整

  • 从最后一个孩子结点的双亲结点开始，依次向前遍历完全二叉树的每个结点。
  • 对于每个结点，执行向下调整操作：
    • 比较当前双亲与其左右子孩子结点中最大孩子的值。
    • 如果当前双亲结点的值小于最大孩子结点的值，则交换当前双亲结点与最大孩子结点的值，然后对交换后的位于最大孩子结点位置的双亲结点的值继续执行向下调整操作。

步骤3：重复步骤2直到完全二叉树的根结点完成向下调整操作。

  • 继续向前遍历完全二叉树并对每个结点执行向下调整，直到完全二叉树的根结点完成向下调整操作为止。
2.3.利用向下调函数建大堆的案例 

例1：在数组a没有变成大堆之前，一开始数组的元素是a[ ] = {1,3,8,5,4,6,9,2,7,10}。

图形解析：把数组a[ ] = {1,3,8,5,4,6,9,2,7,10}先想象成以下图形的完全二叉树，然后从完全二叉树最后一个孩子结点10的双亲结点4开始按照从右往左再从下往上的顺序对完全二叉树的每个结点进行向下调整操作直到完全二叉树根结点1完成向下调整操作为止才结束。最终数组a变成a[ ] = {10,7,9,5,4,6,8,2,1}而且这个数组a写成一个完全二叉树后可以看出这个完全二叉树是个大堆。

注意：以下是整个完全二叉树的所有左右子树变成大堆的执行顺序① —>② —> ③—> ④—>⑤。

例2：在数组a没有变成大堆之前，一开始动态数组的元素是

a[ ] = {18,49,15,27,37,18,28,15,16,20,21,20,21,30,31}。

图形解析：把数组a[ ] = {18,49,15,27,37,18,28,15,16,20,21,20,21,30,31}先想象成以下图形的完全二叉树，然后从完全二叉树最后一个孩子结点31的双亲结点28开始按照从右往左再从下往上的顺序把完全二叉树的每个结点进行向下调整操作直到完全二叉树根结点18完成向下调整操作为止才结束。最终数组a变成a[ ] = {49,37,31,27,21,21,30,15,16,20,18,20,18,15,28}而且这个数组a写成一个完全二叉树后可以看出这个完全二叉树是个大堆。

注意：以下是整个完全二叉树的左右子树变成堆的执行顺序① —>② —> ③—> ④—>⑤。

2.4.代码 
//利用向下调整函数建大堆
int parent = 0;
for (parent = (n - 1 - 1) / 2; parent >= 0; parent--)
	AdjustDown1(a, n, parent);

3.建大堆排升序的思路

① 构建大堆：首先，通过向下调整函数（而非向上调整，因为向下调整更高效）将原数组转换成一个大堆。这样，堆的根结点（即数组的第一个元素）将是数组中的最大值。

② 交换堆顶与堆尾元素：一旦大堆构建完成，将堆顶元素（数组的第一个元素）与堆的最后一个元素进行交换。这样，数组中的最大值就被放置到了数组的末尾。

③ 减少堆的大小：交换操作完成后，认为堆的最后一个元素已经排定，因此不再将其视为堆的一部分，从而将堆的大小减少1。

④ 维护大堆的性质：由于交换操作可能破坏了堆的性质，需要通过向下调整操作从新的堆顶开始，重新构建大堆。这一步骤确保了堆的根结点是剩余元素中的最大值。

⑤ 重复以上步骤：继续执行交换、减少堆大小、维护堆性质的步骤，直到堆的大小减少到只剩一个元素。此时，所有的元素都已经按升序排列。

总体来说，堆排序算法的思路是通过不断选出最大元素并将其放置到数组的末尾，同时维护剩余元素的大堆结构，以此来逐步构建一个升序数组。在每次选出最大元素后，都减少堆的大小，并利用向下调整操作来保持剩余元素的大堆性质，直到整个数组排序完成。

图形解析：下面是建完大堆后进行堆排序的过程。

2.利用向上调整函数或者向下调整函数建大堆排升序

代码：

//交换两个元素的函数
void swap(int* p1, int* p2)
{
	//判断指针p1与p2是否是空指针
	assert(p1 && p2);
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}


//建大堆
//(1)建大堆的向上调整
void AdjustUp1(int* a, int child)
{
	assert(a);
	//找当前孩子的双亲
	int parent = (child - 1) / 2;

	while (child > 0)
	{
		if (a[child] > a[parent])//若当前孩子比自己的双亲还有大，则当前孩子就要进行向上调整。
		{
			swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
			break;
	}
}

//(2)建大堆的向下调整
void AdjustDown1(int* a, int n, int parent)
{
	assert(a);
	//找当前双亲的左孩子
	int child = parent * 2 + 1;

	while (child < n)
	{
		//让child始终指向当前双亲的左右孩子中最大一个孩子
		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 HeapSort1(int* a, int n)
{
	//判断指针a是否是空指针
	assert(a);

	//注意：由于利用向上调整函数建堆的时间复杂度是O(N*logN),而利用向下调整函数建堆的时间复杂度是O(N)，导致我们在建大堆是一般使用向下调整函数来建大堆的。

	//1.在原数组中建大堆

	//(1)利用向上调整函数建大堆。
	/*int child = 0;
	for (child = 1; child < n; child++)
		AdjustUp1(a, child);*/

	//(2)利用向下调整函数建大堆
	int parent = 0;
	for (parent = (n - 1 - 1) / 2; parent >= 0; parent--)
		AdjustDown1(a, n, parent);

	//2.利用大堆把原数组排成升序
	//思路：
	int k = n - 1;//若想排好n个元素，则排序次数是k = n - 1。
	while (k--)
	{
		//(1)交换大堆堆顶元素和堆尾元素的值
		swap(&a[0], &a[n - 1]);

		//(2)不把处于数组尾部的堆顶元素看作是数组元素
		n--;

		//(3)利用向下调整操作保持数组剩余元素依然是个大堆
		AdjustDown1(a, n, 0);
	}

}

二、排降序，建小堆

​1.利用向上调整函数建小堆

1.1.建立小堆的思路

步骤1：初始化堆

  • 将给定的数据序列（例如：数组）看作是一个完全二叉树，但该数据序列暂时不满足堆的性质。

步骤2：向上调整函数

  • 从完全二叉树根结点的第一个孩子结点开始按照从左至右且从上往下的顺序对完全二叉树每个结点执行向上调整操作直到完全二叉树最后一个结点完成向上调整操作为止，最终使其整个数据序列满足小堆的性质。
1.2.以下是具体步骤：

步骤1：找到根结点的第一个孩子结点

  • 在一个完全二叉树中，根结点的第一个孩子结点的位置是 child = 1，其中 n 是结点的总数。

步骤2：执行向上调整

  • 从完全二叉树根结点的第一个孩子结点开始，依次向后遍历完全二叉树的每个结点。
  • 对于每个结点，执行以下操作：
    • 比较当前结点(即孩子结点)与其双亲结点的值。
    • 如果当前结点(即孩子结点)的值小于其双亲结点的值，则交换当前结点(即孩子结点)与其双亲结点的值，然后对交换后位于双亲结点位置的孩子结点继续执行向上调整操作。

步骤3：重复步骤2直到完全二叉树最后一个结点完成向上调整操作

  • 继续向后遍历完全二叉树并对每个结点执行向上调整，直到最后一个结点完成向上调整操作为止。
1.3.代码
//(利用向上调整函数建小堆。
int child = 0;
for (child = 1; child < n; child++)
	AdjustUp2(a, child);

2.利用向下调整函数建小堆

2.1.建立大堆的思路

(1)初始化堆：将给定的数据序列(例如：数组)看作是一个完全二叉树，但该数据序列暂时不满足堆的性质。

(1)向下调整函数：从最后一个孩子结点的双亲结点开始按照从右往左且从下往上的顺序对完全二叉树的每个结点执行向下调整操作直到完全二叉树的根结点完成向下调整操作为止，最终使其整个数据序列满足小堆的性质。

2.2.代码思路步骤

步骤1：找到最后一个孩子结点的双亲结点的位置

  • 在一个完全二叉树中，最后一个孩子结点的双亲结点的位置是parent = (n-1-1)/2，其中 n 是结点的总数。

步骤2：执行向下调整

  • 从最后一个孩子结点的双亲结点开始，依次向前遍历完全二叉树的每个结点。
  • 对于每个结点，执行向下调整操作：
    • 比较当前双亲与其左右子孩子结点中最小孩子的值。
    • 如果当前双亲结点的值大于最小孩子结点的值，则交换当前双亲结点与最小孩子结点的值，然后对交换后的位于最小孩子结点位置的双亲结点的值继续执行向下调整操作。

步骤3：重复步骤2直到完全二叉树的根结点完成向下调整操作。

  • 继续向前遍历完全二叉树并对每个结点执行向下调整，直到完全二叉树的根结点完成向下调整操作为止。
2.3.利用向下调函数建小堆的案例 

例1：在数组a没有变成大堆之前，一开始数组的元素是a[ ] = {1,3,8,5,10,9,6,2,7,4}。

图形解析：把数组a[ ] ={1,3,8,5,10,9,6,2,7,4}先想象成以下图形的完全二叉树，然后从完全二叉树最后一个孩子结点4的双亲结点10开始按照从右往左再从下往上的顺序对完全二叉树的每个结点进行向下调整操作直到完全二叉树根结点1完成向下调整操作为止才结束。最终数组a变成a[ ] = {1,2,6,3,4,9,8,5,7,10}而且这个数组a写成一个完全二叉树后可以看出这个完全二叉树是个大堆。

注意：以下是整个完全二叉树的所有左右子树变成小堆的执行顺序① —>② —> ③—> ④—>⑤。

2.4.代码 
//利用向下调整函数建大堆
int parent = 0;
for (parent = (n - 1 - 1) / 2; parent >= 0; parent--)
	AdjustDown2(a, n, parent);

3.建大堆排升序的思路

① 构建小堆：首先，通过向下调整函数（而非向上调整，因为向下调整更高效）将原数组转换成一个小堆。这样，堆的根结点（即数组的第一个元素）将是数组中的最小值。

② 交换堆顶与堆尾元素：一旦小堆构建完成，将堆顶元素（数组的第一个元素）与堆的最后一个元素进行交换。这样，数组中的最小值就被放置到了数组的末尾。

③ 减少堆的大小：交换操作完成后，认为堆的最后一个元素已经排定，因此不再将其视为堆的一部分，从而将堆的大小减少1。

④ 维护小堆的性质：由于交换操作可能破坏了堆的性质，需要通过向下调整操作从新的堆顶开始，重新构建小堆。这一步骤确保了堆的根结点是剩余元素中的最小值。

⑤ 重复以上步骤：继续执行交换、减少堆大小、维护堆性质的步骤，直到堆的大小减少到只剩一个元素。此时，所有的元素都已经按降序排列。

总体来说，堆排序算法的思路是通过不断选出最小元素并将其放置到数组的末尾，同时维护剩余元素的小堆结构，以此来逐步构建一个降序数组。在每次选出最小元素后，都减少堆的大小，并利用向下调整操作来保持剩余元素的小堆性质，直到整个数组排序完成。

图形解析：下面是建完小堆后进行堆排序的过程。

​2.利用向上调整函数或者向下调整函数建小堆排升序

代码：

//交换两个元素的函数
void swap(int* p1, int* p2)
{
	//判断指针p1与p2是否是空指针
	assert(p1 && p2);
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}


//建小堆的向上调整
void AdjustUp2(int* a, int child)
{
	assert(a);
	//找当前孩子的双亲
	int parent = (child - 1) / 2;

	while (child > 0)
	{
		if (a[child] < a[parent])//若当前孩子比自己的双亲还有小，则当前孩子就要进行向上调整
		{
			swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
			break;
	}
}

//建小堆的向下调整
void AdjustDown2(int* a, int n, int parent)
{
	assert(a);
	//找当前双亲的左孩子
	int child = parent * 2 + 1;

	while (child < n)
	{
		//让child始终指向当前双亲的左右孩子中最小的那个孩子
		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;
	}

}


//堆排序函数->在原数组a中建小堆来排降序
void HeapSort2(int* a, int n)
{
	//判断指针a是否是空指针
	assert(a);

	//注意：由于利用向上调整函数建堆的时间复杂度是O(N*logN),而利用向下调整函数建堆的时间复杂度是O(N)，导致我们在建大堆是一般使用向下调整函数来建小堆的。

	//1.在原数组中建大堆

	//(1)利用向上调整函数建大堆。
	/*int child = 0;
	for (child = 1; child < n; child++)
		AdjustUp2(a, child);*/

	//(2)利用向下调整函数建大堆
	int parent = 0;
	for (parent = (n - 1 - 1) / 2; parent >= 0; parent--)
		AdjustDown2(a, n, parent);

	//2.利用大堆把原数组排成升序
	//思路：
	int k = n - 1;//若想排好n个元素，则排序次数是k = n - 1。
	while (k--)
	{
		//(1)交换大堆堆顶元素和堆尾元素的值
		swap(&a[0], &a[n - 1]);

		//(2)不把处于数组尾部的堆顶元素看作是数组元素
		n--;

		//(3)利用向下调整操作保持数组剩余元素依然是个大堆
		AdjustDown2(a, n, 0);
	}

}

三、堆排序的时间复杂度

1.利用向上调整函数建堆的时间复杂度

(1)对利用向上调整函数建大堆的时间复杂度是O(N*logN)进行解析

(2)分析向上调整函数AdjustUp建堆的时间复杂度是O(N*logN )的原因

完全二叉树层数低的结点少，而结点少的向上调整次数少；完全二叉树层数高的结点多，而结点多的向上调整次数多，而且完全二叉树最后一层结点的结点总数几乎占整个完全二叉树的结点总数的一半进而导致利用向上调整函数建堆的时间复杂度高。总的来说，结点少的调整次数少，结点多的调整次数多。

2.利用向下调整函数建堆的时间复杂度

(1)对利用方式二的向下调整函数建堆的时间复杂度是O(N)进行分析

因为堆是完全二叉树，而满二叉树也是完全二叉树，此处为了简化使用满二叉树来证明(时间复杂度本来看的就是近似值，多几个节点不影响最终结果)：

因此：利用向下调整函数建堆的时间复杂度为O(N)。

(2)分析利用向下调整函数AdjustDown建堆的时间复杂度是O(N)的原因

完全二叉树层数低的结点少，而结点少的向向下调整次数多；完全二叉树层数高的结点多，而结点多的向下调整次数多，而且完全二叉树最后一层结点的结点总数几乎占整个完全二叉树的结点总数的一半进而导致利用向下调整函数建堆的时间复杂度低。总的来说，结点数量多的时候调整的次数少而结点少的时候调整次数多。

3.堆排序的时间复杂度和空间复杂度

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

3.1.时间复杂度：O(N*logN)

以利用向下调整函数建大堆来排升序为例解析时间复杂度为O(N*logN)的原因：

(1)建立大堆过程的时间复杂度计算

①初始化堆的时间复杂度： 在建立大堆的过程中，我们需要从最后一个孩子结点的双亲结点非开始按照从右往左且从下往上的往前遍历完全二叉树并对每个结点执行向下调整操作。最后一个孩子结点的索引是 child = (n-1-1)/2，其中 n 是结点的总数。

②向下调整的时间复杂度： 对于每个结点，向下调整的时间复杂度是 O(logN)，因为最坏的情况下，双亲结点可能需要与每一层的孩子结点比较和交换，直到到达叶结点。完全二叉树的高度是 O(logN)。

③总的时间复杂度： 建立大堆的过程中，我们需要对大约一半的结点执行向下调整操作，即从下标(n-1-1)/2 到 下标0 的结点。因此，总的时间复杂度是：O(1) + O(2) + ...  + O(logN-2) + O(logN-1)  + O(logN) ，这可以近似为：O(N*logN)。因为对于每个层级，向下调整的时间复杂度是 O(logN)，而每一层的节点数大约是上一层的两倍。

(2)排序过程的时间复杂度计算

①排序的时间复杂度： 在建立大堆之后，我们开始排序过程。排序过程中，我们需要执行以下步骤 N-1 次（因为最后一个元素不需要再移动）：

  • 将堆顶元素（最大值）与堆的最后一个元素交换，然后移除堆的最后一个元素（这实际上就是将最大值放置在正确的位置）。
  • 对新的堆顶元素执行向下调整操作，以恢复大堆的性质。

②每次调整的时间复杂度： 每次向下调整操作的时间复杂度是 O(logN)，因为堆的高度是 O(logN)。

③总的时间复杂度： 因为我们需要对 N-1 个元素执行上述操作，所以排序过程的总时间复杂度是：O(logN) + O(logN) + ... + O(logN) (共 N-1 次)。这可以表示为：O((N-1)*logN) = O(N*logN)

(3)对堆排序算法的时间复杂度是O(N*logN)的总结

将建立大堆的时间复杂度 O(NlogN) 和排序的时间复杂度 O(NlogN) 结合起来，整个利用向下调整函数建大堆并排升序的过程的总时间复杂度仍然是 O(N*logN)。尽管建立大堆和排序是两个不同的步骤，但它们的时间复杂度是相同的，并且在总的时间复杂度计算中，排序步骤的时间复杂度起主导作用。

3.2.空间复杂度：O(1)
3.3.稳定性：不稳定

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.mfbz.cn/a/886900.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

【人人保-注册安全分析报告-无验证方式导致安全隐患】

【人人保-注册安全分析报告-无验证方式导致安全隐患】

前言 由于网站注册入口容易被黑客攻击&#xff0c;存在如下安全问题&#xff1a; 1. 暴力破解密码&#xff0c;造成用户信息泄露 2. 短信盗刷的安全问题&#xff0c;影响业务及导致用户投诉 3. 带来经济损失&#xff0c;尤其是后付费客户&#xff0c;风险巨大&#xff0c;造…
阅读更多...
C++系列-多态

C++系列-多态

&#x1f308;个人主页&#xff1a;羽晨同学 &#x1f4ab;个人格言:“成为自己未来的主人~” 多态 多态就是不同类型的对象&#xff0c;去做同一个行为&#xff0c;但是产生的结果是不同的。 比如说&#xff1a; 都是动物叫声&#xff0c;猫是喵喵&#xff0c;狗是汪汪&am…
阅读更多...
Flink集群部署

Flink集群部署

本次部署1.17版本 需要修改的配置文件地方为 Job为指挥中心&#xff0c;只能有一台主机&#xff0c;集群中所有的配置文件都这样配置 Rest为客户端UI显示使用&#xff0c;集群中所有的配置文件都这样配置 Task是每个节点工作使用的&#xff0c;每个节点的Task各不相同 conf配…
阅读更多...
【mmengine】配置器(config)（进阶）继承与导出，命令行修改配置

【mmengine】配置器(config)（进阶）继承与导出，命令行修改配置

一、配置文件的继承 1.1 继承机制概述 新建optimizer_cfg.py: optimizer dict(typeSGD, lr0.02, momentum0.9, weight_decay0.0001)新建runtime_cfg.py: device "cuda" gpu_ids [0, 1] batch_size 64 epochs 100 num_workers 8新建resnet50.py: _base_ […
阅读更多...
数据结构-3.9.栈在递归中的应用

数据结构-3.9.栈在递归中的应用

一.函数被调用背后的过程&#xff1a;最后被调用的函数最先结束也符合栈的后进先出 1.main函数为主函数即程序入口&#xff0c;运行时主函数先入栈&#xff0c;然后存入主函数里的数据&#xff1b; 2.func1函数加载在栈中时他后面的代码的地址#1(调用返回地址&#xff0c;不是…
阅读更多...
OpenAI全新多模态内容审核模型上线：基于 GPT-4o，可检测文本和图像

OpenAI全新多模态内容审核模型上线：基于 GPT-4o，可检测文本和图像

在数字时代&#xff0c;内容安全问题愈发受到重视。9月26日&#xff0c;OpenAI 正式推出了一款全新的多模态内容审核模型&#xff0c;名为 “omni-moderation-latest”。 该模型基于最新的 GPT-4o 技术&#xff0c;能够准确地识别检测有害文本图像。这一更新将为开发者提供强大…
阅读更多...
Woocommerce怎么分类显示产品？如何将Shopify的产品导入到Woocommerce？

Woocommerce怎么分类显示产品？如何将Shopify的产品导入到Woocommerce？

WooCommerce作为WordPress的一个电子商务插件&#xff0c;功能强大、使用简洁&#xff0c;能够轻松集成到WordPress网站中&#xff0c;为用户提供了一个完整的在线商店解决方案&#xff0c;在国外还是挺受欢迎的。 Woocommerce怎么分类显示产品&#xff1f; 在Woocommerce中&a…
阅读更多...
TCP Analysis Flags 之 TCP ZeroWindowProbe

TCP Analysis Flags 之 TCP ZeroWindowProbe

前言 默认情况下&#xff0c;Wireshark 的 TCP 解析器会跟踪每个 TCP 会话的状态&#xff0c;并在检测到问题或潜在问题时提供额外的信息。在第一次打开捕获文件时&#xff0c;会对每个 TCP 数据包进行一次分析&#xff0c;数据包按照它们在数据包列表中出现的顺序进行处理。可…
阅读更多...
【C++】空指针和野指针

【C++】空指针和野指针

文章目录 1.空指针2.野指针总结 1.空指针 概念&#xff1a;指针变量指向内存中编号为0的空间。 用途&#xff1a;初始化指针变量。 注意&#xff1a;空指针指向的内存是不可以访问的。 示例&#xff1a; int main(){//指针变量p指向内存地址编号为0的空间int *PNULL&#…
阅读更多...
在java后端发送HTTPClient请求

在java后端发送HTTPClient请求

简介 HttpClient遵循http协议的客户端编程工具包支持最新的http协议 部分依赖自动传递依赖了HttpClient的jar包 明明项目中没有引入 HttpClient 的Maven坐标&#xff0c;但是却可以直接使用HttpClient原因是&#xff1a;阿里云的sdk依赖中传递依赖了HttpClient的jar包 发送get请…
阅读更多...
Django 配置邮箱服务，实现发送信息到指定邮箱

Django 配置邮箱服务，实现发送信息到指定邮箱

一、这里以qq邮箱为例&#xff0c;打开qq邮箱的SMTP服务 二、django项目目录设置setting.py 文件 setting.py 添加如下内容&#xff1a; # 发送邮件相关配置 EMAIL_BACKEND django.core.mail.backends.smtp.EmailBackend EMAIL_USE_TLS True EMAIL_HOST smtp.qq.com EMAIL…
阅读更多...
1.2.2 计算机网络的分层结构（下）

1.2.2 计算机网络的分层结构（下）

水平视角 YSCS协议&#xff08;压缩传输协议&#xff09; 发送方先压缩然后接收方再解压。 为什么要分层&#xff1f;为什么要制定协议&#xff1f; 计算机网路功能负责->采用分层结构&#xff0c;将诸多功能合理地划分在不同层次->对等层之间制定协议&#xff0c;以…
阅读更多...
正则表达式的使用示例--Everything文件检索批量重命名工具

正则表达式的使用示例--Everything文件检索批量重命名工具

一、引言 Everything是一款非常实用的文件搜索工具&#xff0c;它可以帮助您快速定位并查找计算机中的文件和文件夹。Everything搜索文件资料之神速&#xff0c;有使用过的朋友们都深有体会&#xff0c;相对于Windows自带的搜索功能&#xff0c;使用Everything&#xff0c;可以…
阅读更多...
QT将QBytearray的data()指针赋值给结构体指针变量后数据不正确的问题

QT将QBytearray的data()指针赋值给结构体指针变量后数据不正确的问题

1、问题代码 #include <QCoreApplication>#pragma pack(push, 1) typedef struct {int a; // 4字节float b; // 4字节char c; // 1字节int *d; // 8字节 }testStruct; #pragma pack(pop)#include <QByteArray> #include <QDebug>int main() {testStruct …
阅读更多...
基于VUE的在线手办交易平台购物网站前后端分离系统设计与实现

基于VUE的在线手办交易平台购物网站前后端分离系统设计与实现

目录 1. 需求分析 2. 技术选型 3. 系统架构设计 4. 前端开发 5. 后端开发 6. 数据库设计 7. 测试 8. 部署上线 9. 运维监控 随着二次元文化的兴起&#xff0c;手办作为一种重要的周边产品&#xff0c;受到了广大动漫爱好者的喜爱。手办市场的需求日益增长&#xff0c;…
阅读更多...
Android-Handle消息传递和线程通信

Android-Handle消息传递和线程通信

本文为作者学习笔记&#xff0c;如有误&#xff0c;请各位大佬指点 目录 一、同步异步 二、Java多线程通信 三、Handler是什么 四、Handler相关的类 五、Handler常用方法 1. 发送消息 2. 接收处理消息 3. 切换线程 六、使用Handler 使用Handler更新UI 使用Handler延…
阅读更多...
electron教程（三）窗口设置

electron教程（三）窗口设置

在main.js文件中&#xff0c;创建窗口时会设置窗口的大小&#xff0c;其实还有很多其他属性&#xff0c;可以根据实际需求选择设置&#xff0c;但部分属性存在局限性&#xff0c;官网也有明确告知&#xff1a;自定义窗口 | Electron (electronjs.org) 项目文件目录如下&#x…
阅读更多...
Windows安装Vim，并在PowerShell中直接使用vim

Windows安装Vim，并在PowerShell中直接使用vim

大家好啊&#xff0c;我是豆小匠。 这期介绍下怎么在windows的PowerShell上使用vim&#xff0c;方便在命令行里修改配置文件等。 先上效果图&#xff1a; 1、下载Vim GitHub传送门&#xff1a;https://github.com/vim/vim-win32-installer/releases 选择win-64的版本下载即可&…
阅读更多...
信息技术网络安全政策制定

信息技术网络安全政策制定

为什么要制定网络安全政策&#xff1f; 通常&#xff0c;公司并不认为需要制定网络安全政策。现有的政策是为了保护公司的资产&#xff0c;而数据也是一项资产。 网络安全政策的真正必要性很简单&#xff1a;网络安全并不像锁门或不偷公司笔那么简单。在许多情况下&#xff0…
阅读更多...
HTML的修饰(CSS) -- 第三课

HTML的修饰(CSS) -- 第三课

文章目录 前言一、CSS是什么&#xff1f;二、使用方式1. 基本语法2. 引入方式1.行内式2.内嵌式3. 链入式 3. 选择器1. 标签选择器2.类选择器3. id选择器4. 通配符选择器 4. css属性1. 文本样式属性2. 文本外观属性 5. 元素类型及其转换1. 元素的类型2. 元素的转换 6.css高级特性…
阅读更多...
最新文章

Copyright @ 2022~2023