我要招人

去企业版

首页 > 试题广场 >

将整数数组（7-6-3-5-4-1-2）按照堆排序的方式原地

[单选题]

将整数数组（7-6-3-5-4-1-2）按照堆排序的方式原地进行升序排列，请问在第一轮排序结束之后，数组的顺序是_____。

```
2-6-3-5-4-1-7
```
```
6-2-3-5-4-1-7
```
```
6-5-3-2-4-1-7
```
```
1-5-3-2-4-6-7
```
```
5-4-3-2-1-6-7
```
```
5-1-3-2-4-6-7
```

查看答案及解析

牛客7309617号

可以看堆排序的源代码，主要是理解“一轮排序”具体做了，不仅仅交换，还要调整堆。

发表于 2017-07-19 08:51:58 回复(1)

╰微笑感染嘴角的苦涩

选C，堆顶元素与堆底元素交换后，前面的序列还需要构成最大堆

发表于 2015-08-27 16:48:09 回复(1)

林乔夕

原数组已经是一个大顶堆，可直接开始排序。
（大顶堆：每个节点的值都不小于自己两个左右子节的完全二叉树）
每轮输出堆顶元素后，以堆中最后一个元素代替之（由于此题要求原地排序，即不产生额外的空间，堆顶元素与最后一个元素交换）。再将新的顶点元素不断与其子节点中大于该元素的较大者交换，直到该元素大于其左右两个子节点，或成为叶子节点。此时将剩余元素调整成一个新的大顶推。
           7                      2                      6                     6
          / \                    / \              / \                 / \
        6     3     ==>    6     3    ==>    2     3    ==>     5    3
       / \    / \              / \    /             / \    /          / \    /
   5 4 1   2          5 4 1 7      5 4 1    7     2 4 1    7

由此得出，第一轮结束后的顺序是：6,5,3,2,4,1,7。

发表于 2016-06-24 11:41:19 回复(8)

姜太公

问题是“一轮排序”都做了什么：

肯定是先构建堆，再把堆顶和最后的元素交换；

如果交换后再一次构建堆，那就已经进入“第二轮排序”的步骤了吧

发表于 2015-08-29 09:29:37 回复(5)

seekerjie

n 1 2 3 4 5 6 7

7 6 3 5 4 1 2

2 6 3 5 4 1 7

6 2 3 5 4 1 7

6 5 3 2 4 1 7

构建最大堆的过程如上所示：

1.先把堆顶元素和末尾数交换

2.然后对前面的数进行最大堆调整

发表于 2015-08-28 15:44:12 回复(6)

小崔冲冲冲

这个题目显而易见选C，没有任何疑惑

利用堆排序升序排列，通过以下步骤；

1.构建一次最大堆，将堆顶与末尾数交换，这样最大的数就到达了末尾；

2.除了末尾的元素以外，对前面的数经行最大堆调整，再次取得最大堆，将堆顶交换到倒数第二个位置

...

最终按照此方式排序

按照此顺序继续，每次堆元素都会减少一个，其实是最大的元素被交换到尾端。

这样，第1步后就可以得到答案C

发表于 2015-08-28 09:42:47 回复(1)

hhjudbi

第一轮排序结束为将大顶堆根元素与最后叶子结点交换以后，还要再构建一次大顶堆后，该结果即为答案

发表于 2017-10-12 19:49:12 回复(1)

vector<>

交换完之后，记得还要调整堆

发表于 2020-03-20 09:02:57 回复(0)

牛客532247378号

不是说升序排列吗？不应该是用小根堆，然后选出最小的吗

发表于 2024-10-17 16:48:21 回复(0)

窝在小角落里刷题

升序要构建大根堆

发表于 2022-06-28 23:01:16 回复(0)

孟迪

什么叫做原地进行升序排列。如果想要升序排列不是先要建立小顶堆么不懂不懂

发表于 2020-10-18 19:51:41 回复(0)

健康成长玛卡巴卡

感觉这题真的坑。原地堆排序的话按理就不用建堆，直接用这个数组堆排序，一轮比较后把7调到最后。一轮结束。

发表于 2020-07-22 12:36:26 回复(0)

猪客

虽然我选了A 但是让我回顾了以前的知识看了以前写的笔记马上懂了赞

public class 堆排序 {
    /**
     * 第一步:
     *       先建立大根堆(每一个父节点都比左右子节点大)->(根节点最大)
     *       从最后一个非叶子节点开始
     * 第二部:
     *      把最后一个叶子节点交换
     *第三部:
     *      写一个方法,用来从上到下重新排列子树
     */
    public static void main(String[] args) {
        int[] nums = {1,2,3,4,5};//待排序的数组
        sort(nums);
        System.out.println(Arrays.toString(nums));
    }

    private static void sort(int[] arr){
        int lengh = arr.length;
        /**
         * 第一步:建立大根堆
         */
        for (int i = lengh/2-1; i >= 0; i--) {
            //进入建立大根堆方法
            bigRootHeap(arr,i,lengh);
        }
        System.out.println(Arrays.toString(arr));

        for (int i = lengh-1; i > 0 ; i--) {
            swap(arr,0,i);//将堆顶元素与末尾元素进行交换
            bigRootHeap(arr,0,i);//重新对堆进行调整
        }
    }
    private static void bigRootHeap(int[] arr,int k,int lengh) {
        //取出根节点的值              //关键步骤:当交换了位置后,继续调整子节点所在子树
        int temp = arr[k];

        for (int i = 2*k+1; i < lengh; i=2*i+1) {
            //求该节点与其左右子树谁大,k就指向谁
            if (i+1<lengh && arr[i+1]>arr[i]){
                i++;
            }
            if (temp<arr[i]){
                arr[k] = arr[i];
                k=i;
            }else {
                break;
            }
        }
        arr[k] = temp;
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

发表于 2019-10-05 19:22:19 回复(0)

牛客2817416号

所有答案都在讨论一轮排序,这么说吧,

[1,2,4,3]===>一次冒泡排序后为[1,2,3,4]

所以一轮排序的意思就是一趟排序,我们这一趟要产生一个最大元素.就像冒泡排序一样，一趟排序后产生一个最大元素。那么既然要产生最大元素，堆自然而然就是建好的。这儿如果题目是（7-6-3-5-4-1-2）按照堆排序的方式原地进行降序排列，我们先自己建堆，调整堆为最小堆，然后再将堆顶与最后个元素交换，然后调整堆，结果就是答案。

发表于 2019-08-30 13:12:49 回复(0)