J'ai fait un nouvel algorithme de tri!

Pour le moment, j'ai mis au point un algorithme de tri. J'ai pensé: "Est-ce que ça ne va pas marcher?", Et quand j'ai écrit un petit flot sur un morceau de papier autour de cette zone, il ne semble y avoir rien d'étrange à ce sujet. Je l'ai implémenté avec la colle de "Alors, voulez-vous l'implémenter! W".

Récemment, faute de matériel, je n'ai introduit que des programmes antérieurs, mais celui-ci en fait partie et il est implémenté en java. Je pense que c'était il y a environ un an.

Le nom de l'algorithme est "Hanoi Sort"

La raison de cette dénomination est que le mouvement pour réaliser le tri en utilisant deux piles était similaire à la résolution d'une tour à Hanoi.

Ce qui suit montre comment trier par Hanoi Sort.

Explication de l'algorithme

Cet algorithme de tri utilise deux piles, une pile de tri et une pile de stockage temporaire. Le flux de tri est illustré ci-dessous.

Remplissez la pile de tri avec une valeur
Remplacez le contenu de la pile de tri par la pile de stockage temporaire.
Stockez la première valeur du tableau d'entrée dans la variable de comparaison
Comparez la valeur de la pile de stockage temporaire avec la valeur au début du tableau et compressez la valeur la plus petite dans la pile de tri.
Continuez jusqu'à ce que la pile de stockage temporaire soit vide
Répétez 2-5

Veuillez me pardonner la mauvaise explication. Je pense que le mouvement de la valeur est facile à comprendre si vous pouvez voir la vidéo gif ci-dessus.

Pour le moment, j'utilise pleinement la pile et je mets des valeurs d'entrée et de sortie tout en interposant des comparaisons. Je ne suis pas très sûr de calculer la quantité de calcul, mais je pense que c'est probablement O (n ^ 2), donc ce n'est pas une excellente sorte. À propos, en comparant le temps de tri de 30000 entiers avec le tri à bulles, le temps de traitement

Tri à Hanoi	Tri à bulles
3.997s	1.53s

J'ai fini avec un résultat misérable. Le montant du calcul est-il supérieur à O (n ^ 2)?

Je pense que j'y ai pensé moi-même, mais peut-être que ça existe déjà

Je ne connais même pas tous les algorithmes de tri. Peut-être que vous avez déjà un tri avec le même mécanisme, donc si quelqu'un le sait, faites-le moi savoir!

Enfin laisse tomber le putain de code

`hanoi_sort.java`


import java.util.*;
import java.io.*;

class hanoi_sort{
    static int[] data;
    public static void main(String[] args) {
        int dataNum = 30000;
        data = new int[30000];
        String[] strarray = new String[30000];
        int k = 0;

        try{
             File file = new File("numbers.txt");
             BufferedReader br = new BufferedReader(new FileReader(file));
             String str= null;
             k = 0;
             while((str = br.readLine()) != null){
                 strarray[k]=str;
                 data[k] = Integer.parseInt(strarray[k]);
                 System.out.println("[" + k + "]" + data[k]);
                 k++;
             }

             br.close();
        }catch(FileNotFoundException e){
              System.out.println(e);
        }catch(IOException e){
              System.out.println(e);
        }

        for(int i = 0; i < dataNum; i++){
            System.out.println("[" + i + "]: " + data[i]);
        }

        System.out.println("--------------sort---------------");

        Deque<Integer> dequeFirst = new ArrayDeque<>();
        Deque<Integer> dequeSecond = new ArrayDeque<>();
        int box = 0;
        int count = 0;
        int countF = 0;
        boolean flag = true;
        dequeFirst.push(data[0]);
        countF++;
        double start = System.currentTimeMillis();
        for(int i = 1; i < dataNum; i++){
            flag = true;
            while(flag){
                box = dequeFirst.pop();
                countF--;
                if(box <= data[i]){
                    dequeFirst.push(box);
                    countF++;
                    dequeFirst.push(data[i]);
                    countF++;
                    for(int j = 0; j < count; j++){
                        dequeFirst.push(dequeSecond.pop());
                        countF++;
                    }
                    count = 0;
                    flag = false;
                }else{
                    dequeSecond.push(box);
                    count ++;
                    if(countF == 0){
                        dequeFirst.push(data[i]);
                        countF++;
                        for(int j = 0; j < count; j++){
                            dequeFirst.push(dequeSecond.pop());
                            countF++;
                        }
                        count = 0;
                        flag = false;
                    }
                }
            }
        }
        double end = System.currentTimeMillis();

        for(int i = 0; i < dataNum; i++){
            System.out.println("[" + i + "]: " + dequeFirst.pop());
        }
        System.out.println("sort time: " + (end - start)  + "ms");
        System.out.println("sort time: " + (end - start)/1000  + "s");
    }
}

À propos, l'entrée est un fichier texte, et la valeur numérique est stockée dans le tableau en lisant celui dans lequel l'entier est écrit un par un sur chaque ligne (partout putain de spécification) Comme ça ↓

Les programmes et les idées d'il y a un an sont embarrassants à regarder en arrière.

Jusqu'à la fin Merci d'avoir lu!

[JAVA] J'ai essayé de créer un nouvel algorithme de tri, mais je ne sais pas si c'est vraiment nouveau