算法基础(二) 堆
1 普通堆排序
public class TestHeap<T extends Comparable> {private T[] data; private int capacity; private int count; public TestHeap(int capacity) {this.capacity = capacity 1; data = (T[]) new Comparable[this.capacity]; } public void insert(T t) {if (count >= capacity) {return; } data[ count] = t; shiftUp(count); } private void swap(int i, int j) {T t = data[i]; data[i] = data[j]; data[j] = t; } public void shiftUp(int k) {while (k >= 2 && data[k].compareTo(data[k / 2]) > 0) {swap(k, k / 2); k /= 2; } } private T popMax() {T t = data[1]; swap(1, count--); shiftDown(1); return t; } private void shiftDown(int k) {while (2 * k <= count) {int j = 2 * k; if (j 1 <= count && data[j].compareTo(data[j 1]) < 0) {j ; } if (data[j].compareTo(data[k]) < 0) {break; } swap(j, k); k = j; } } public void printArray() {SortTestUtils.printArray(data); }}
测试用例:一个一个pop的方式实现堆排序
public static void main(String[] args) {int n = 100; Integer[] arr = SortTestUtils.generateRandomArray(n, 0, 1000); SortTestUtils.printArray(arr); TestHeap<Integer> testHeap = new TestHeap<>(n); for (int i = 0; i < n; i ) {testHeap.insert(arr[i]); } System.out.println("一个一个pop的方式实现堆排序 =================="); for (int i = 0; i < n; i ) {Integer integer = testHeap.popMax(); arr[i] = integer; } SortTestUtils.printArray(arr); SortTestUtils.isSorted(arr);}
2 通过数组构造堆排序
public TestHeap(T[] arr) { int n = arr.length; data = (T[]) new Comparable[n 1]; count = n; //1 将arr中的元素copy到data中 for (int i = 0; i < n; i ) { data[i 1] = arr[i]; } //2 把每个非叶子节点的值向下shiftdown for (int i = n / 2; i >= 1; i--) { shiftDown(i); }}
测试用例:以构造函数方式构建堆排序
System.out.println("以构造函数方式构建堆排序 =================="); Integer[] arr2 = SortTestUtils.generateRandomArray(n, 0, 1000); TestHeap<Integer> testHeap2 = new TestHeap(arr2); for (int i = 0; i < n; i ) { Integer integer = testHeap2.popMax(); arr2[i] = integer; } SortTestUtils.printArray(arr2); SortTestUtils.isSorted(arr2);
3 原地堆排序
public static void sort(Comparable[] arr) {int n = arr.length; //构建最大堆 第一个非叶子节点向下遍历 for (int i = (n - 1 - 1) / 2; i >= 0; i--) {shiftDown2(arr, n, i); } //将最大堆排序 将第一个值(最大值)放到最后 型号才能有序 for (int i = n - 1; i > 0; i--) {swap(arr, i, 0); shiftDown2(arr, i, 0); } } private static void shiftDown2(Comparable[] arr, int n, int i) {Comparable e = arr[i]; while (2 * i 1 < n) {int j = 2 * i 1; if (j 1 < n && arr[j].compareTo(arr[j 1]) < 0) {j ; } arr[i] = arr[j]; i = j; } arr[i] = e; } private static void swap(Comparable[] arr, int i, int j) {Comparable t = arr[i]; arr[i] = arr[j]; arr[j] = t; }
测试用例: 原地堆排序
System.out.println("原地堆排序 ==================");Integer[] arr3 = SortTestUtils.generateRandomArray(n, 0, 1000); sort(arr3);SortTestUtils.printArray(arr3);SortTestUtils.isSorted(arr2);
赞 (0)