Bubble sort and heap sort

1. Heap sort is nlogN level sort:

 public static void heapSort(int[] arr){//1. First perform heapify on arr and adjust it to the maximum heap//Start the shiftDown operation from the last non-leaf nodefor (int i = (arr.length -1 -1)>>1; i >= 0; i--) {shiftDown(arr, i, arr.length);}//At this time, arr is adjusted to the maximum heapfor (int i = arr.length -1; i >0 ; i--) {//arr[0] is the top element of the heap, which is the maximum value of the current heapswap(arr,0,i);shiftDown(arr,0,i);}}// element sink operationprivate static void shiftDown(int[] arr, int i, int length) {while(2* i +1 arr[j]){j = j+1;}//j is the maximum value of the left and right subtreesif(arr[i] >arr[j]){// end of sinkingbreak;}else{swap(arr,i,j);i = j;}}}private static void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}public static void main(String[] args) {int[] arr = {7,5,4,3,1,2,10,9,8};heapSort(arr);System.out.println(Arrays.toString(arr));}

2. Bubble sort o(n^2)

 public static void bubbleSort(int[] arr){for (int i = 0; i arr[j +1]){swap(arr,j,j+1);isSwaped = true;}}if(!isSwaped){break;//It has been completely ordered}}

Heap and priority queue:

1. Maximum heap, minimum heap implementation

2. Heap sort

3.TopK problem

17.14 -- 343--373