八大排序算法之堆排序的实现+经典TopK问题

这篇具有很好参考价值的文章主要介绍了八大排序算法之堆排序的实现+经典TopK问题。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

一.堆元素的上下调整接口

1.前言

2.堆元素向上调整算法接口

3.堆元素向下调整算法接口

二.堆排序的实现

1.空间复杂度为O(N)的堆排序(以排升序为例)

思路分析:

代码实现:

排序测试:

​时空复杂度分析:

2. 空间复杂度为O(1)的堆排序(以排降序为例)

将数组arr调整成堆的思路:

将数组arr调整成堆的时间复杂度分析: ​

在数组arr数组被调整成堆的基础上完成排序的思路

堆排序代码实现:

排序时空复杂度分析:

三.用堆数据结构解决TopK问题

1. 问题描述:

 2.问题分析与求解

 


一.堆元素的上下调整接口

1.前言

完全二叉树的物理结构和逻辑结构:

大根堆 topk,初阶数据结构,数据结构

关于堆和堆元素上下调整算法接口设计原理分析参见青菜的博客http://t.csdn.cn/MKzythttp://t.csdn.cn/MKzyt青菜友情提示:想要深刻理解堆排序,必须掌握堆的构建

注意:接下来给出的两个接口针对小根堆元素调整算法接口,若需要用到大根堆数据结构,只需在小根堆的元素调整算法接口中子父结点值比较符号换一下方向即可用于实现大根堆.

2.堆元素向上调整算法接口

函数首部:

void AdjustUp(HPDataType* arry, size_t child)  //child表示孩子结点的编号

HPDataType是typedef定义的数据类型,arry是指向堆区数组的指针,child是待调整的结点在完全二叉树中的编号(物理上是其数组下标)

  •  算法调用场景: 

大根堆 topk,初阶数据结构,数据结构

接口实现:

//元素交换接口
void Swap(HPDataType* e1, HPDataType* e2)
{
	assert(e1 && e2);
	HPDataType tem = *e1;
	*e1 = *e2;
	*e2 = tem;
}



//小堆元素的向上调整接口
void AdjustUp(HPDataType* arry, size_t child)  //child表示待调整的结点的编号
{
	assert(arry);
	size_t parent = (child - 1) / 2;           //找到child结点的父结点
	while (child > 0)						   //child减小到0时则调整结束(说明待调整结点被调整到了根结点位置)
	{
		if (arry[child] < arry[parent])        //父结点大于子结点,则子结点需要上调以保持小堆的结构
		{
			Swap(arry + child, arry+parent);
			child = parent;				//将原父结点作为新的子结点继续迭代过程
			parent = (child - 1) / 2;	//继续向上找另外一个父结点
		}
		else
		{
			break;						//父结点不大于子结点,则堆结构任然成立,无需调整
		}
	}
}
  • 循环的结束分两种情况:
  1. child减小到0时,说明待调整结点调整到了根结点的位置(小根堆数据结构恢复)
  2. 某次父子结点比较中,父结点的值若大于子结点,则说明小根堆数据结构恢复,break跳出循环即可
  • 调用该接口的前提是:待调整的结点上层结构(包括待调整结点的所在层,但不包括待调整结点本身)满足小根堆的数据结构,比如:大根堆 topk,初阶数据结构,数据结构否则的话堆元素的调整将失去意义(因为只有在满足上述前提的情况下,每次调用完该接口,待调整的结点的上层结构保持小根堆的数据结构,并且以待调整结点为叶结点的上层结构会成为一个堆)
  • 大根堆的元素向上调整算法接口:
  • 大根堆 topk,初阶数据结构,数据结构
  • 若要将接口改为大根堆元素向上调整算法接口,只需将上图中的红圈中的小于号改为大于号即可

3.堆元素向下调整算法接口

函数首部:

void AdjustDown(HPDataType* arry,size_t size,size_t parent)

HPDataType是typedef定义的数据类型,arry是指向堆区数组首地址的指针,size是堆的元素总个数,parent是待调整的结点在完全二叉树中的编号(物理上是其数组下标)

  •  算法调用场景: 

大根堆 topk,初阶数据结构,数据结构

