数据结构之堆排序（升序和降序）

关于堆这种数据结构，可以观看这篇文章【数据结构之堆】，要是不了解的话。

1 升序排序

升序排序使用最大堆，降序排序排序使用最小堆，并不是说只能这样用，只是这种设计会比较简洁。 这里以升序排序为例，每次需要将当前堆调整为最大堆，然后将堆顶元素（数组第0个元素）和最后一个元素（第size-1个元素）进行交换。然后对前面的（n-1）个元素调整成最大堆， 但是需要注意：此时，堆相当于删除了对顶元素，然后最后一个元素换到堆顶的位置，此时需要重新调整，但是堆的大小也减小了1。所以，此时调整的应该是n-1个元素的堆。

public class HeapSort { private int[] a; public HeapSort(int[] a) { this.a = a; } public void increaseSort(){ int n = this.a.length; for (int i = (int)(n-2)/2; i >=0 ; i--) { downAdjust(i,n);//第一次调整，大小是数据的长度 } for (int i = n-1; i >0; i--) { int t = this.a[i]; this.a[i] = this.a[0]; this.a[0]=t; downAdjust(0,i);//此时，堆的大小发生了改变，大小变成了i } } private void downAdjust(int pIndex,int n){ int childIndex = 2*pIndex+1; int tem = this.a[pIndex]; while (childIndex < n){ //当有右子树且右子树的值大于左子树的值，则定位到右子树，让大的数参与比较 if (childIndex + 1 < n && this.a[childIndex+1] > this.a[childIndex]) childIndex++; //如果父节点的值大于子节点的值 则不用交换 if (tem > this.a[childIndex]) break; this.a[pIndex] = this.a[childIndex]; pIndex = childIndex; childIndex = 2 * childIndex + 1; } this.a[pIndex] = tem; } }

2 降序排序

降序排序的思路和升序一致，使用最小堆，每次讲堆顶元素（第0号元素）和最后一个元素（第size-1号元素）进行交换，此时，最小的数已经放到数组的最后面了，然后继续调整堆，将第二小的数放到倒数第二的位置，然后是第三…

public class HeapSort { private int[] a; public HeapSort(int[] a) { this.a = a; } public void decreaseSort(){ int n = this.a.length; for (int i = (int)(n-2)/2; i >-1 ; i--) { downAdjust2(i,n); } for (int i = n-1; i >0; i--) { int t = this.a[i]; this.a[i] = this.a[0]; this.a[0]=t; downAdjust2(0,i); } } private void downAdjust2(int pIndex,int n){ int childIndex = 2*pIndex+1; int tem = this.a[pIndex]; while (childIndex < n){ if (childIndex + 1 < n && this.a[childIndex+1] < this.a[childIndex]) childIndex++; if (tem < this.a[childIndex]) break; this.a[pIndex] = this.a[childIndex]; pIndex = childIndex; childIndex = 2 * childIndex + 1; } this.a[pIndex] = tem; } }

3 总代码

import java.util.Arrays; public class HeapSort { private int[] a; public HeapSort(int[] a) { this.a = a; } public void decreaseSort(){ int n = this.a.length; for (int i = (int)(n-2)/2; i >-1 ; i--) { downAdjust2(i,n); } for (int i = n-1; i >0; i--) { int t = this.a[i]; this.a[i] = this.a[0]; this.a[0]=t; downAdjust2(0,i); } } public void increaseSort(){ int n = this.a.length; for (int i = (int)(n-2)/2; i >=0 ; i--) { downAdjust(i,n); } for (int i = n-1; i >0; i--) { int t = this.a[i]; this.a[i] = this.a[0]; this.a[0]=t; downAdjust(0,i); } } private void downAdjust(int pIndex,int n){ int childIndex = 2*pIndex+1; int tem = this.a[pIndex]; while (childIndex < n){ //当有右子树且右子树的值大于左子树的值，则定位到右子树，让大的数参与比较 if (childIndex + 1 < n && this.a[childIndex+1] > this.a[childIndex]) childIndex++; if (tem > this.a[childIndex]) break; this.a[pIndex] = this.a[childIndex]; pIndex = childIndex; childIndex = 2 * childIndex + 1; } this.a[pIndex] = tem; } private void downAdjust2(int pIndex,int n){ int childIndex = 2*pIndex+1; int tem = this.a[pIndex]; while (childIndex < n){ if (childIndex + 1 < n && this.a[childIndex+1] < this.a[childIndex]) childIndex++; if (tem < this.a[childIndex]) break; this.a[pIndex] = this.a[childIndex]; pIndex = childIndex; childIndex = 2 * childIndex + 1; } this.a[pIndex] = tem; } public static void main(String[] args) { int[]a ={4,13,8,9,10,18,16,1}; System.out.println("原数组："+Arrays.toString(a)); HeapSort heapSort = new HeapSort(a); heapSort.decreaseSort(); System.out.println("降序排序："+Arrays.toString(a)); heapSort.increaseSort(); System.out.println("升序排序："+Arrays.toString(a)); } }

4 时间复杂度分析

堆排序需要进行两次循环，一次是交换堆顶元素和堆中最后一个位置的算法，需要执行n次，此循环的时间复杂度是O(n)。每次交换完之后，就需要对新的堆进行调整，由于堆是一颗完全二叉树，所以，调整堆的时间复杂度为O(logn)。 所以堆排序的时间复杂度为O(nlogn)。且是一种稳定的排序。