排序篇:heap
程序员文章站
2022-04-17 09:01:45
...
public static void heapSort() { int[] arr = {0, 5, 6, 333, 5, 8, 999, 7, 7, 5, 45, 3}; int heapSize = arr.length - 1;//堆的大小, buildHeap(arr, heapSize);//建堆,递归调用maxHeapify System.out.println(Arrays.toString(arr)); for (int i = arr.length - 1; i > 0; i--) { // 堆从index=1开始建立,方便操作 swap(arr, 1, i); //每一次把第一个元素(最大)放到堆的最后一个节点,所以每一次堆的大小减一 heapSize--; maxHeapify(arr, 1, heapSize); } System.out.println(Arrays.toString(arr)); } private static void maxHeapify(int[] arr, int index, int heapSize) { int leftIndex = index << 1; int rightIndex = leftIndex + 1; int largestIndex = index; if (leftIndex <= heapSize && arr[leftIndex] > arr[index]) { largestIndex = leftIndex; } if (rightIndex <= heapSize && arr[rightIndex] > arr[largestIndex]) { largestIndex = rightIndex; } if (largestIndex != index) { swap(arr, index, largestIndex); maxHeapify(arr, largestIndex, heapSize); } } private static void buildHeap(int[] arr, int heapSize) { //(arr.length/2)从非叶子节点处开始遍历 for (int i = arr.length / 2; i > 0; i--) { maxHeapify(arr, i, heapSize); } } public static void swap(int arr[], int j, int i) { int tmp = arr[j]; arr[j] = arr[i]; arr[i] = tmp; }
上一篇: 运维面试题小总结