How to realize heap sort, quick sort and merge sort of Java
In this article Xiaobian for you to introduce in detail "Java heap sort, quick sort, merge sort how to achieve", detailed content, clear steps, details handled properly, hope that this "Java heap sort, fast sort, merge sort how to achieve" article can help you solve doubts, following the editor's ideas slowly in-depth, together to learn new knowledge.
Heap sort
Time complexity: 0 (N*log (N))
Space complexity: 0 (1)
Stability: instability
Private static void heapSort (int [] arr) {/ / build crearHeap (arr); for (int I = 0; I
< arr.length-1; i++) { int heapSize=arr.length-i; swap(arr,heapSize-1,0); heapSize--; shiftDown(arr,heapSize,0); } System.out.println(Arrays.toString(arr)); } private static void crearHeap(int[] arr) { // 从后往前遍历(右边非叶子节点开始), 依次进行向下调整 for (int i = (arr.length-1-1)/2; i >= 0; iMel -) {shiftDown (arr,arr.length,i);}} / / adjust downwards to form a large pile of private static void shiftDown (int [] arr, int size, int I) {int parent = I; int child= parent*2+1; while (child arr [child]) {child=child+1 } if (arr [child] > arr [parent]) {swap (arr,child,parent);} else {break;} parent=child; child=parent*2+1 }} / / Exchange private static void swap (int [] arr, int child, int parent) {int tmp = arr [child]; arr [child] = arr [parent]; arr [parent] = tmp;} Quick sort
Time complexity: O (N ^ logN) the worst O (N ^ 2) is closely related to the benchmark value.
Space complexity: 0 (logN) at worst O (N)
Stability: instability
Recursive private static void quick (int [] arr) {quickSortHelper (arr,0,arr.length-1); System.out.println (Arrays.toString (arr));} private static void quickSortHelper (int [] arr, int left, int right) {if (left > = right) {/ / interval has only one element, or zero element return } int index = partition (arr,left,right); quickSortHelper (arr,left,index-1); quickSortHelper (arr,index+1,right);} private static int partition (int [] arr, int left, int right) {int iCompleft; int jigsaw; int baseValue=arr [right]; while (I