接口实现:

//元素交换接口
void Swap(HPDataType* e1, HPDataType* e2)
{
	assert(e1 && e2);
	HPDataType tem = *e1;
	*e1 = *e2;
	*e2 = tem;
}

//小堆元素的向下调整接口
void AdjustDown(HPDataType* arry,size_t size,size_t parent)
{
	assert(arry);
	size_t child = 2 * parent + 1;   //确定父结点的左孩子的编号
	while (child < size)			 //child增加到大于或等于size时则调整结束
	{
		if (child + 1 < size && arry[child + 1] < arry[child]) //确定左右孩子中较小的孩子结点
		{
			++child;
		}
		if ( arry[child] < arry[parent])//父结点大于子结点,则子结点需要上调以保持小堆的结构
		{
			Swap(arry + parent, arry + child);
			parent = child;				//将原子结点作为新的父结点继续迭代过程
			child = 2 * parent + 1;		//继续向下找另外一个子结点
		}
		else
		{
			break;						//父结点不大于子结点,则堆结构任然成立,无需调整
		}
	}
}
  •  算法需要注意的一些边界条件:
  1. child >= size说明被调整元素已经被交换到了叶结点的位置,小根堆数据结构恢复,终止循环
  2. 接口中,我们只设计了一个child变量来表示当前父结点的孩子结点编号,因此我们需要先确定左右孩子中哪一个结点值较小,令child等于较小的孩子结点的编号:
    if (child + 1 < size && arry[child + 1] > arry[child]) //确定左右孩子中较小的孩子结点
    {
    	++child;
    }

    child + 1<size判断语句是为了确定当前父结点的右孩子是否存在

  • 调用该接口的前提是:待调整的结点位置的左右子树都满足小根堆的数据结构,比如:大根堆 topk,初阶数据结构,数据结构否则的话堆元素的调整将失去意义(因为只有在满足上述前提的情况下,每次调用完该接口后,待调整的结点位置的左右子树保持小根堆的数据结构,并且以待调整结点为根结点的子树会成为一个堆)

  • 大根堆的元素向下调整算法接口:

  • 大根堆 topk,初阶数据结构,数据结构

    若要实现大根堆的元素向下调整算法接口,我们只需将上图红圈中的两个小于号改为大于号即可 

堆元素上下调整算法接口的实现原理分析参见:http://t.csdn.cn/MKzythttp://t.csdn.cn/MKzyt

二.堆排序的实现

有了堆元素的上下调整算法接口后,我们便可以利用堆的数据结构来实现高效的排序算法.

现在我们给出一个一百个元素的数组(每个元素随机附一个值):

typedef int HPDataType;
int main()
{
	int arr[100] = { 0 };
	srand((unsigned int)time(NULL));
	for (int i = 0; i < 100; i++)
	{
		arr[i] = rand() % 10000;        //数组每个元素赋上一个随机值
	}
	
	return 0;
}

堆排序函数接口:

void HeapSort(int * arr,int size);

 arr是指向待排序数组首地址的指针,size是待排序的数组的元素个数

1.空间复杂度为O(N)的堆排序(以排升序为例)

