Je suis un nouvel ingénieur diplômé d'avril. C'est le premier message de Qiita.
Comme le titre l'indique, les algorithmes de recherche / tri de base Je l'ai écrit en Java. Je l'ai publié sur Blog avant, mais je l'ai posté en 4 parties. Je vais le mettre en place dans Qiita. L'algorithme de recherche / tri mis en œuvre cette fois est le suivant.
Montant moyen du calcul: O $ (n) $
public class linearSearch {
public static int execute(int[] data, int target){
int notFound = -1;
for(int i = 0; i < data.length; i++){
if(data[i] == target){
return i;
}
}
return notFound;
}
public static void main(String[] args){
int[] data = {1, 2, 3, 4, 5};
int result;
result = linearSearch.execute(data, 3);
if(result != -1) {
System.out.println("Found: index key = " + result);
}
else{
System.out.println("Not found.");
}
}
}
Montant moyen du calcul: $ O (\ log_2 {n}) $
public class binarySearch {
public static boolean execute(int[] data, int target) {
int low = 0;
int high = data.length - 1;
while (low <= high) {
int middle = (low + high) >>> 1;
if (data[middle] == target) {
return true;
} else if (data[middle] < target) {
low = middle + 1;
} else {
high = middle - 1;
}
}
return false;
}
public static void main(String[] args) {
int[] data = {23, 25, 53, 444, 5466, 12646};
boolean result;
result = binarySearch.execute(data, 25);
if (result){
System.out.println("Found!");
}
else {
System.out.println("Not Found.");
}
}
}
Montant moyen du calcul: $ O (n ^ 2) $
public class bubbleSort {
public static void sort(int[] array){
int temp;
for(int i = 0; i < array.length; i++){
for(int j = 0; j< array.length -i -1; j ++){
if(array[j] > array[j + 1]){
temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
}
}
public static void main(String[] args){
int[] test
= { 10, 75, 24, 32, 98,
72, 88, 43, 60, 35,
54, 62, 2, 12, 82,
};
bubbleSort.sort(test);
for( int i=0; i<test.length; i++ ) {
System.out.println( (i+1) + ":" + test[i] );
}
}
}
Montant moyen du calcul: $ O (n ^ 2) $
public class selectionSort {
public static void sort(int[] array){
for(int i = 0; i < array.length; i++ ){
int index = i;
for(int j = i + 1; j < array.length; j++){
if(array[j] < array[index]){
index = j;
}
}
if(i != index){
int tmp = array[index];
array[index] = array[i];
array[i] = tmp;
}
}
}
public static void main(String[] args){
int[] test
= { 10, 75, 24, 32, 98,
72, 88, 43, 60, 35,
54, 62, 2, 12, 82,
};
selectionSort.sort(test);
for( int i=0; i<test.length; i++ ) {
System.out.println( (i+1) + ":" + test[i] );
}
}
}
Montant moyen du calcul: $ O (n ^ 2) $
public class insertionSort {
public static void sort(int[] array){
for(int i = 1; i < array.length; i++){
int j = i;
while(j >= 1 && array[j-1] > array[j]){
int tmp = array[j];
array[j] = array[j - 1];
array[j-1] = tmp;
j --;
}
}
}
public static void main(String[] args){
int[] test
= { 10, 75, 24, 32, 98,
72, 88, 43, 60, 35,
54, 62, 2, 12, 82,
};
insertionSort.sort(test);
for( int i=0; i<test.length; i++ ) {
System.out.println( (i+1) + ":" + test[i] );
}
}
}
Montant moyen du calcul: O $ (n ^ 1,25) $
Le tri par insertion compare et échange les éléments adjacents, et le tri par shell compare / échange les éléments séparés par h. Le processus d'alignement de h éléments séparés est appelé tri-h. Le tri par insertion est utilisé pour la logique d'alignement du tri-h. En tri shell, en réduisant le nombre de h dans h-sort, le résultat final est un tri par insertion simple (h = 1). Au moment où il devient un tri d'insert, il est dans un état d'être "presque aligné", il est donc possible d'effectuer un alignement qui tire parti du tri d'insert.
public class shellSort {
public static void sort(int[] array){
int h = array.length / 2;
while(h > 0){
for(int i=h; i < array.length; i++){
int j = i;
while(j >= h && array[j - h] > array[j]){
int tmp = array[j];
array[j] = array[j-h];
array[j-h] = tmp;
j --;
}
}
h /= 2;
}
}
public static void main(String[] args){
int[] test
= { 10, 75, 24, 32, 98,
72, 88, 43, 60, 35,
54, 62, 2, 12, 82,
};
shellSort.sort(test);
for( int i=0; i<test.length; i++ ) {
System.out.println( (i+1) + ":" + test[i] );
}
}
}
Montant moyen du calcul: $ O (n \ log {n}) $
public class quickSort {
public static void sort(int[] array, int left, int right){
if(left <= right){
int p = array[(left + right) >>> 1];
int l = left;
int r = right;
while(l <= r){
while (array[l] < p){
l ++;
}
while (array[r] > p){
r --;
}
if (l <= r){
int tmp = array[l];
array[l] = array[r];
array[r] = tmp;
l++ ;
r-- ;
}
}
quickSort.sort(array, left, r);
quickSort.sort(array, l, right);
}
}
public static void main(String[] args){
int[] test
= { 10, 75, 24, 32, 98,
72, 88, 43, 60, 35,
54, 62, 2, 12, 82,
};
quickSort.sort(test, 0, test.length-1);
for( int i=0; i<test.length; i++ ) {
System.out.println( (i+1) + ":" + test[i] );
}
}
}
Montant moyen du calcul: $ O (n \ log {n}) $
public class mergeSort {
public static void sort(int[] array, int low, int high){
if(low < high){
int middle = (low + high) >>> 1;
mergeSort.sort(array, low , middle);
mergeSort.sort(array, middle+1, high);
mergeSort.merge(array, low, middle, high);
}
}
public static void merge(int[] array, int low, int middle, int high){
int[] helper = new int[array.length];
for (int i = low; i <= high; i++){
helper[i] = array[i];
}
int helperLeft = low;
int helperRight = middle + 1;
int current = low;
while (helperLeft <= middle && helperRight <= high){
if (helper[helperLeft] <= helper[helperRight]){
array[current] = helper[helperLeft];
helperLeft ++;
}
else {
array[current] = helper[helperRight];
helperRight ++;
}
current ++;
}
int remaining = middle - helperLeft;
for (int i = 0; i <= remaining; i++){
array[current + i] = helper[helperLeft + i];
}
}
public static void main(String[] args){
int[] test
= { 10, 75, 24, 32, 98,
72, 88, 43, 60, 35,
54, 62, 2, 12, 82,
};
mergeSort.sort(test, 0, test.length-1);
for( int i=0; i<test.length; i++ ) {
System.out.println( (i+1) + ":" + test[i] );
}
}
}
Montant moyen du calcul: $ O (n \ log {n}) $
public class heapSort {
public static void sort(int[] array) {
int n = array.length;
for (int i = n /2 -1; i>=0; i--){
heap(array, n, i);
}
for (int i = n-1 ; i>=0; i --){
if (array[0] > array[i]) {
int tmp = array[0];
array[0] = array[i];
array[i] = tmp;
heap(array, i-1, 0);
}
}
}
public static void heap(int[] array, int n , int root){
int largest = root;
int left = 2 * root + 1;
int right = 2 * root + 2;
if (left < n && array[left] > array[largest]){
largest = left;
}
if (right < n && array[right] > array[largest]){
largest = right;
}
if (largest != root){
int swap = array[root];
array[root] = array[largest];
array[largest] = swap;
heap(array, n ,largest);
}
}
public static void main(String[] args) {
int[] test
= {10, 75, 24, 32, 98,
72, 88, 43, 60, 35,
54, 62, 2, 12, 82,
};
heapSort.sort(test);
for (int i = 0; i < test.length; i++) {
System.out.println((i + 1) + ":" + test[i]);
}
}
}
Montant moyen du calcul: O $ (n + k) $
En principe, les données à trier sont un entier de 1 à 10.
public class bucketSort {
public static void sort(int[] array, int maxValue){
int[] bucket = new int[maxValue + 1];
for (int i = 0; i < bucket.length; i++){
bucket[i] = 0;
}
for (int i = 0; i < array.length; i++){
bucket[array[i]] ++;
}
int outPos = 0;
for (int i = 0; i < bucket.length; i++){
for (int j = 0; j < bucket[i]; j++){
array[outPos++] = i;
}
}
}
public static void main(String[] args) {
int[] test
= {10, 75, 24, 32, 98,
72, 88, 43, 60, 35,
54, 62, 2, 12, 82,
};
bucketSort.sort(test, 100);
for (int i = 0; i < test.length; i++) {
System.out.println((i + 1) + ":" + test[i]);
}
}
}
Montant moyen du calcul: O $ (nk) $
En principe, les données à trier sont un entier de 0 à 5. Soit le tableau A à trier {5,3,3,1,4}.
public class countingSort {
public static int[] sort(int[] array, int maxValue){
int[] counts = new int[maxValue + 1];
for (int i = 0; i < array.length; i ++){
counts[array[i]] ++;
}
int total = 0;
for (int i =0 ;i <= maxValue; i++){
int count = counts[i];
counts[i] = total;
total += count;
}
int[] sortedValues = new int[array.length];
for (int i = 0; i < array.length; i++){
sortedValues[counts[array[i]]] = array[i];
counts[array[i]] ++ ;
}
return sortedValues;
}
public static void main(String[] args) {
int[] test
= {10, 75, 24, 32, 98,
72, 88, 43, 60, 35,
54, 62, 2, 12, 82, 2, 12, 12
};
test = countingSort.sort(test, 100);
for (int i = 0; i < test.length; i++) {
System.out.println((i + 1) + ":" + test[i]);
}
}
}
Github
Code pour l'implémentation Java de cet algorithme de recherche et de tri Je l'ai résumé sur Github. Si vous avez des inquiétudes, faites-en la publicité (j'étudie car je suis susceptible d'utiliser Java en formation).
https://github.com/takaaki82/algorithm-training-java
Nous prévoyons de passer l'examen d'ingénieur en technologie de l'information appliquée en octobre. Parce que cette plage est également la plage de questions Si vous avez des suggestions ou d'autres choses à faire Commentez s'il vous plaît!
Recommended Posts