精华内容
下载资源
问答
  • 先从数组A[ ]中取前k个元素建立大根堆.../*给定数组A[n],设计最优算法查找第k小元素,最优算法是堆排序,时间复杂度O(nlogk)*/ void Adjust(A[],k,len){ int i; A[0]=A[k]; for(i=k*2;i<len;i*=2){ if(A[i]<

    先从数组A[ ]中取前k个元素建立大根堆,然后再遍历剩下的n-k个元素,

    如果大于或者等于堆顶,则舍弃;

    如果小于堆顶,则将其与堆顶替换,并将换下来的堆顶舍弃,然后重新向下调整为大根堆,最后堆顶即为所求。

    时间复杂度为O(nlogk)

    /*给定数组A[n],设计最优算法查找第k小元素,最优算法是堆排序,时间复杂度O(nlogk)*/
    void Adjust(A[],k,len){
    	int i;
    	A[0]=A[k];
    	for(i=k*2;i<len;i*=2){
    		if(A[i]<A[i+1]){
    			i++;
    		}
    		if(A[0]<A[i]){
    			A[k]=A[i];
    			k=i;
    		}
    		else break;
    	}
    	A[k]=A[0];
    }
    
    void HeapSort(int A[]){
    	int n=A[].length;
    	for(i=k/2;i>=1;i--)		//取前k个元素建立大根堆 
    		Adjust[A,i,k];
    	for(i=k+1;i<=n;i++){
    		if(A[i]<A[1]){	//A[1]位堆顶 
    			A[1]=A[i];
    			Adjust[A,1,k]; 
    		}
    	}
    	return A[1];	//堆顶即为所求 
    }

     

    展开全文
  • 堆排序建立初始堆

    万次阅读 2020-01-08 19:35:34
    例1.有一组记录的排序码为 (3,5,4,7,1,2),则利用堆排序的方法建立的初始堆为 _____________?

    例1.有一组记录的排序码为 (3,5,4,7,1,2)(3, 5, 4, 7, 1, 2),则利用堆排序的方法建立的初始堆为 _____________?

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    所以初始堆为 (7,5,4,3,1,2)(7,5,4,3,1,2)

    展开全文
  • 有组记录的排序码为{ 46,79,56,38,40,84 },则利用堆排序的方法建立的初始堆为: A. 84,79,56,46,40,38 B. 84,56,79,40,46,38 C. 79,46,56,38,40,80 D. 84,79,56,38,40,46 对N个...

    判断题

    1. NN个记录进行简单选择排序,比较次数和移动次数分别为O(N2)O(N^2)O(N)O(N)
      T
    2. NN个记录进行堆排序,需要的额外空间为O(N)O(N)
      F

    选择题

    1. 有组记录的排序码为{ 46,79,56,38,40,84 },则利用堆排序的方法建立的初始堆为:

      • A. 84,79,56,46,40,38
      • B. 84,56,79,40,46,38
      • C. 79,46,56,38,40,80
      • D. 84,79,56,38,40,46

      大顶堆:每个结点的值都大于或等于其左右孩子结点的值

    2. 对N个记录进行堆排序,最坏的情况下时间复杂度是:

      • A. O(logN)O(\log{N})
      • B. O(N2)O(N^2)
      • C. O(NlogN)O(N\log{N})
      • D. O(N)O(N)
    3. NN个元素采用简单选择排序,比较次数和移动次数分别为:

      • A. O(logN),O(N2)O(\log{N}),O(N^2)
      • B. O(NlogN),O(NlogN)O(N\log{N}),O(N\log{N})
      • C. O(N),O(logN)O(N),O(\log{N})
      • D. O(N2),O(N)O(N^2),O(N)
    4. NN个记录进行堆排序,需要的额外空间为:

      • A. O(N)O(N)
      • B. O(logN)O(\log{N})
      • C. O(1)O(1)
      • D. O(NlogN)O(N\log{N})
    5. 在快速排序的一趟划分过程中,当遇到与基准数相等的元素时,如果左指针停止移动,而右指针在同样情况下却不停止移动,那么当所有元素都相等时,算法的时间复杂度是多少?

      • A. O(N2)O(N^2)
      • B. O(N)O(N)
      • C. O(logN)O(\log{N})
      • D. O(NlogN)O(N\log{N})
    6. NN个记录进行快速排序,在最坏的情况下,其时间复杂度是:

      • A. O(N2)O(N^2)
      • B. O(NlogN)O(N\log{N})
      • C. O(N2logN)O(N_2\log{N})
      • D. O(N)O(N)
    7. 排序过程中,对尚未确定最终位置的所有元素进行一遍处理称为一“趟”。下列序列中,不可能是快速排序第二趟结果的是:

      • A. 5, 2, 16, 12, 28, 60, 32, 72
      • B. 5, 2, 12, 28, 16, 32, 72, 60
      • C. 2, 12, 16, 5, 28, 32, 72, 60
      • D. 2, 16, 5, 28, 12, 60, 32, 72

      A中,第一次快排选的基准值是72,第二次的基准值是28
      C中,第一次的基准值是28,第二次的基准值是2 和32.
      D中,第一次的基准值是72,第二次的是2

    8. 对于10个数的简单选择排序,最坏情况下需要交换元素的次数为:

      • A. 100
      • B. 9
      • C. 45
      • D. 36
    展开全文
  • 堆排序

    2019-04-02 10:23:00
    堆排序 算法说明 ...堆排序有两中方法: 利用最大堆得到是从小到大排序; 利用最小堆得到最大到最小排序. 两种方法都需要向下调整 最大堆排序: void maxTrickleDown(int *a, int start, int end) { ...

    堆排序

    算法说明

    若数组中节点的索引为x, 则

    (1) 它的父节点下标为 (x-1)/2

    (2) 它的左子节点的下标为 2*x+1

    (3) 它的右子节点的下标为 2*x+2

    堆排序有两中方法: 利用最大堆得到的是从小到大排序; 利用最小堆得到最大到最小排序. 两种方法都需要向下调整

    最大堆排序:

    void maxTrickleDown(int *a, int start, int end) {
        int ct = start;         // 当前节点索引
        int left = 2 * ct + 1;  // 当前节点左孩子
        int temp = a[ct];       // 当前节点值
    
        for (; left <= end; (left = 2 * left + 1)) {
            // 最大堆调整, 取孩子值最大的索引
            if ((left < end) && (a[left] < a[left + 1]))
                left++;             
            if (temp >= a[left])    // 当前索引的值比两个孩子都大时停止循环
                break;
            else {                  // 否则向下交换
                a[ct] = a[left];
                a[left] = temp;
            }
            ct = left;
        }
    }
    
    void maxHeapSort(int *arr, int len)  {
        // 从(len/2-1)到0逐次遍历, 遍历结束后得到最大堆
        for (int i = len / 2 - 1; i >= 0; i--) 
            maxTrickleDown(arr, i, len - 1);
    
        for (int i = len - 1; i > 0; i--) {
            mySwap(arr[0], arr[i]);         // 把最大值和最后一个元素交换
            maxTrickleDown(arr, 0, i - 1);  // 堆调整
        }
    }

    最小堆排序

    void minTrickleDown(int *a, int start, int end) {
        int ct = start;
        int left = 2 * ct + 1;
        int temp = a[ct];
    
        for (; left <= end; left = 2 * left + 1) {
            // 最小堆, 取值最小的孩子节点的索引
            if ((left < end) && (a[left] > a[left + 1]))
                left++;
            if (temp <= a[left])    // 当前索引比两个孩子都小, 则结束循环
                break;
            else {                  // 否则进行交换
                a[ct] = a[left];
                a[left] = temp;
            }
            ct = left;
        }
    }
    
    void minHeapSort(int *a, int len) {
        // 从(len/2-1)开始遍历, 遍历结束后得到最小堆
        for (int i = len / 2 - 1; i >= 0; i--)
            minTrickleDown(a, i, len - 1);
    
        for (int i = len - 1; i > 0; i--) {
            mySwap(a[0], a[i]);             // 把最小值和最后一个元素交换
            minTrickleDown(a, 0, i - 1);    // 堆调整
        }
    }

    效率和稳定性

    在构建对的过程中, 应为是完全二叉树从最下层到最右边的非终端节点开始构建, 将它与其孩子进行比较和若有必要的交换, 对于每个非终端节点来说, 其实最多进行两次比较和互换操作, 因此整个构建堆的时间复杂度为O(N)

    在正式排序时, 第i次取堆顶记录重建堆需要用O(logi)的时间(完全二叉树的某个节点到根结点的距离为logi+1), 并且需要去n-1次堆定记录, 因此重建堆的时间复杂度为O(nlogn)

    总体来说, 堆排序的时间复杂度为O(nlogn). 由于堆排序对原始记录的排序状态并不敏感, 因此无论是最好, 最坏和平均时间复杂度都为O(nlogn). 这在性能上显然要远远好过于冒泡, 简单选择, 直接插入的O(n^2)的时间复杂度

    由于记录的比较与交换时跳跃式进行, 因此堆排序是一种不稳定的排序方法

    测试

    #include <iostream> 
    using namespace std;
    
    void mySwap(int &a, int &b) {
        int temp = a;
        a = b;
        b = temp;
    }
    
    void maxTrickleDown(int *a, int start, int end) {
        int ct = start;         // 当前节点索引
        int left = 2 * ct + 1;  // 当前节点左孩子
        int temp = a[ct];       // 当前节点值
    
        for (; left <= end; (left = 2 * left + 1)) {
            // 最大堆调整, 取孩子值最大的索引
            if ((left < end) && (a[left] < a[left + 1]))
                left++;             
            if (temp >= a[left])    // 当前索引的值比两个孩子都大时停止循环
                break;
            else {                  // 否则向下交换
                a[ct] = a[left];
                a[left] = temp;
            }
            ct = left;
        }
    }
    
    void maxHeapSort(int *arr, int len)  {
        // 从(len/2-1)到0逐次遍历, 遍历结束后得到最大堆
        for (int i = len / 2 - 1; i >= 0; i--) 
            maxTrickleDown(arr, i, len - 1);
    
        for (int i = len - 1; i > 0; i--) {
            mySwap(arr[0], arr[i]);         // 把最大值和最后一个元素交换
            maxTrickleDown(arr, 0, i - 1);  // 堆调整
        }
    }
    
    void minTrickleDown(int *a, int start, int end) {
        int ct = start;
        int left = 2 * ct + 1;
        int temp = a[ct];
    
        for (; left <= end; left = 2 * left + 1) {
            // 最小堆, 取值最小的孩子节点的索引
            if ((left < end) && (a[left] > a[left + 1]))
                left++;
            if (temp <= a[left])    // 当前索引比两个孩子都小, 则结束循环
                break;
            else {                  // 否则进行交换
                a[ct] = a[left];
                a[left] = temp;
            }
            ct = left;
        }
    }
    
    void minHeapSort(int *a, int len) {
        // 从(len/2-1)开始遍历, 遍历结束后得到最小堆
        for (int i = len / 2 - 1; i >= 0; i--)
            minTrickleDown(a, i, len - 1);
    
        for (int i = len - 1; i > 0; i--) {
            mySwap(a[0], a[i]);             // 把最小值和最后一个元素交换
            minTrickleDown(a, 0, i - 1);    // 堆调整
        }
    }
    
    
    int main() {
        int a[] = { 149, 192, 66, 66, 47, 152, 159, 195, 61, 66, 17, 168, 118, 64, 27, 80, 30, 105 };
        int len = (sizeof(a)) / sizeof(a[0]);
    
        cout << "排序之前: " << endl;
        for (int i = 0; i < len; i++) {
            cout << a[i] << " ";
        }
        cout << endl;
    
        maxHeapSort(a, len);
        //minHeapSort(a, len);
    
        cout << "排序之后: " << endl;
        for (int i = 0; i < len; i++) {
            cout << a[i] << " ";
        }
        cout << endl;
    
        return 0;
    }
    
    /*
    排序之前:
    149 192 66 66 47 152 159 195 61 66 17 168 118 64 27 80 30 105
    排序之后:
    17 27 30 47 61 64 66 66 66 80 105 118 149 152 159 168 192 195
    请按任意键继续. . .
    */

    转载于:https://www.cnblogs.com/hesper/p/10641000.html

    展开全文
  • 由于N取值很大,所以不可能把N个值全部保存下来后再通过排序的方法解决,这样做缺点有: 1、需要分配大量内存来保存这N个数 2、只需要找到前K小,其它N-K个数没必要保存 3、假如有很多组这样的N个数都需要找到前K小...
  • 堆排序和归并排序

    2021-04-15 16:31:42
    之前总结过快排,想看的童鞋可以一看,与本文所讲的堆排和归并排序一样用到递归的方法 点击->快排详解 文章目录堆排序和归并排序一、堆排序过程二、归并排序过程 一、堆排序过程 简介:个人认为堆排序相当于一个...
  • 关于堆排序

    2019-12-26 19:35:26
    堆排序实现的方法利用堆的父节点大于子节点的特性来进行不断建堆使得最上面的元素始终未整个数组中的最大值,然后将该堆的最大值删除(放置于堆尾,即将堆的顶部与尾部元素进行交换),然后重复进行建堆操作,即...
  • 堆排序C++实现

    2021-03-31 11:04:27
    7.堆排序堆排序的基本思想堆排序的实现步骤C++代码实现 堆排序的基本思想 堆排序是利用堆这种数据结构而设计的一种不稳定的排序算法,时间复杂度O(N*logN),额外空间复杂度O(1),堆排序有以下特点: 堆的数据结构:...
  • 堆排序的底层实现

    2019-06-23 17:21:30
    堆排序是一种树形选择排序方法,它的特点是:在排序的过程中,将array[0,…,n-1]看成是一颗完全二叉树的顺序存储结构,利用完全二叉树中双亲节点和孩子结点之间的内在关系,在当前无序区中选择关键字最大(最小)...
  • 堆排序是不稳定的排序方法,辅助空间为O(1), 最坏时间复杂度为O(nlog2n),堆排序的堆序的平均性能较接近于最坏性能。 1. 若array[0,...,n-1]表示一颗完全二叉树的顺序存储模式,双亲节点指针和孩子结点指针...
  • 我们先研究一下几种常见算法...堆排序利用堆的特性对记录序列进行排序的一种排序方法。即小根堆:父结点的值小于左右孩子结点的值,大顶堆相反假设我们要排序的序列是{50,10,90,30,70,40,80,60,20}堆排序分为两...
  • Java实现堆排序

    2019-11-12 00:00:06
    堆排序基础是最大二叉堆; 实现方法: ... import java.util.Arrays; /** * 堆排序 ... * 利用二叉堆堆基础实现 ... * (最大堆)下沉:根节点跟左右节点最大比较,如果小于最大节点进行下沉; * ...
  • 数据结构之堆排序

    2018-04-23 16:33:05
    堆是什么? 堆是具有下列性质的完全二叉树:每个结点的值都大于或等于其左右孩子结点的值,称为大顶堆;...堆排序(Heap Sort)就是利用堆进行排序的方法。 基本思想 将待排序的序列构造成...
  •  归并排序利用归并思想实现的排序方法,该算法采用经典分治策略(分治法将问题分(divide)成一些小问题然后递归求解,而治(conquer)阶段将分阶段得到各答案&quot;修补&quot;在一起,即...
  • 数据结构-堆排序

    2016-12-09 15:44:39
    下面讨论利用堆进行排序的方法。可以分两种情况分别讨论: ① 如果初始序列是堆,可通过反复执行如下操作而最终得到一个有序序列: 输出根:即将根(第一个元素)与当前子序列中的最后一个元素交换。 调整堆:...
  • 堆排序是一种树形选择排序方法,它的特点是:在排序的过程中,将array[0,...,n-1]看成是一颗完全二叉树的顺序存储结构,利用完全二叉树中双亲节点和孩子结点之间的内在关系,在当前无序区中选择关键字最大(最小)...
  • 选择排序之堆排序

    2011-02-14 01:50:00
    双亲结点为Ri,其左孩子和右孩子分别为R2i,R(2i+1),利用这一点关系,通过构造堆的方法排序。 假设我们要输出从小到大的排列,那么可以构造大根,即寻找的最大元素,上浮到根节点(还有就是保证双亲...
  • 堆排序利用堆进行排序的方法。假设进行升序排序,它的基本思想是,将待排序的序列构造成一个大顶堆,这是一个建堆的过程。此时,整个序列的最大值就是堆顶的根结点。将它与堆数组的末尾元素交换,此时末尾元素...
  • 快速排序和堆排序

    2014-10-31 22:30:17
    快速排序是利用了partition( )进行排序的。partition( )有两种实现形式,(1)利用两个指针一个头指针,一个尾指针,通过交换头尾指针所指的数进行排序; (2)一前一后两个指针同时从左往右进行遍历,如果前指针...
  • 什么是堆? 堆是一棵完全二叉树 最小堆 设堆中任意结点C,其父节点为P,如果结点值P<...堆排序利用堆来进行排序的一种排序算法。 什么是堆排序堆排序利用堆这种数据结构及操作来实现的一种排序方法
  • 1.简单选择排序:指一种排序算法,在简单选择排序过程中,所需移动记录次数比较少。最好情况下,即待排序记录初始状态就已经是正序排列了,不需要移动记录。...2.堆排序:是指利用堆这种数据结构所设计一...
  • 我们循环遍历每个数组的元素,然后利用堆的add方法,最终把一个数组实现成最大堆的形式。然后我们开始循环遍历最大堆,每次都使用最大堆的取出最大元素的方法,不断的放入传入的数组里。循环结束后,我们的数组是...

空空如也

空空如也

1 2 3 4 5 ... 10
收藏数 193
精华内容 77
关键字:

则利用堆排序的方法