思路分析:

  • 实现堆排序的其中一种非常暴力的思路是:
  1. 在HeapSort接口中动态开辟一个和待排序数组空间大小相同Heap数组作为
  2. 然后将待排序数组的元素逐个尾插到Heap数组中同时调用堆元素向上调整算法调整堆尾元素的位置来建堆(排升序则建立小根堆)
  3. 建堆过程完成后,再逐个取出堆顶数据(按照堆顶元素删除的方式取出,具体参见堆的实现http://t.csdn.cn/vhbJf)(堆顶数据为堆中的最小元素)从待排序数组首地址开始覆盖待排序数组的空间即可完成排序

排序算法图解:

  • 先将arr中的元素逐个尾插到Heap数组中建堆大根堆 topk,初阶数据结构,数据结构
  • 大根堆 topk,初阶数据结构,数据结构
  • 逐个Heap数组的堆顶元素利用堆顶元素删除操作放回到arr数组中,完成升序排序(其原理在于小根堆堆顶元素永远是堆中的最小元素)(堆顶元素删除操作指的是:先将堆顶元素与堆尾元素交换,维护堆尾的下标指针减一(堆元素个数减一),再将堆顶元素向下调整恢复小根堆数据结构):大根堆 topk,初阶数据结构,数据结构

代码实现:

//元素交换接口
void Swap(HPDataType* e1, HPDataType* e2)
{
	assert(e1 && e2);
	HPDataType tem = *e1;
	*e1 = *e2;
	*e2 = tem;
}



//小堆元素的向上调整接口
void AdjustUp(HPDataType* arry, size_t child)  //child表示待调整的结点的编号
{
	assert(arry);
	size_t parent = (child - 1) / 2;           //找到child结点的父结点
	while (child > 0)						   //child减小到0时则调整结束(说明待调整结点被调整到了根结点位置)
	{
		if (arry[child] < arry[parent])        //父结点大于子结点,则子结点需要上调以保持小堆的结构
		{
			Swap(arry + child, arry+parent);
			child = parent;				//将原父结点作为新的子结点继续迭代过程
			parent = (child - 1) / 2;	//继续向上找另外一个父结点
		}
		else
		{
			break;						//父结点不大于子结点,则堆结构任然成立,无需调整
		}
	}
}

//小堆元素的向下调整接口
void AdjustDown(HPDataType* arry,size_t size,size_t parent)
{
	assert(arry);
	size_t child = 2 * parent + 1;   //确定父结点的左孩子的编号
	while (child < size)			 //child增加到大于或等于size时则调整结束
	{
		if (child + 1 < size && arry[child + 1] < arry[child]) //确定左右孩子中较小的孩子结点
		{
			++child;
		}
		if ( arry[child] < arry[parent])//父结点大于子结点,则子结点需要上调以保持小堆的结构
		{
			Swap(arry + parent, arry + child);
			parent = child;				//将原子结点作为新的父结点继续迭代过程
			child = 2 * parent + 1;		//继续向下找另外一个子结点
		}
		else
		{
			break;						//父结点不大于子结点,则堆结构任然成立,无需调整
		}
	}
}


void HeapSort(int* arr, int size)
{
	assert(arr);
	int* Heap = (int*)malloc(size * sizeof(int));
	assert(Heap);
	int ptrarr = 0;		//维护arr数组的下标指针
	int ptrheap = 0;	//维护Heap数组的下标指针
	//逐个尾插元素建堆
	while (ptrarr < size)
	{
		Heap[ptrheap] = arr[ptrarr]; //将arr数组中的元素逐个尾插到Heap数组中
		AdjustUp(Heap, ptrheap);     //每尾插一个元素就将该元素向上调整保持小堆的数据结构
		ptrheap++;
		ptrarr++;

	}
	//逐个将堆顶的元素放回arr数组(同时进行删堆操作)
	ptrarr = 0;
	int HeapSize = size;
	while (ptrarr < size)
	{
		Swap(&Heap[0], &Heap[HeapSize - 1]);  //交换堆顶和堆尾的元素
		arr[ptrarr] = Heap[HeapSize-1];		  //将原堆顶元素插入arr数组中
		HeapSize--;                           //堆元素个数减一(完成堆数据弹出)
		ptrarr++;                             //维护arr的下标指针+1
		AdjustDown(Heap, HeapSize, 0);        //将交换到堆顶的数据向下调整恢复堆的数据结构
	}
}

排序测试:

int main()
{
	int arr[100] = { 0 };
	srand((unsigned int)time(NULL));
	for (int i = 0; i < 100; i++)
	{
		arr[i] = rand() % 10000;        //数组每个元素赋上一个随机值
	}

	HeapSort(arr, 100);
	for (int i = 0; i < 100; ++i)
	{
		printf("%d ", arr[i]);
	}
	
	return 0;
}

大根堆 topk,初阶数据结构,数据结构时空复杂度分析:

  • 由于尾插建堆堆顶删堆时间复杂度都是O(NlogN),因此排序的时间复杂度为O(NlogN)
  • 显然,在HeapSort接口中多开辟了一个Heap数组,排序的空间复杂度为O(N)
  • 关于建堆和删堆的时间复杂度证明参见青菜的博客:http://t.csdn.cn/MKzythttp://t.csdn.cn/MKzyt
  • 该种堆排序代码量很大,数据并发量也很大,而且空间复杂度较高,接下来我们来实现一种最优良的堆排序算法

2. 空间复杂度为O(1)的堆排序(以排降序为例)

前面的堆排序算法中引入了Heap数组来建堆,浪费了很多空间。

实际上,我们可以在待排序数组上原地完成堆的构建(即将数组arr调整成堆).

将数组arr调整成堆的思路:

  • 现有一个乱序数组arr,逻辑上我们将其看成一颗完全二叉树:大根堆 topk,初阶数据结构,数据结构
  • 接下来我们尝试用堆的元素向下调整算法接口将arr调整成小根堆 
  1. 调用堆元素向下调整接口的前提是:待调整的结点位置的左右子树都满足小根堆的数据结构(因为在满足这个前提的情况下,我们每次调用完该接口待调整的结点位置的左右子树保持小根堆的数据结构,并且以待调整结点为根结点的子树会成为一个堆)
  2. 由上述前提可知,如果从堆顶(或中间任意一个位置的结点)元素开始调整堆是没有意义的,所以我们只能从堆尾的子结构开始调堆:大根堆 topk,初阶数据结构,数据结构
  3. 通过上图的分析,我们可以通过堆尾元素找到第一个要被向下调整的结点,然后从第一个要被向下调整的结点开始依次往前向下调整其他结点直到完成对树的根结点的向下调整之后,整颗完全二叉树就会被调整成堆:
  4. 调堆小动画:大根堆 topk,初阶数据结构,数据结构
  • 实现将arr数组调整成小根堆的代码:
    void HeapSort(int* arr, int size)
    {
    	assert(arr);
    	int parent = (size - 1 - 1) / 2;	//找到第一个要被调整向下调整的元素
    	for (; parent >= 0; --parent)
    	{
    		AdjustDown(arr, size, parent);  //逐个元素向下调整完成堆的构建
    	}
    }

将数组arr调整成堆的时间复杂度分析: 大根堆 topk,初阶数据结构,数据结构

因此假设arr数组中有N个元素,将数组arr调整成堆的时间复杂度为:O(N)

在数组arr数组被调整成堆的基础上完成排序的思路

  • 数组arr被调整成小根堆后,我们只需逐个删除堆顶元素就可以完成所有数的降序排序(堆顶的元素是堆中的最值)大根堆 topk,初阶数据结构,数据结构
  • 堆元素删除操作指的是:先将堆顶元素与堆尾元素交换,维护堆尾的下标指针减一(堆元素个数减一),再将堆顶元素向下调整恢复小根堆数据结构(保证堆顶元素永远为堆中的最值))
  • 逐个删除堆顶元素完成降序排序的过程图解:大根堆 topk,初阶数据结构,数据结构
  • 整个排序的过程其实相当于每次选出堆顶的数据(堆中的最值)交换到堆尾,因此堆排序是一种选择排序
  • 由上述算法设计思路可知:为了完成堆排序我们只需额外设计一个堆元素向下调整算法接口

