赞
踩
堆排序的基本原理为将待排序序列构造成一个大根堆,此时,整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换,此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个大根堆,重复上述操作,最终序列为有序。
备注:大根堆是每个结点的值都大于或等于其左右孩子结点的值;小根堆是每个结点的值都小于或等于其左右孩子结点的值。
如图所示:
而实际上堆的存储形式是一维数组。
例如:25、15、88、45、8、1、33、21、55、6
如图所示:
具体步骤:
说明:最开始 i 为最后一个结点的位置,依据树的性质,推算该结点的双亲结点,我们将之标记为 s。接下来比较双亲结点和叶子结点,并进行交换,然后找到下一个双亲结点,重复上述操作,直到最后达到根节点,比较交换完成后,此时大根堆或小根堆便建立完成。(下面我们按照从小到大进行排序,因此我们建立大根堆)
(1)第一次排序:
(2)第二次排序:
以此类推,可得最后一次排序情况为:
此时排为大根堆,接下来只需要将根节点和最后一个节点交换值,然后对根节点进行一次排序即可.
如图所示:此时排为大根堆,接下来只需要将根节点和最后一个节点交换值,然后对根节点进行一次排序即可.
如图所示:
- void Adjust (int *arr,int start,int end)
- {
- int temp = arr[start];
- for(int i = 2*start +1;i<= end;i = 2*i+1) //i是左孩子下标
- {
- //判断是否有右孩子
- if(i < end && arr[i] < arr[i+1]) //说明有右孩子,左孩子小于右孩子
- {
- i++;
- }
- if(arr[i] > temp)
- {
- arr[start] = arr[i];
- start = i;
- }
- else
- {
- break;
- }
- }
- arr[start] = temp;
- }
- void Heap_Sort(int *arr,int len)
- {
- int i = 0;
- for(i = (len-1-1)/2;i >= 0;i--)
- {
- Adjust(arr,i,len-1);
- }
- //此时已经是大根堆
- for(i = 0;i < len-1;i++)
- {
- int temp = arr[0];
- arr[0] = arr[len-1-i];
- arr[len-1-i] = temp;
- Adjust(arr,0,len-1-i-1);
- }
- }
备注:
父====>>子
若父为n,则其右孩子为2n+1;左孩子为2n+2。
子====>>父
若子为n,则其父为(n-1)/2;
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。