首页 > 代码库 > 白话经典算法二叉堆排序之思想简介

白话经典算法二叉堆排序之思想简介

2024-07-07 05:43:01   222人阅读

常用的排序算法有冒泡排序，插入排序和选择排序。他们的时间复杂度是o(n2)，与数据量的平方成正比。他们的效率还是比较低的。现在来说说他们的效率为什么比较低下。以冒泡排序为例，它每一轮都是与相邻的元素进行交换，交换的距离为1，每次每个(没有冒泡出来的)元素都要与前一个比较再交换。每次相邻的比较只能比较出两个元素的大小，不能以整个数组进行参照来确定在整个数组里的大小，也就是说每次的比较不能确定其他元素的相对位置，因而每次比较的贡献不大，所以这样的比较是笨拙的，进而需要完全比较O(n2)次才能得出正确的结果。
    为了得到比较高的效率，我们对排序算法进行改进。怎么改进呢？改进的关键在于不要和相邻的元素比较，也就是加大比较的距离。我们想象一下，我们同学照毕业照时是怎么排序的，按照个高的高矮，我们绝对不只是比较左右同学的高矮，我们是先比较前后的高矮，然后再左右微调。您看，比较的距离肯定远远大于1（前后同学在数组里的索引差是该行的大小），这样就能快速的排序。为了达到这个目的，我们模拟一下这个过程，先把要比较的数组按照这个顺序来排列：第一个排一个数据，第二排2个数据，第三个4个数据.....以此类推，举例说明：
    假设要比较的数组是：int a[] = {5, 3, 7, 9, 1, 4, 2, 8, 6}， 那么排列的顺序是：（前后两个数据之前用线连接）
因为拍照时，个高的肯定要站在后排，所以我们排序的规则是后排的两个元素要比前排的那个元素大，如果前排的元素大于后排的那个，
那么就将前排的那个元素和后排中最小的那个元素交换。
比方说最后一排的两个学生和他们前排的那个学生，即，9要比8和6大，
那么就将9与8、6中较小者（也就是6）互换位置，变成了。
我们对每一个这样的三人组进行这样的调整，也就是这三人组。
按照什么样的顺序来分别调整这三人组呢？由于后排的数字大于前排的数字，我们按从下到上从右至左的顺序，也就是数字原始排列的反顺序。所以依次调整
的结构，注意上一次的调整会影响下一次的结果。进过调整将会变成下面的顺序：

我们注意观察，发现如果只是对这四个三人组依次调整还是不能得到我们想要的效果，因为不符合我们的要求。所以我们还需要调整。调整成下面这个样子就得到了我们的要求：

 综上，我们排列的规则是：首先给数组中的数字按照第一排1个，第二排2个，第三排4个。。。的顺序排好队，然后从底至上，从右至左的顺序调整三人组的顺序，调整的规则是如果前排的元素大于了后排一个元素，则将前排的元素与后排较小的那个元素交换位置。每调整一次后，再审视一下它后面的元素是否也准守这个规则，没有准守，则继续调整直到整个排列达到这个要求。
    那么得到这个排列之后，数组里面的元素也不是按照升序后者降序排列啊，没有达到我们将数组排序的效果啊。不急，我们再看这个排列有什么特点。嘿嘿，不难发现，每个三人组的领头也就是前排那个元素是三人组中最小的，而且第一个元素是整个元素中最小的。如果我们将第一个元素和最好一个元素交换位置，得到下面那个顺序：

那么这样会打破我们的排列规则。怎么办呢？现在我们将最后一个元素从数组中拿掉，然后再根据我们的规则重新排列数据，也就是把下面的排列重新排列：

 按照我们的排列规则，我们将很容易调整成下面那个正确的排列：（两人组也是按照三人组的规则，将会发现更简单，因为只需比较一个元素了）

 怎么样？接下来的步骤您肯定知道啦。重复上面的步骤即可将得到一个全新的数组，不过数组中的元素是降序排列的。
不过，这又不是问题，只要调整我们的排序规则即可，即前排的元素大于后排的元素，然后执行我们的排序步骤即可以得到升序排列的数组。
好了，经过上面的介绍，您应该理解了我们排序的规则，它就是大名鼎鼎的堆排序的过程和思想。
呵呵，要将堆排序给您讲清楚可花费了我不少精力，先歇一会，下篇再介绍具体的程序实现。


联系
我们