七大排序

七大排序

public class SevenSort {public static void main(String[] args) {int[] arr = new int[] {1,5,3,2,4,10,7,9,8,30,25,26,21,15};heapSort(arr);System.out.println(Arrays.toString(arr));}// 传入任意整形数组arr，对其进行原地堆排序public static void heapSort(int[] arr) {// 1.heapifyfor (int i = (arr.length - 1 - 1) / 2; i >= 0; i--) {siftDown(arr,i,arr.length);}// 2.不断交换堆顶元素和数组的最后一个位置for (int i = arr.length - 1; i > 0; i--) {swap(arr,0,i);// 交换之后，最大值已经放在了最终的位置siftDown(arr,0,i);}}//在arr数组的索引为k的位置进行siftDown操作//size有效元素的个数，size的位置是下一个元素插入的位置//此时length 相当于sizeprivate static void siftDown(int[] arr, int k, int length) {// 还存在左子树while (2 * k + 1 < length) {int j = 2 * k + 1;if (j + 1 < length && arr[j + 1] > arr[j]) {j = j + 1;}// j就保存了此时左右子树的最大值if (arr[k] >= arr[j]) {break;}else {swap(arr,k,j);k = j;}}}private static void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}
}