java实现堆排序

堆排序原理

堆排序是利用二叉树来进行算法的排序，堆的特点是父结点数据大于或等于它的左右两个孩子结点的数据，例如数组{3,1,8,4,5,7,6,2}共有八个数，我们把它当做二叉树来看就是 如下图所示：

我们从倒数第一个节点4开始，如果节点的左右子叶最大的数大于节点的话我们就把它与节点进行交换，否则就继续向上一个节点开始遍历，看是否符合节点大于两个叶子，不符合就进行交换，如1和5交换，3和8交换，一波交换之后虽然调节到了根节点，但图中交换下来的“3”使得这个序列仍不满足堆的特点，需继续往下进行交换，所以7和3交换。这就成功的构建了一个堆。 这时候我们就进行大顶堆进行升序排序，它的过程是：你可以自己在纸上画一下，我们把根节点“8”和最后一个结点“2”交换。对除去“2”的其他结点，重新进行排序，交换后，以“2”为根，对数据重新进行调整。由于最大值“8”已经调整到数组末尾，则被调整的子序列不包括该结点。然后此时需要把“7”和“2”交换。交换“7”和“2”后，以“2”为根节点继续调整，此时需要交换“6”和“2”。交换“6”和“2”后，以“2”为根，继续进行调整。此时交换“5”和“1”，步骤和前面相同，不在啰嗦了。每次调整，根节点为最大值，使该值和子序列最后一个值交换，当子序列只有一个元素时，排序结束。

代码实现

static void fun1(int a[],int root,int n) { int j; int t; int c; int temp; j=2*root+1; t=a[root]; c=0; while(j<=n&&c==0) { if(j<n) if(a[j]<a[j+1]) j++; if(a[j/2-1+j%2]>=a[j]) c=1; else { temp=0; temp=a[j/2-1+j%2]; a[j/2-1+j%2]=a[j]; a[j]=temp; j=j*2+1; } } } static void fun(int a[],int n) { int i; int temp; for(i=(n/2);i>=0;i--) fun1(a,i,n); for(i=n-1;i>=0;i--) { temp=0; temp=a[i+1]; a[i+1]=a[0]; a[0]=temp; fun1(a,0,i); } for(i=0;i<=n;i++) { System.out.print(a[i]+" "); } System.out.println(); } public static void main(String[] args) { int[] a=new int[]{3,1,8,4,5,7,6,2}; fun(a,7); }

代码解释

我的代码和上面的原理差不多，只是一些数组下标的处理方面有点不是那么巧妙，我的数组下标是从0开始的，所以有些不同，还有就是交换函数，java交换函数写的有点复杂，因为java没有指针，所以我就直接在里面实现了交换，看起来有点不是那么美观。还有就是后面我会继续更新算法的，有问题的希望大家指正一下，谢谢！