SortingJun26
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154
class Main {
public static void bubblesort(int[] array1){
if (array1 ==null){
return;
}
// O(n°2=
for (int index1 = 0; index1 < array1.length; index1++){
for (int index2= index1+1; index2 < array1.length; index2++){
if (array1[index1]< array1[index2]){
int tmp = array1[index1];
array1[index1] = array1[index2];
array1[index2] = tmp;
}
if (array1[index1]> array1[index2]){
int tmp = array1[index1];
array1[index1] = array1[index2];
array1[index2] = tmp;
}
}
}
}
public static int[] mergeSort(int array[]){
if (array.length == 1){
return array;
}
// 0 1 2 3 4 5 6 7 8 9
// 5
// 0 1 2 3 4 5 6 7 8
//
int leftSize = 0;
int rightSize = 0;
if ( array.length % 2 == 0 ){
leftSize= array.length /2;
rightSize= array.length /2;
} else {
leftSize= array.length /2+1;
rightSize= array.length /2;
}
System.out.println("length:"+array.length+" leftSize:"+ leftSize+" rightSize:"+rightSize);
int left[] = new int[leftSize];
int right[] = new int[rightSize];
fill(left, array, 0);
fill(right, array, rightSize);
printAll(left);
printAll(right);
return merge(mergeSort(left), mergeSort(right));
}
public static void fill(int []emptyArray, int[] sourceArray, int start){
for (int i=0; i < emptyArray.length; i++){
emptyArray[i]= sourceArray[start+i];
}
}
public static int[] merge(int left[], int right[]){
int mergedArray[] = new int[left.length+right.length];
int leftIndex=0, rightIndex=0, mergedIndex=0;
while (leftIndex < left.length && rightIndex < right.length){
if (left[leftIndex] <= right[rightIndex]){
mergedArray[mergedIndex++] = left[leftIndex++];
} else if (left[leftIndex] >= right[rightIndex]){
mergedArray[mergedIndex++] = right[rightIndex++];
}
}
while (left.length > leftIndex){
mergedArray[mergedIndex++] = left[leftIndex++];
}
while (right.length > rightIndex){
mergedArray[mergedIndex++] = right[rightIndex++];
}
return mergedArray;
}
// array 8 9 7 6 5 4 3 2 1 0
// index = 0 1
// index2 = 1 2
// smallestIndex = 0
public static void selectionSort(int [] unsortedArray){
if (unsortedArray == null || unsortedArray.length == 1){
System.out.println("");
}
int smallestNumberIndex=0;
for (int index=0; index < unsortedArray.length; index ++){
for (int index2=index+1; index2 < unsortedArray.length; index2 ++){
if (unsortedArray[index2] < unsortedArray[smallestNumberIndex]){
smallestNumberIndex = index2;
}
}
swap (unsortedArray, index, smallestNumberIndex);
smallestNumberIndex= index+1;
}
}
public static void insertionSort(int[] halfSortedArray){
for (int currentIndex=1; currentIndex < halfSortedArray.length; currentIndex ++){
int lastSorted =currentIndex;
while (lastSorted > 0 && halfSortedArray[lastSorted] < halfSortedArray[lastSorted-1]){
swap(halfSortedArray, lastSorted, lastSorted-1);
lastSorted--;
}
}
}
public static void swap(int[] array, int currentIndex, int smallestNumberIndex){
int tmp= array[currentIndex];
array[currentIndex] = array[smallestNumberIndex];
array[smallestNumberIndex] = tmp;
}
public static void printAll(int array[]){
System.out.println(" ");
for (int i=0; i < array.length; i++){
System.out.print(array[i]+ " ");
}
}
public static void main(String[] args) {
int array[] = new int[10];
array[0] = 9;
array[1] = 8;
array[2] = 7;
array[3] = 6;
array[4] = 5;
array[5] = 4;
array[6] = 3;
array[7] = 2;
array[8] = 1;
array[9] = 0;
mergeSort(array);
printAll(array);
}
}
Java
INFO