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);
}
}
评论
填写昵称与邮箱即可评论，无需登录。