Code\_01\_InsertionSort package basic\_class\_01; import java.util.Arrays; public class Code\_01\_InsertionSort { publicstatic void insertionSort(int arr) { if(arr == null || arr.length < 2) { return; } for(int i = 1; i < arr.length; i++) { for(int j = i - 1; j >= 0 && arr > arr; j--) { swap(arr,j, j + 1); } } } publicstatic void swap(int arr, int i, int j) { arr= arr ^ arr; arr= arr ^ arr; arr= arr ^ arr; } // fortest publicstatic void comparator(int arr) { Arrays.sort(arr); } // fortest publicstatic int generateRandomArray(int maxSize, int maxValue) { intarr = new int; for(int i = 0; i < arr.length; i++) { arr= (int) ((maxValue + 1) \* Math.random()) - (int) (maxValue \* Math.random()); } returnarr; } // for test publicstatic int copyArray(int arr) { if(arr == null) { returnnull; } intres = new int; for(int i = 0; i < arr.length; i++) { res= arr; } returnres; } // fortest publicstatic boolean isEqual(int arr1, int arr2) { if((arr1 == null && arr2 != null) || (arr1 != null && arr2 ==null)) { returnfalse; } if(arr1 == null && arr2 == null) { returntrue; } if(arr1.length != arr2.length) { returnfalse; } for(int i = 0; i < arr1.length; i++) { if(arr1 != arr2) { returnfalse; } } returntrue; } // fortest publicstatic void printArray(int arr) { if(arr == null) { return; } for(int i = 0; i < arr.length; i++) { System.out.print(arr+ " "); } System.out.println(); } // fortest publicstatic void main(String args) { inttestTime = 500000; intmaxSize = 100; intmaxValue = 100; booleansucceed = true; for(int i = 0; i < testTime; i++) { intarr1 = generateRandomArray(maxSize, maxValue); intarr2 = copyArray(arr1); insertionSort(arr1); comparator(arr2); if(!isEqual(arr1, arr2)) { succeed= false; break; } } System.out.println(succeed? "Nice!" : "Fucking fucked!"); intarr = generateRandomArray(maxSize, maxValue); printArray(arr); insertionSort(arr); printArray(arr); } } Code\_02\_SelectionSort package basic\_class\_01; import java.util.Arrays; public class Code\_02\_SelectionSort { publicstatic void selectionSort(int arr) { if(arr == null || arr.length < 2) { return; } for(int i = 0; i < arr.length - 1; i++) { intminIndex = i; for(int j = i + 1; j < arr.length; j++) { minIndex= arr < arr ? j : minIndex; } swap(arr,i, minIndex); } } publicstatic void swap(int arr, int i, int j) { inttmp = arr; arr= arr; arr= tmp; } // fortest publicstatic void comparator(int arr) { Arrays.sort(arr); } // fortest publicstatic int generateRandomArray(int maxSize, int maxValue) { intarr = new int; for(int i = 0; i < arr.length; i++) { arr= (int) ((maxValue + 1) \* Math.random()) - (int) (maxValue \* Math.random()); } returnarr; } // fortest publicstatic int copyArray(int arr) { if(arr == null) { returnnull; } intres = new int; for(int i = 0; i < arr.length; i++) { res= arr; } returnres; } // fortest publicstatic boolean isEqual(int arr1, int arr2) { if((arr1 == null && arr2 != null) || (arr1 != null && arr2 ==null)) { returnfalse; } if(arr1 == null && arr2 == null) { returntrue; } if(arr1.length != arr2.length) { returnfalse; } for(int i = 0; i < arr1.length; i++) { if(arr1 != arr2) { returnfalse; } } returntrue; } // fortest publicstatic void printArray(int arr) { if(arr == null) { return; } for(int i = 0; i < arr.length; i++) { System.out.print(arr+ " "); } System.out.println(); } // fortest publicstatic void main(String args) { inttestTime = 500000; intmaxSize = 100; intmaxValue = 100; booleansucceed = true; for(int i = 0; i < testTime; i++) { intarr1 = generateRandomArray(maxSize, maxValue); intarr2 = copyArray(arr1); selectionSort(arr1); comparator(arr2); if(!isEqual(arr1, arr2)) { succeed= false; printArray(arr1); printArray(arr2); break; } } System.out.println(succeed? "Nice!" : "Fucking fucked!"); intarr = generateRandomArray(maxSize, maxValue); printArray(arr); selectionSort(arr); printArray(arr); } } Code\_03\_HeapSort package basic\_class\_01; import java.util.Arrays; public class Code\_03\_HeapSort { publicstatic void heapSort(int arr) { if(arr == null || arr.length < 2) { return; } for(int i = 0; i < arr.length; i++) { heapInsert(arr,i); } intsize = arr.length; swap(arr,0, --size); while(size > 0) { heapify(arr, 0, size); swap(arr,0, --size); } } publicstatic void heapInsert(int arr, int index) { while(arr > arr) { swap(arr,index, (index - 1) / 2); index= (index - 1) / 2; } } publicstatic void heapify(int arr, int index, int size) { intleft = index \* 2 + 1; while(left < size) { intlargest = left + 1 < size && arr > arr ? left + 1: left; largest= arr > arr ? largest : index; if(largest == index) { break; } swap(arr,largest, index); index= largest; left= index \* 2 + 1; } } publicstatic void swap(int arr, int i, int j) { inttmp = arr; arr= arr; arr= tmp; } // fortest publicstatic void comparator(int arr) { Arrays.sort(arr); } // fortest publicstatic int generateRandomArray(int maxSize, int maxValue) { intarr = new int; for(int i = 0; i < arr.length; i++) { arr= (int) ((maxValue + 1) \* Math.random()) - (int) (maxValue \* Math.random()); } returnarr; } // fortest publicstatic int copyArray(int arr) { if(arr == null) { returnnull; } intres = new int; for(int i = 0; i < arr.length; i++) { res= arr; } returnres; } // fortest publicstatic boolean isEqual(int arr1, int arr2) { if((arr1 == null && arr2 != null) || (arr1 != null && arr2 ==null)) { returnfalse; } if(arr1 == null && arr2 == null) { return true; } if(arr1.length != arr2.length) { returnfalse; } for(int i = 0; i < arr1.length; i++) { if(arr1 != arr2) { returnfalse; } } returntrue; } // fortest publicstatic void printArray(int arr) { if (arr== null) { return; } for(int i = 0; i < arr.length; i++) { System.out.print(arr+ " "); } System.out.println(); } // fortest publicstatic void main(String args) { inttestTime = 500000; intmaxSize = 100; intmaxValue = 100; booleansucceed = true; for(int i = 0; i < testTime; i++) { intarr1 = generateRandomArray(maxSize, maxValue); intarr2 = copyArray(arr1); heapSort(arr1); comparator(arr2); if(!isEqual(arr1, arr2)) { succeed= false; break; } } System.out.println(succeed? "Nice!" : "Fucking fucked!"); intarr = generateRandomArray(maxSize, maxValue); printArray(arr); heapSort(arr); printArray(arr); } } Code\_04\_QuickSort package basic\_class\_01; import java.util.Arrays; public class Code\_04\_QuickSort { publicstatic void quickSort(int arr) { if(arr == null || arr.length < 2) { return; } quickSort(arr,0, arr.length - 1); } publicstatic void quickSort(int arr, int l, int r) { if (l arr) { swap(arr,--more, l); }else { l++; } } swap(arr,more, r); returnnew int { less + 1, more }; } publicstatic void swap(int arr, int i, int j) { inttmp = arr; arr= arr; arr= tmp; } // fortest publicstatic void comparator(int arr) { Arrays.sort(arr); } // fortest publicstatic int generateRandomArray(int maxSize, int maxValue) { intarr = new int; for(int i = 0; i < arr.length; i++) { arr= (int) ((maxValue + 1) \* Math.random()) - (int) (maxValue \* Math.random()); } returnarr; } // fortest publicstatic int copyArray(int arr) { if(arr == null) { returnnull; } intres = new int; for(int i = 0; i < arr.length; i++) { res= arr; } returnres; } // fortest publicstatic boolean isEqual(int arr1, int arr2) { if((arr1 == null && arr2 != null) || (arr1 != null && arr2 ==null)) { returnfalse; } if(arr1 == null && arr2 == null) { returntrue; } if(arr1.length != arr2.length) { returnfalse; } for(int i = 0; i < arr1.length; i++) { if(arr1 != arr2) { returnfalse; } } returntrue; } // fortest publicstatic void printArray(int arr) { if(arr == null) { return; } for(int i = 0; i < arr.length; i++) { System.out.print(arr+ " "); } System.out.println(); } // fortest publicstatic void main(String args) { inttestTime = 500000; intmaxSize = 100; intmaxValue = 100; booleansucceed = true; for(int i = 0; i < testTime; i++) { intarr1 = generateRandomArray(maxSize, maxValue); intarr2 = copyArray(arr1); quickSort(arr1); comparator(arr2); if(!isEqual(arr1, arr2)) { succeed= false; printArray(arr1); printArray(arr2); break; } } System.out.println(succeed? "Nice!" : "Fucking fucked!"); intarr = generateRandomArray(maxSize, maxValue); printArray(arr); quickSort(arr); printArray(arr); } } Code\_05\_MergeSort package basic\_class\_01; import java.util.Arrays; public class Code\_05\_MergeSort { publicstatic void mergeSort(int arr) { if(arr == null || arr.length < 2) { return; } mergeSort(arr,0, arr.length - 1); } publicstatic void mergeSort(int arr, int l, int r) { if (l== r) { return; } intmid = l + ((r - l) >> 1); mergeSort(arr,l, mid); mergeSort(arr,mid + 1, r); merge(arr,l, mid, r); } publicstatic void merge(int arr, int l, int m, int r) { inthelp = new int; int i= 0; int p1= l; int p2= m + 1; while(p1 <= m && p2 <= r) { help= arr < arr ? arr : arr; } while(p1 <= m) { help= arr; } while(p2 <= r) { help= arr; } for (i= 0; i < help.length; i++) { arr = help; } } // fortest public staticvoid comparator(int arr) { Arrays.sort(arr); } // fortest publicstatic int generateRandomArray(int maxSize, int maxValue) { intarr = new int; for(int i = 0; i < arr.length; i++) { arr= (int) ((maxValue + 1) \* Math.random()) - (int) (maxValue \* Math.random()); } returnarr; } // fortest publicstatic int copyArray(int arr) { if(arr == null) { returnnull; } intres = new int; for(int i = 0; i < arr.length; i++) { res= arr; } returnres; } // fortest publicstatic boolean isEqual(int arr1, int arr2) { if((arr1 == null && arr2 != null) || (arr1 != null && arr2 ==null)) { returnfalse; } if(arr1 == null && arr2 == null) { returntrue; } if(arr1.length != arr2.length) { returnfalse; } for(int i = 0; i < arr1.length; i++) { if(arr1 != arr2) { returnfalse; } } returntrue; } // fortest publicstatic void printArray(int arr) { if(arr == null) { return; } for(int i = 0; i < arr.length; i++) { System.out.print(arr+ " "); } System.out.println(); } // fortest publicstatic void main(String args) { inttestTime = 500000; intmaxSize = 100; int maxValue= 100; booleansucceed = true; for(int i = 0; i < testTime; i++) { intarr1 = generateRandomArray(maxSize, maxValue); intarr2 = copyArray(arr1); mergeSort(arr1); comparator(arr2); if(!isEqual(arr1, arr2)) { succeed= false; printArray(arr1); printArray(arr2); break; } } System.out.println(succeed? "Nice!" : "Fucking fucked!"); intarr = generateRandomArray(maxSize, maxValue); printArray(arr); mergeSort(arr); printArray(arr); } } Code\_06\_BucketSort package basic\_class\_01; import java.util.Arrays; public class Code\_06\_BucketSort { // onlyfor 0~200 value publicstatic void bucketSort(int arr) { if(arr == null || arr.length < 2) { return; } intmax = Integer.MIN\_VALUE; for(int i = 0; i < arr.length; i++) { max= Math.max(max, arr); } intbucket = new int; for(int i = 0; i < arr.length; i++) { bucket\]++; } int i= 0; for(int j = 0; j < bucket.length; j++) { while (bucket-- > 0) { arr= j; } } } // fortest publicstatic void comparator(int arr) { Arrays.sort(arr); } // fortest publicstatic int generateRandomArray(int maxSize, int maxValue) { intarr = new int; for(int i = 0; i < arr.length; i++) { arr= (int) ((maxValue + 1) \* Math.random()); } returnarr; } // fortest publicstatic int copyArray(int arr) { if(arr == null) { returnnull; } intres = new int; for(int i = 0; i < arr.length; i++) { res= arr; } returnres; } // fortest publicstatic boolean isEqual(int arr1, int arr2) { if((arr1 == null && arr2 != null) || (arr1 != null && arr2 ==null)) { returnfalse; } if(arr1 == null && arr2 == null) { returntrue; } if(arr1.length != arr2.length) { returnfalse; } for(int i = 0; i < arr1.length; i++) { if(arr1 != arr2) { returnfalse; } } returntrue; } // for test publicstatic void printArray(int arr) { if(arr == null) { return; } for(int i = 0; i < arr.length; i++) { System.out.print(arr+ " "); } System.out.println(); } // fortest publicstatic void main(String args) { int testTime= 500000; intmaxSize = 100; intmaxValue = 150; booleansucceed = true; for(int i = 0; i < testTime; i++) { intarr1 = generateRandomArray(maxSize, maxValue); intarr2 = copyArray(arr1); bucketSort(arr1); comparator(arr2); if(!isEqual(arr1, arr2)) { succeed= false; printArray(arr1); printArray(arr2); break; } } System.out.println(succeed? "Nice!" : "Fucking fucked!"); intarr = generateRandomArray(maxSize, maxValue); printArray(arr); bucketSort(arr); printArray(arr); } } Code\_07\_RadixSort package basic\_class\_01; import java.util.Arrays; public class Code\_07\_RadixSort { // onlyfor no-negative value publicstatic void radixSort(int arr) { if(arr == null || arr.length < 2) { return; } radixSort(arr,0, arr.length - 1, maxbits(arr)); } publicstatic int maxbits(int arr) { intmax = Integer.MIN\_VALUE; for(int i = 0; i < arr.length; i++) { max= Math.max(max, arr); } intres = 0; while(max != 0) { res++; max/= 10; } returnres; } publicstatic void radixSort(int arr, int begin, int end, int digit) { finalint radix = 10; int i= 0, j = 0; intcount = new int; intbucket = new int; for(int d = 1; d <= digit; d++) { for(i = 0; i < radix; i++) { count= 0; } for(i = begin; i <= end; i++) { j= getDigit(arr, d); count++; } for(i = 1; i < radix; i++) { count= count + count; } for(i = end; i >= begin; i--) { j= getDigit(arr, d); bucket- 1\] = arr; count--; } for(i = begin, j = 0; i <= end; i++, j++) { arr= bucket; } } } publicstatic int getDigit(int x, int d) { return((x / ((int) Math.pow(10, d - 1))) % 10); } // fortest publicstatic void comparator(int arr) { Arrays.sort(arr); } // fortest publicstatic int generateRandomArray(int maxSize, int maxValue) { intarr = new int; for(int i = 0; i < arr.length; i++) { arr= (int) ((maxValue + 1) \* Math.random()); } returnarr; } // fortest publicstatic int copyArray(int arr) { if(arr == null) { returnnull; } intres = new int; for(int i = 0; i < arr.length; i++) { res= arr; } returnres; } // fortest publicstatic boolean isEqual(int arr1, int arr2) { if((arr1 == null && arr2 != null) || (arr1 != null && arr2 ==null)) { returnfalse; } if(arr1 == null && arr2 == null) { returntrue; } if(arr1.length != arr2.length) { returnfalse; } for(int i = 0; i < arr1.length; i++) { if(arr1 != arr2) { returnfalse; } } returntrue; } // fortest publicstatic void printArray(int arr) { if(arr == null) { return; } for(int i = 0; i < arr.length; i++) { System.out.print(arr+ " "); } System.out.println(); } // fortest publicstatic void main(String args) { inttestTime = 500000; intmaxSize = 100; intmaxValue = 100000; booleansucceed = true; for(int i = 0; i < testTime; i++) { intarr1 = generateRandomArray(maxSize, maxValue); intarr2 = copyArray(arr1); radixSort(arr1); comparator(arr2); if(!isEqual(arr1, arr2)) { succeed= false; printArray(arr1); printArray(arr2); break; } } System.out.println(succeed? "Nice!" : "Fucking fucked!"); intarr = generateRandomArray(maxSize, maxValue); printArray(arr); radixSort(arr); printArray(arr); } }

【基础部分】java编写排序算法总结整理