public static void radixsort(int[] a){
int max=a[0];
for(int i=1;i<a.length;i++){
if (max<a[i]) {
max=a[i];
}
}
int time=0;
while(max>0){
max/=10;
time++;
}
java.util.List<ArrayList> queue=new ArrayList<ArrayList>();
for(int i=0;i<10;i++){
ArrayList<Integer> queue1=new ArrayList<>();
queue.add(queue1);
}
for(int i=0;i<time;i++){
for(int j=0;j<a.length;j++){
int x=a[j]%(int)Math.pow(10, i+1)/(int)Math.pow(10, i);
queue.get(x).add(a[j]);
}
int tmp=0;
for(int j=0;j<10;j++){
while(!queue.get(j).isEmpty()){
a[tmp++]=(int)queue.get(j).remove(0);
}
}
} for (int i = 0; i < a.length; i++) {
System.out.println("radixsort" + a[i]);
}
} public static void mergesort(int[] a) {
sort(a, 0, a.length-1);
for (int i = 0; i < a.length; i++) {
System.out.println("mergesort" + a[i]);
}
} public static void merging(int[] a, int left, int middle, int right) {
if (middle < left || middle > right) {
return;
}
int[] tmpArray = new int[a.length];
int tmp = left;
int tmpIndex = left;
int begin1 = left;
int begin2 = middle+1;
while (begin1 <= middle && begin2 <= right) {
if (a[begin1] < a[begin2]) {
tmpArray[tmp++] = a[begin1++];
} else {
tmpArray[tmp++] = a[begin2++];
}
}
while (begin1 <= middle) {
tmpArray[tmp++] = a[begin1++];
}
while (begin2 <= right) {
tmpArray[tmp++] = a[begin2++];
}
while(tmpIndex<=right){
a[tmpIndex]=tmpArray[tmpIndex++];
}
} public static void sort(int[] a, int left, int right) {
if (left < right) {
int middle = (right - left) / 2 + left;
sort(a, left, middle);
sort(a, middle + 1, right);
merging(a, left, middle, right);
}
} public static void quicksort(int[] a) {
System.out.println("quicksort");
quick(a, 0, a.length - 1);
for (int i = 0; i < a.length; i++) {
System.out.println("quicksort" + a[i]);
}
} public static void quick(int[] a, int left, int right) {
if (left < right) {
int middle = getMiddle(a, left, right);
quick(a, left, middle);
quick(a, middle + 1, right);
}
} public static int getMiddle(int[] a, int left, int right) {
int tmp = a[left];
while (left < right) {
while (a[right] >= tmp && right > left) {
right--;
}
a[left] = a[right];
while (a[left] <= tmp && left < right) {
left++;
}
a[right] = a[left];
}
a[left] = tmp;
return left;
} public static void bubblesort(int[] a) {
for (int i = 0; i < a.length; i++) {
for (int j = 0; j < a.length - i - 1; j++) {
if (a[j] > a[j + 1]) {
swap(a, j, j + 1);
}
}
}
for (int i = 0; i < a.length; i++) {
System.out.println("bubblesort" + a[i]);
}
} public static void heapsort(int[] a) {
for (int i = a.length - 1; i >= 0; i--) {
buildmaxheap(a, i);
swap(a, i, 0); }
for (int i = 0; i < a.length; i++) {
System.out.println("heapsort" + a[i]);
}
} public static void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
} public static void buildmaxheap(int[] a, int lastindex) {
int length = a.length;
if (lastindex >= length) {
return;
}
int index = (lastindex - 1) / 2;
for (; index >= 0; index--) {
int left = index * 2 + 1;
if (left <= lastindex) {
if (a[index] < a[left]) {
swap(a, index, left);
}
}
if (left < lastindex && a[index] < a[left + 1]) {
swap(a, index, left + 1);
}
}
} public static void selectsort(int[] a) {
int pos = 0;
for (int i = 0; i < a.length; i++) {
pos = i;
for (int j = i + 1; j < a.length; j++) {
if (a[pos] > a[j]) {
pos = j;
}
}
if (pos != i) {
int temp = a[i];
a[i] = a[pos];
a[pos] = temp;
}
}
for (int i = 0; i < a.length; i++) {
System.out.println("shellsort" + a[i]);
}
} public static void shellsort(int[] a) {
int length = a.length;
System.out.println(length);
for (int d = (int) Math.ceil(length / 2); d > 0; d /= 2) {
for (int i = 0; i < d; i++) {
System.out.println("i=" + i + " d=" + d);
for (int j = i + d; j < length; j += d) {
int temp = a[j];
int k = j - d;
System.out.println("j=" + j + " temp=" + temp + " k=" + k);
for (; k >= 0 && temp < a[k]; k -= d) {
System.out.println("k+d=" + (k + d) + " k=" + k + " a[k+d]=" + a[k + d] + " a[k]=" + a[k]);
a[k + d] = a[k];
}
System.out.println("end" + "k+d=" + (k + d) + " a[k+d]=" + a[k + d] + " temp=" + temp);
a[k + d] = temp;
}
}
}
for (int i = 0; i < a.length; i++) {
System.out.println("shellsort" + a[i]);
}
} public static void selectSort(int[] a) {
int length = a.length;
int position = 0;
for (int i = 0; i < length - 1; i++) {
int temp = a[i];
int j = i + 1;
position = i;
for (; j < length; j++) {
if (a[j] < temp) {
temp = a[j];
position = j;
}
}
a[position] = a[i];
a[i] = temp;
}
for (int i = 0; i < a.length; i++) {
System.out.println("selectSort" + a[i]);
}
} public static void insertSort(int[] a) {
int temp = 0;
for (int i = 1; i < a.length; i++) {
int j = i - 1;
temp = a[j + 1];
for (; j >= 0 && a[j] > temp; j--) {
System.out.println(j);
a[j + 1] = a[j];
}
System.out.println(j);
a[j + 1] = temp;
}
for (int i = 0; i < a.length; i++) {
System.out.println(a[i]);
}
}
}