堆排序代码实现:

//元素交换接口
void Swap(HPDataType* e1, HPDataType* e2)
{
	assert(e1 && e2);
	HPDataType tem = *e1;
	*e1 = *e2;
	*e2 = tem;
}

//小堆元素的向下调整接口
void AdjustDown(HPDataType* arry,size_t size,size_t parent)
{
	assert(arry);
	size_t child = 2 * parent + 1;   //确定父结点的左孩子的编号
	while (child < size)			 //child增加到大于或等于size时则调整结束
	{
		if (child + 1 < size && arry[child + 1] < arry[child]) //确定左右孩子中较小的孩子结点
		{
			++child;
		}
		if ( arry[child] < arry[parent])//父结点大于子结点,则子结点需要上调以保持小堆的结构
		{
			Swap(arry + parent, arry + child);
			parent = child;				//将原子结点作为新的父结点继续迭代过程
			child = 2 * parent + 1;		//继续向下找另外一个子结点
		}
		else
		{
			break;						//父结点不大于子结点,则堆结构任然成立,无需调整
		}
	}
}

void HeapSort(int* arr, int size)
{
	assert(arr);
	int parent = (size - 1 - 1) / 2;	//找到第一个要被调整向下调整的元素
	for (; parent >= 0; --parent)
	{
		AdjustDown(arr, size, parent);  //逐个元素向下调整完成堆的构建
	}

	while (size > 0)					//逐个删除堆顶元素完成降序排序,我们将size作为堆尾指针
	{
		Swap(&arr[0], &arr[size - 1]);  //交换堆尾与堆顶元素
		size--;							//堆尾指针减一,堆元素个数减一
		AdjustDown(arr, size, 0);       //将堆顶元素向下调整恢复小根堆数据结构
	}
}

