汽配公司的网站要怎么做/西安百度竞价托管

常用的排序算法属快速排序和堆排序应用的最多，快速排序的递归版本要受限制于栈空间溢出问题的困扰，无法处理大量数据排序（但是对于外存上的数据进行排序，什么排序算法猜算是适合的？也许mergeSort会是一种选择，但是这个要再考虑）。而其他的排序包括插入排序，归并排序，冒泡排序，选择排序，相较于这两种排序算法，或者在时间或者空间上消耗要更大。

HeapSort算法是一个就地的排序算法，时间复杂度和quickSort一样，为O(N*LogN)，同时和快速排序一样，是不稳定的排序（貌似ShellSort，QuickSort，HeapSort这三种最高效的排序都是不稳定的，但是InsertSort，BubbleSort是稳定的）。并且在实现上，除了在保持堆结构的过程当中需要使用递归（由于是和深度有关的，所以递归的次数很少，而且应该是可以做尾递归优化的，是不是？），要了解堆排序首先要了解堆得定义。

Heap在计算机领域有两个主要的解释：

1.Heap是一种数据结构，在逻辑上为一颗完全二叉树，在物理上表现为一个数组。

2.Heap是一个程序执行空间当中的可动态申请的内存区域。

在堆排序当中，我们当然是选择第一种解释，堆的性质主要表现在如下的两个方面（以最大堆为例）：

1.堆的任何一个节点的都要大于它的后裔

2.堆是一颗完全二叉树

 

如果把堆看成一种数据结构，那么对于定义抽象数据类型来说，堆的常用操作包括：

1.HeapIdf():保持堆得性质

2.BuildHeap():建立初始堆

3.Insert():插入新的元素进入堆

4.Update()：更新堆元素的key并保持堆结构

5.get():获取堆顶部的元素

6.delete():删除堆顶部的元素并保持堆结构

 

但是对HeapSort来说，只有1,3是用到的，具体的HeapSort算法，我用C实现的版本如下：

#include <stdio.h>
#include "heapsort.h"//data:heap data
///size: the size of the heap
//i: the node neeeded to be adjustedint parent(int i){return (i-1)/2;
}int left(int i){return (i*2+1);
}int right(int i){return (i*2+2);    
}void maxHeapIdf(int data[],int size,int i){int largerId;int temp;int l,r;l=left(i);r=right(i);largerId=i;if(l<size && data[largerId]<data[l]){largerId=l;}if(r<size && data[largerId]<data[r]){largerId=r;}if(largerId!=i){temp=data[i];data[i]=data[largerId];data[largerId]=temp;maxHeapIdf(data,size,largerId);}
}void buildMaxHeap(int data[],int size){int i;for(i=(size-2)/2;i>=0;i--){maxHeapIdf(data,size,i);}}void heapSort(int data[],int size){int i;int temp;buildMaxHeap(data,size);for(i=size-1;i>=0;i--){temp=data[i];data[i]=data[0];data[0]=temp;maxHeapIdf(data,i,0);}
}void print(int A[],int heap_size)
{int i;for(i = 0; i < heap_size;i++){printf("%d ", A[i]);}printf("\n");
}int main(){int data[]={5,2,3,7,6,4,1};heapSort(data,7);print(data,7);
}

 

Heap结构除了可以应用到排序上，还是作为优先级队列的一种选择，优先级队里可以用于比如进程调度等场合。