快速排序和堆排序

末蓝、 2022-08-07 13:43 170阅读 0赞

最近在看算法方面的知识，自己动手写了点代码。为了以后复习方便，主要是自己总是遗忘，所以把这些代码保留下来。

</pre><pre name="code" class="cpp">#include<iostream>
    using namespace std;
    
    void quickSort(int a[], int l, int r)
    {
    	if(l < r){
    		swap(a[l], a[(l+r)/2]);
    		int i = l, j = r, t = a[i];
    		while(i < j){
    			while(i < j && a[j] >= t)
    				j--;
    			if(i < j)
    				a[i++] = a[j];
    			while(i < j && a[i] <=t)
    				i++;
    			if(i < j)
    				a[j--] = a[i];
    		}
    		a[i] = t;
    		quickSort(a, l, i - 1);
    		quickSort(a, i + 1, r);
    	}
    }
    
    //k为数组中的前k个数，i为当前的数（位置非下标，下标为i-1）
    void maxHeap(int a[], int k, int i){
    	int max = i-1;
    	if(2*i < k)
    		if(a[2*i] > a[max])
    			max = 2*i;
    	if(2*i - 1 < k)
    		if(a[2*i - 1] > a[max])
    			max = 2*i - 1;
    	if(max != i-1){
    		swap(a[max], a[i-1]);
    		maxHeap(a, k, max + 1);
    	}
    }
    void buildHeap(int a[], int k){
    	for(int i = k/2 - 1; i >= 0; i--)
    	{
    		maxHeap(a, k, i+1);
    	}
    }
    void heapSort(int a[], int k){
    	buildHeap(a, k);
    	int t = k-1;
    	while(t>0)
    	{
    		swap(a[t], a[0]);
    		maxHeap(a, t, 1);
    		t--;
    	}
    }
    
    int main(){
    	int a[] = {1, 5, 2, 10, 3, 5, 4, 8, 9};
    	//quickSort(a, 0, 8);
    	//heapSort(a, 9);
    	buildHeap(a, 4);
    	for(int i = 0; i < 9; i++){
    		cout<<a[i]<<" ";
    	}
    	cout<<endl;
    	return 0;
    }

在写堆排序时，主要是参数k的设置，这个k为希望数组的前k个元素进行相关操作，因为在 寻找最小的k个数问题中，需要建立前k个数的最大堆，所以书写函数时，考虑了相关问题。

发表评论取消回复

表情：

评论列表（有 0 条评论，170人围观）

还没有评论，来说两句吧...

相关阅读

相关堆和堆排序：为什么说堆排序没有快速排序快

“堆（Heap）” 是一种特殊的数。堆这种数据结构的应用场景非常多，最经典的莫过于堆排序了。堆排序是一种原地的、时间复杂度为 O(nlogn) 的排序算法。快速排序，平均情

逃离我推掉我的手/ 2023年06月22日 13:57/ 0 赞/ 98 阅读

相关作业23-快速排序与堆排序

1-1 对N个记录进行堆排序，需要的额外空间为O(N)。(F) \[解析\] 辅助空间是O(1) 需要用到的辅助空间有: rc(根节点的关键值) head的

忘是亡心i/ 2022年12月27日 14:14/ 0 赞/ 113 阅读

相关堆排序、归并排序、快速排序总结

昨天刚把这三个排序算法复习了一遍，其中归并排序和快速排序特别的重要，一定要熟练并理解透彻！以下排序的结果都默认为非递减 1、堆排序（默认大顶堆）堆排序的思想：首先

浅浅的花香味﹌/ 2022年09月28日 13:19/ 0 赞/ 167 阅读

相关堆排序与快速排序的奥妙

堆排序堆排序的核心思想是构建大（小）顶堆，然后与末尾元素交换值，并且，堆大小减一；这里面的重点是如何构建大（小）顶堆，这是最核心的部分，其实总结起来也很简单，首先明

清疚/ 2022年09月10日 04:11/ 0 赞/ 130 阅读

相关快速排序和堆排序

最近在看算法方面的知识，自己动手写了点代码。为了以后复习方便，主要是自己总是遗忘，所以把这些代码保留下来。 </pre><pre name="code" cl

末蓝、/ 2022年08月07日 13:43/ 0 赞/ 171 阅读

相关快速排序、归并排序、堆排序的实现

最近总是遇到面试问到归并排序的问题，下面我们来走一遍。 1、快速排序参考严蔚敏数据结构教材，下面是本人写的快速排序实现： include<iostream>

我会带着你远行/ 2022年08月07日 07:37/ 0 赞/ 184 阅读

相关快速排序，归并排序，堆排序python实现

http://blog.csdn.net/u011608357/article/details/37724329 快速排序的时间复杂度最好情况下为O(n\lo

淡淡的烟草味﹌/ 2022年07月17日 02:53/ 0 赞/ 265 阅读

相关选择排序和堆排序

选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数

朴灿烈づ我的快乐病毒、/ 2022年06月13日 08:07/ 0 赞/ 256 阅读

相关锦标赛排序和堆排序

　　1964年，堆排序被提出，它改善了锦标赛排序的种种缺点。　　锦标赛排序：　　锦标赛排序，也称为树形选择排序（Tree Selection Sort），是一种按

桃扇骨/ 2022年05月25日 02:21/ 0 赞/ 496 阅读

相关堆和堆排序

堆排序堆排序基本介绍 1. 堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为 O(nlogn)，它也

柔光的暖阳◎/ 2021年10月19日 21:12/ 0 赞/ 395 阅读