一、堆排序

       堆排序的核心是把数组看作一个完全二叉树，通过入堆操作把整个二叉树整理一遍，使所有的父节点都比其子节点大，如此根节点a（即数组的第一位）就是最大的数。把根节点a与二叉树最后一位z调换，称为a的出堆，即a已经排序完成。再处理被换上去的z，由于所有的父节点都比子节点大，只要把根节点下面子节点较大的那一位换到根节点，而根节点上的z就重复的进行处理沉下去，直到沉到底。重复出堆的操作，就可以得到升序排列的数组。整个操作的时间复杂度为O(Nlog(N))，空间复杂度为O（1）。

1.入堆：

从根节点开始，判断其与父节点的大小关系，如果比父节点大，就与父节点交换，交换完成后继续与新的父节点作比较。而根节点没有父节点就不进行操作。

2.出堆：

将根节点与二叉树最后一片叶交换，并且二叉树的节点减一，即原先的根节点已经排序完成，退出比较。再把新的根节点通过与子节点比较交换一路沉下去。需要注意的是由于排好序的节点已经退出比较，所以要注意更新子节点是否存在，否则会把已经排序完成的数唤醒。

规律：画出一个完全二叉树并且标号（根节点标号为1）会发现任何一个父节点K的子节点为2k和2k+1，有这样的位置关系容易比较。

3.代码部分：

#include<stdio.h> #include<stdlib.h> #define N 21 void enheap(int *a,int n); void outheap(int *a,int n,int count); void heap_sort(int *a,int n) { int i=0,temp=0,j=0; for(i=1;i<=n;i++) //将数组内按照堆排序的入堆操作从前往后推，使所有的父节点都比其子节点大，如此则根节点最大。一次操作复杂度为O(log(n)) enheap(a,i); for(i=n;i>=1;i--) { temp=a[1]; a[1]=a[i]; a[i]=temp; //把根节点（即最大的数）和数组后面未排序的数交换 outheap(a,1,i-1); //交换完成后i节点已经完成排序，不再进入比较序列，传入参数变为i-1 } return; } void enheap(int *a,int n) { int temp=0,index=0; if(n/2<1 || a[n/2]>a[n]) //若该节点是根节点或者比父节点小则不作任何操作 return; if(a[n]>a[n/2]) //该节点比父节点大，则与父节点交换并继续往上比较 { temp=a[n]; a[n]=a[n/2]; a[n/2]=temp; enheap(a,n/2); } return; } void outheap(int *a,int n,int count) //count数记录目前排序未完成的个数，若超出此数则说明触碰了已排序完成的数 { int temp,index=0; if(2*n>count) //n节点下面的已经比较过或者超出了数组范围 return; if(2*n+1>count || a[2*n]>=a[2*n+1]) // n节点下只有左节点或左节点不比右节点小，则n节点和其左节点比较 index=2*n; else //n节点下右节点比左节点大 index=2*n+1; if(a[n]<=a[index]) //若n节点不比子节点大，则交换后继续比较 { temp=a[n]; a[n]=a[index]; a[index]=temp; outheap(a,index,count); //在这里count是不变的，因为一次比较还没有完成 } return; } int main(void) { int i=0; int a[N+1]={0}; for(i=1;i<=N;i++) a[i]=rand()%N; /*for(i=1;i<N;i++) printf("%d\n",a[i]);*/ heap_sort(a,N); for(i=1;i<=N;i++) printf("%d\n",a[i]); return 0; }

二、归并排序：

归并排序和快速排序在将排序数组递归划分成两段上有一点点像，但快速排序是根据一个关键数将数据分成两段，递归过程中是先处理大的数据再划分处理小的数据量。而归并排序是将所有的数据先不断递归划分，直到一个数字单元，再处理该段数据，然后返回，处理的数据量是从小到大的。而且归并排序需要一个额外的空间。但是快速排序在最坏情况下时间复杂度会退化到O（n*n），归并不会存在这个问题。 1.原理： 将所有的数据递归划分成两段，直到单个数据不可分。然后再把两两相邻的数组合并。合并完之后得到的数组再次合并，直到整个数组合并。 2.代码部分： #include <stdio.h> #include <stdlib.h> #include <string.h> #define N 1000000 int temp[N]; void merge(int *a,int *b,int n,int m) //将两个数组合并到temp数组中 { int i=0,j=0,count=0; while(i<n && j<m) //两段数组都未比较完毕 { if(a[i]<b[j]) temp[count++]=a[i++]; else temp[count++]=b[j++]; } if(i>=n) //如果a数组先被处理完就把b数组剩下的所有的数放入temp数组中 while(j<m) temp[count++]=b[j++]; else //b数组先处理完 while(i<n) temp[count++]=a[i++]; return; } void merg_sort(int *a,int n) { if(n<=1) //若已经不可再分则不处理 return; if(n>2) //若还可再分，就先处理小的 { merg_sort(a,n/2); merg_sort(a+n/2,n-n/2); } merge(a,a+n/2,n/2,n-n/2); //此处第一次处理的话就是两个单个数合并 memcpy(a,temp,n*sizeof(int)); return; } int main(void) //测试代码 { int a[N]={0}; int i=0; for(i=0;i<N;i++) { a[i]=rand()%N; //printf("%d ",a[i]); } puts(""); merg_sort(a,N); for(i=0;i<N;i++) printf("%d\n",a[i]); return 0; }