-
堆排序
对于非递归的堆排序主要有两个步骤:
(一)构建大/小根堆
(二)对于构建好的堆,每次取第一个元素(也就是最大或者最小的那个元素)和最后一个元素交换,并把它移除堆的结构,这样,就必须重新维护剩下的树,使它重新变成一个大/小根堆,重复这个步骤,直到堆中的元素为0。
-
代码
public class HeapSort { public static void buildHeap(int[] a, int i, int n) { int leftChild = i * 2 + 1; int rightChild = i * 2 + 2; int largest = i; /** * 循环找出父节点和左右节点中最大的值, * 并将最大值节点交换为父节点 */ while (leftChild < n) { if (a[leftChild] > a[i]) { largest = leftChild; } if (rightChild < n && a[rightChild] > a[largest]) { largest = rightChild; } if (largest != i) { swap(a, largest, i); } else { break; } i = largest; leftChild = i * 2 + 1; rightChild = i * 2 + 2; } } public static void swap(int[] a, int i, int j) { int tmp = a[i]; a[i] = a[j]; a[j] = tmp; } public static void main(String[] args) { int[] a = new int[]{1,23,234,234,22,1,-1,0,3}; for (int i = a.length/2 -1; i >= 0; i--) { // 构建堆,因为a.length/2后面的数据都不会有左右节点了 buildHeap(a, i, a.length); } System.out.println("开始排序前,构建的大根堆:"); for (int i : a) { System.out.print(i + " "); } System.out.println(); // 开始不断的交换,移除,构建堆 for (int i = a.length - 1; i >=0; i--) { swap(a, 0, i); // 每次都把堆中第一个数和最后一个数交换 buildHeap(a, 0, i); // 第二个参数是i,就相当于是把i(最后一个数)移除堆,剩下的重新构建堆 System.out.println("第" + (a.length - i) + "次排序后的数组:"); for (int j : a) { System.out.print(j + " "); } System.out.println(); } } }
-
结果
从结果可以看出每次排序都是把最大值和堆的最后一位进行交换,然后,又重新构建堆。对于大根堆,用来从小到大排序,对于小根堆用来从大到小的排序