排序接口测试: 

int main()
{
	int arr[100] = { 0 };
	srand((unsigned int)time(NULL));
	for (int i = 0; i < 100; i++)
	{
		arr[i] = rand() % 10000;      //数组每个元素赋上一个随机值
	}

	HeapSort(arr, 100);
	for (int i = 0; i < 100; ++i)
	{
		printf("%d ", arr[i]);
	}
	
	return 0;
}

大根堆 topk,初阶数据结构,数据结构

排序时空复杂度分析:

  • 逐个删除堆顶元素直到将堆删空的时间复杂度为O(NlogN),证明分析参见青菜的博客:http://t.csdn.cn/vhbJfhttp://t.csdn.cn/vhbJf
  • 已知将arr数组调整成堆的时间复杂度为O(N),因此堆排序整体的时间复杂度为O(NlogN)
  • 同时易知,堆排序算法的空间复杂度为O(1)
  • 可见堆排序是一中高效的选择排序算法

三.用堆数据结构解决TopK问题

TopK问题指的是,从N个元素数组中,选出K个最值.(K<=N)

Leetcode上面有相关题型.

面试题 17.14. 最小K个数 - 力扣(Leetcode)

1. 问题描述:

设计一个算法,找出数组中最小的k个数。以任意顺序返回这k个数均可。(数组元素个数为arrSize)

(k<=arrSize)

示例:

输入: arr = [1,3,5,7,2,4,6,8], k = 4
输出: [1,2,3,4]

题解接口: 

int* smallestK(int* arr, int arrSize, int k, int* returnSize)
{

}

arrSize为题设数组的元素个数,k为要找出的最小数的个数,returnSize是结果数组元素个数

 2.问题分析与求解

  • 本题如果直接对arr数组进行排序理论上是可以解决的,但是时间效率略低(O(NlogN)),有种杀鸡用牛刀的感觉
  • 我们可以考虑利用堆数据结构实现本题的最优解之一:
  1. 首先创建一个k*sizeof(int)字节大小数组Heap用于存储大根堆
  2. 然后将arr中前k个元素尾插到Heap中建立大根堆
  3. 然后将arr中后(arrSize-k)个元素逐个与Heap堆顶的元素比较,若arr中后(arrSize-k)个元素中的某元素小于Heap堆顶的元素,则将其与Heap堆顶元素交换,再将其进行向下调整操作保持大根堆的数据结构(元素交换入堆)
  4. 完成arr中后(arrSize-k)个元素Heap堆顶遍历比较后,堆中最后剩下的就是arr数组中最小的k个元素大根堆 topk,初阶数据结构,数据结构

算法图解: 大根堆 topk,初阶数据结构,数据结构

算法的合理性证明:

  • 由于大根堆堆顶元素是堆中的最大元素,因此在arr中后(arrSize-k)个元素Heap堆顶遍历比较的过程中没有入堆的元素一定都大于堆中的k个元素,因此最终堆中的k个元素一定是arr数组中最小的k个元素

题解代码:

void Swap(int* e1 ,int* e2)
{
    int tem = *e1;
    *e1 = *e2;
    *e2 = tem;
}

