c++9中排序算法解释及代码(2)

8. 希尔排序

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

int A[200005]; int main(){

int n,i,j,k,step,tmp; scanf(\,&n); for(i=0;i

for(step=n/2;step>0;step/=2){//增量 for(i=step;itmp){ A[k+step]=A[k]; k-=step; } A[k+step]=tmp; } } }

for(i=0;i

}

不稳定的排序算法，复杂度存在争议，下限是O(nlogn)，平均O(n^1.5)

9. 堆排序

堆得定义：

一个长度为n的数组A，下标1,2,3,….,n-2,n-1,n。

如果对于在[1,n/2]范围内的i，有A[i]<=A[i*2]且A[i]<=A[i*2+1]，则称为小顶堆。 如果对于在[1,n/2]范围内的i，有A[i]>=A[i*2]且A[i]>=A[i*2+1]，则称为大顶堆。

如果要将数组从小到大排序，则需要维护小顶堆。每次取出堆顶元素，再删除，一直维护小顶堆。

向下调整过程，可以用一个down()函数来完成。 void swap(int &a,int &b){//交换两个数 int t=a;a=b;b=t; }

void down(int k){ while(2*k<=sz){ int a=2*k; if(a+1<=sz&&heap[a]>heap[a+1])a++;//找较小的儿子 if(heap[k]>heap[a])swap(heap[k],heap[a]);//交换 else break; }

}

k=a;//往下走

初始化堆得时候，可以把n/2到1的每个元素都down下。

int heap[200005],sz;//sz记录当前堆得大小，也是最后一个元素的下标 int main(){ int i,j,k,n; scanf(\ sz=n; for(i=1;i<=n;i++) scanf(\ for(i=n/2;i>=1;i--) down(i);//初始化堆 for(i=1;i<=n;i++){ printf(\ }

heap[1]=heap[sz--];//用最后一个元素覆盖堆顶，在删除最后一个元素 down(1);//调整堆 }

return 0;

堆也可以添加元素，原理down类似，用up，把数字添加在heap[++sz]的位置上。 如果父亲节点比当前元素小，就不断向上。 void up(int k){ while(k>1){ int a=k/2;//a是父亲节点 if(heap[a]>heap[k])swap(heap[k],heap[a]); else break; k=a; } }

每次向上和向下都是logn，通过堆实现排序，复杂度是O(nlogn)，不稳定，“1 2 2”可以说明，删除1后，第二个2被赋值到堆顶，下次出来。

因此堆可以添加元素，并维护最大值，删除最大值，在很多贪心问题上，可以用到。