[JAVA] Ich habe versucht, einen neuen Sortieralgorithmus zu erstellen, aber ich weiß nicht, ob er wirklich neu ist

Ich habe einen neuen Sortieralgorithmus erstellt!

Im Moment habe ich mir einen Sortieralgorithmus ausgedacht. Ich dachte: "Wird es nicht funktionieren?", Und als ich einen kleinen Fluss auf ein Stück Papier um diesen Bereich herum schrieb, schien daran nichts Seltsames zu sein. Ich habe es mit dem Kleber "Dann wollen Sie es implementieren! W" implementiert.

In letzter Zeit habe ich aus Materialmangel nur frühere Programme eingeführt, aber dies ist eines davon, und es ist in Java implementiert. Ich denke, das war vor ungefähr einem Jahr.

Der Name des Algorithmus lautet "Hanoi Sort"

Der Grund für diese Benennung ist, dass der Schritt zum Sortieren mit zwei Stapeln dem Lösen eines Turms in Hanoi ähnlich war.

Das Folgende zeigt, wie nach Hanoi Sort sortiert wird.

Erklärung des Algorithmus

Dieser Sortieralgorithmus verwendet zwei Stapel, einen Sortierstapel und einen temporären Speicherstapel. Der Sortierablauf ist unten dargestellt.

1. Füllen Sie den Sortierstapel mit einem Wert
2. Ersetzen Sie den Inhalt des Sortierstapels durch den temporären Speicherstapel.
3. Speichern Sie den ersten Wert des Eingabearrays in der Vergleichsvariablen
4. Vergleichen Sie den Wert des temporären Speicherstapels mit dem Wert am Anfang des Arrays und packen Sie den kleineren Wert in den Sortierstapel.
5. Tun Sie dies, bis der temporäre Speicherstapel leer ist
6. Wiederholen Sie 2-5

Bitte vergib mir die schlechte Erklärung. Ich denke, dass die Bewegung des Wertes leicht zu verstehen ist, wenn Sie das GIF-Video oben sehen können.

Vorerst nutze ich den Stapel voll aus und setze Werte ein und aus, während ich Vergleiche einfüge. Ich bin nicht sehr sicher bei der Berechnung des Rechenaufwands, aber ich denke, es ist wahrscheinlich O (n ^ 2), also ist es keine ausgezeichnete Sorte. Übrigens, wenn man die Sortierzeit von 30.000 ganzen Zahlen mit der Blasensortierung vergleicht, die Verarbeitungszeit

Am Ende hatte ich ein miserables Ergebnis. Ist der Rechenaufwand größer als O (n ^ 2)?

Ich denke, ich habe selbst darüber nachgedacht, aber vielleicht existiert es bereits

Ich kenne nicht einmal alle Sortieralgorithmen. Vielleicht haben Sie bereits eine Sorte mit dem gleichen Mechanismus. Wenn es jemand weiß, lassen Sie es mich bitte wissen!

Lass endlich den verdammten Code fallen

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");
    }
}

Übrigens ist die Eingabe eine Textdatei, und durch Lesen der Datei mit einer Ganzzahl in jeder Zeile wird der numerische Wert im Array gespeichert (überall verdammte Spezifikation). So ↓

6418
18183
13643
6535
8436
3820
8969
19150
11902
4122
.
.
.

Es ist peinlich, auf die Programme und Ideen von vor einem Jahr zurückzublicken.

Bis zum Ende Danke fürs Lesen!