//大堆元素的向上调整接口
void AdjustUp(int * arry, size_t child)     //child表示待调整结点的编号
{
	assert(arry);
	size_t parent = (child - 1) / 2;
	while (child > 0)						//child减小到0时则调整结束
	{
		if (arry[child] > arry[parent])     //父结点小于子结点,则子结点需要上调以保持大堆的结构
		{
			Swap(arry + child, arry+parent);
			child = parent;				    //将原父结点作为新的子结点继续迭代过程
			parent = (child - 1) / 2;	    //继续向上找另外一个父结点
		}
		else
		{
			break;						    //父结点不小于子结点,则堆结构任然成立,无需调整
		}
	}
}


//大堆元素的向下调整接口
void AdjustDown(int * arry,size_t size,size_t parent)
{
	assert(arry);
	size_t child = 2 * parent + 1;   //确定父结点的左孩子的编号
	while (child < size)			 //child增加到大于或等于size时则调整结束
	{
		if (child + 1 < size && arry[child + 1] > arry[child]) //确定左右孩子中较大的孩子结点
		{
			++child;
		}
		if ( arry[child] > arry[parent])//父结点小于子结点,则子结点需要上调以保持大堆的结构
		{
			Swap(arry + parent, arry + child);
			parent = child;				//将原子结点作为新的父结点继续迭代过程
			child = 2 * parent + 1;		//继续向下找另外一个子结点
		}
		else
		{
			break;						//父结点不小于子结点,则堆结构任然成立,无需调整
		}
	}
}

int* smallestK(int* arr, int arrSize, int k, int* returnSize)
{
    if(0==k)
    {
        *returnSize =0;
        return NULL;
    }
    int * Heap = (int*)malloc(k*sizeof(int));
    *returnSize = k;                     //创建一个空间大小为k的数组用于存储堆
    int ptrHeap =0;                      //维护堆尾的指针
    while(ptrHeap<k)                     //将arr数组前k个元素尾插到Heap中完成建堆
    {
        Heap[ptrHeap]=arr[ptrHeap];
        AdjustUp(Heap,ptrHeap);    
        ptrHeap++;
    }


    int ptrarr = k;             //用于遍历arr中后(arrSize-k)个元素的下标指针
    while(ptrarr < arrSize)     //将arr中后(arrSize-k)个元素逐个与Heap堆顶的元素进行比较
    {
        //如果找到arr中后(arrSize-k)个元素中比堆顶元素小的元素则将该元素替换入堆
        //并通过堆元素向下调整接口保持大根堆的数据结构
        if(Heap[0]>arr[ptrarr])
        {
            Swap(&Heap[0],&arr[ptrarr]);
            AdjustDown(Heap,k,0);
        }
        ptrarr++;
    }
    return Heap;                  //返回Heap数组作为及结果
}

大根堆 topk,初阶数据结构,数据结构

算法时空复杂度分析:

设数组arr元素个数为N

  • 建立Heap数组堆的时间复杂度为O(klogk)
  • arr后(N-k)个元素与heap堆顶元素比较并入堆的时间复杂度为O((N-k)logk)(在最坏的情况下,arr后(N-k)个元素每个都进行了交换入堆并且被调整到了堆的叶子结点位置)
  • 因此算法的总体时间复杂度为O(Nlogk)
  • 易知算法的空间复杂度为O(k)

TopK问题的求解思想有着十分重要的实际意义

比如在硬盘中有十亿个数据,我们想选出其中的100个最小值,那么利用上面的算法思想我们就可以在极少的内存消耗,极高的时间效率下完成这个工作.

大根堆 topk,初阶数据结构,数据结构文章来源地址https://www.toymoban.com/news/detail-787604.html

到了这里,关于八大排序算法之堆排序的实现+经典TopK问题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构学习分享之堆的详解以及TopK问题

    💓博主CSDN主页:杭电码农-NEO💓   ⏩专栏分类:数据结构学习分享⏪   🚚代码仓库:NEO的学习日记🚚   🌹关注我🫵带你了解更多数据结构的知识   🔝🔝 本章就给大家带来久违的堆的知识,如果你还不知道数的相关知识,或者什么是完全二叉树,请跳转 树的介绍, 本章的堆结

    2024年02月05日
    浏览(109)
  • 堆排序+TopK问题——“数据结构与算法”

    各位CSDN的uu们你们好呀,好久不见,停更了很长一段时间吧,最近小雅兰会开始慢慢更新起来的,下面,就进入小雅兰今天的分享的知识点吧,让我们一起进入堆的世界!!! 堆排序——(1) heap.h的内容: heap.c的内容: test.c的内容: 这样的堆排序其实也是可以的 但是有弊

    2024年02月13日
    浏览(49)
  • 【数据结构】长篇详解堆,堆的向上/向下调整算法,堆排序及TopK问题

    堆就是将一组数据所有元素按完全二叉树的顺序存储方式存储在一个 一维数组 中,并满足树中 每一个父亲节点都要大于其子节点 称为 大堆 (树中 每一个父亲节点都要大于其子节点 称为 小堆 )。 性质 ①对于大堆(大根堆)来说,堆的顶部也就是数组首元素一定是最大的元素 ②

    2024年02月07日
    浏览(42)
  • 八大排序算法之归并排序(递归实现+非递归实现)

    目录 一.归并排序的基本思想 归并排序算法思想(排升序为例) 二.两个有序子序列(同一个数组中)的归并(排升序) 两个有序序列归并操作代码: 三.归并排序的递归实现 递归归并排序的实现:(后序遍历递归) 递归函数抽象分析:  四.非递归归并排序的实现 1.非递归归并排序算法思想

    2024年02月03日
    浏览(41)
  • 【DS】八大排序算法实现详解

    ✨ 博客主页: 心荣~ ✨ 系列专栏: 【Java实现数据结构】 ✨ 一句短话: 难在坚持,贵在坚持,成在坚持! 排序 :所谓排序,就是使一串记录,按照其中的某个或某些的大小,递增或递减的排列起来的操作。 稳定性 :假定在待排序的记录序列中,存在多个具有相同的

    2024年01月17日
    浏览(46)
  • 【经典八大排序】

    本文所介绍的排序算法均以升序为例。 直接插入排序是从一段数据中将一个数据在合适的位置插入。 案例: 一张图弄懂直接插入排序 实现代码: 直接插入排序时间复杂度 直接插入排序的时间复杂度为:O(N^2),因为最坏的情况是逆序的情况: 每一次插入需要挪动的次数为:

    2023年04月18日
    浏览(27)
  • 八大排序算法之快速排序(下篇)(快排的优化+非递归快排的实现)

    目录 一.前言 1.快速排序的实现: 快速排序的单趟排序(排升序)(快慢指针法实现):​ 2.未经优化的快排的缺陷 二.快速排序的优化 1.三数取中优化 优化思路: 2. 小区间插入排序优化 小区间插排优化的递归快排: 三.非递归快速排序的实现 1.快排一个难以避免的缺陷(暂不考虑三指针

    2024年02月02日
    浏览(49)
  • 数据结构与算法之堆排序

    堆排序 (Heap Sort)是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构,每个结点的值都大于或等于其左右孩子结点的值,称为大顶堆;或者每个结点的值都小于或等于其左右孩子结点的值,称为小顶堆。如下图: 同时,我们对堆中的结点按

    2024年02月09日
    浏览(42)
  • 解密堆排序与TopK问题

    📙 作者简介:  清水加冰,目前大二在读,正在学习C/C++、Python、操作系统、数据库等。 📘 相关专栏: C语言初阶、C语言进阶、C语言刷题训练营、数据结构刷题训练营、有感兴趣的可以看一看。 欢迎点赞 👍 收藏 ⭐留言 📝 如有错误还望各路大佬指正! ✨每一次努力都

    2024年02月07日
    浏览(31)
  • 追梦之旅【数据结构篇】——C语言手撕八大经典排序

        😎博客昵称:博客小梦 😊最喜欢的座右铭:全神贯注的上吧!!! 😊作者简介:一名热爱C/C++,算法等技术、喜爱运动、热爱K歌、敢于追梦的小博主! 😘博主小留言:哈喽! 😄各位CSDN的uu们,我是你的博客好友小梦,希望我的文章可以给您带来一定的帮助,话不

    2024年02月17日
    浏览(48)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包