So implementieren Sie Einfügungssortierung und Hill-Sortierung in einer Java-Datenstruktur

1. Text

1. Das Konzept des Sortierens und seine Anwendung

1.1 Sortieren Konzept

Sortieren : Das sogenannte Sortieren bedeutet , eine Reihe von Datensätzen entsprechend der Größe eines oder mehrerer Schlüsselwörter in zu erhöhen it Oder Operationen in absteigender Reihenfolge .

Stabilität: Es wird davon ausgegangen, dass sich in der zu sortierenden Datensatzreihenfolge die relative Reihenfolge dieser Datensätze nicht ändert. Das heißt, in der ursprünglichen Sequenz ist r[i] = r[j] und r[i] liegt vor r[j], aber in der sortierten Sequenz liegt r[i] immer noch vor r[j], also Dies Der Sortieralgorithmus wird als stabil bezeichnet, andernfalls als instabil.

Interne Sortierung: Sortierung, bei der alle Datenelemente im Speicher abgelegt werden.

Externe Sortierung: Es gibt zu viele Datenelemente, die nicht gleichzeitig im Speicher abgelegt werden können, die Daten können nicht gleichzeitig gespeichert werden zwischen internem und externem Speicher verschoben.

1.2 Sortieranwendung

Nachdem ich die Grundkonzepte des Sortierens gelesen habe, fragen sich einige Freunde vielleicht, was passieren wird, selbst wenn ich das Sortieren gelernt habe in der Praxis? Ist es im Leben nützlich? Tatsächlich Sortieren gibt es überall im Leben , etwa bei der Wahl verschiedener Abmessungen eines Produkts, oder beim Ranking von Universitäten. Tatsächlich steckt dahinter die Idee des Sortierens, #🎜 🎜# gut lernen Sortieren kann uns helfen, alle Aspekte des Lebens aus einer anderen Dimension zu betrachten und Probleme im Leben besser zu lösen.

1.3 Gängige Sortieralgorithmen

# 🎜 🎜#Im Bereich der Datenstruktur haben wir vier gängige Sortieralgorithmen:

①

Einfügungssortierung

: Direkteinfügungssortierung, Hill-Sortierung# 🎜 🎜#②Auswahlsortierung

: Auswahlsortierung, Heap-Sortierung

③Austauschsortierung

: Blasensortierung, Schnellsortierung

#🎜 🎜#④Sortierung zusammenführen: Sortierung zusammenführen

2. Implementierung des Einfügungssortierungsalgorithmus

Weil aufgrund Aus Platzgründen stellen wir in diesem Artikel hauptsächlich

direkte Einfügungssortierung

und

Hill-Sortierung

in der Einfügungssortierung vor, und die direkte Einfügungssortierung wird oft als Einfügungssortierung bezeichnet. 2.1 Einfügungssortierung

2.1.1Grundidee

Direkte Einfügungssortierung ist eine einfache Einfügungssortierungsmethode #🎜 🎜#

Die Grundidee besteht darin, die zu sortierenden Datensätze nacheinander entsprechend der Größe ihrer Schlüsselwerte in eine bereits sortierte Reihenfolge einzufügen, bis alle Datensätze eingefügt sind, um eine neue geordnete Reihenfolge zu erhalten

                                                                                                                                              # Wenn wir Poker spielen, verwenden wir die Idee der Einfügungssortierung. Wenn

Sie eine neue Karte ziehen, vergleichen Sie diese natürlich nacheinander mit dem vorhandenen Kartenstapel in Ihrer Hand und legen sie an die Position , an der sie nach dem Vergleich sein sollte. Wir wissen vielleicht nicht, was Einfügungssortierung ist, aber unser unbewusster Ansatz stimmt genau mit der Einfügungssortierung überein.

2.1.2 Direkteinfügungssortierung Verwenden Sie eine geschriebenere Sprache, um die Direkteinfügungssortierung zu beschreiben: Beim Einfügen des i-ten (i> =1 ) Elemente, das vorherige Array[0],Array[1],...,Array[i-1] wurden sortiert. Verwenden Sie zu diesem Zeitpunkt den Sortiercode von Array[i] und Array[i-1 ],Array [i-2],... Vergleichen Sie die Sortiercodesequenz, finden Sie die Einfügeposition, fügen Sie Array[i] ein und verschieben Sie die Elemente an der ursprünglichen Position nach hinten

Aber einige Freunde mögen das vielleicht Ich glaube, ich verstehe es nicht ganz, also sagen wir es mal in Laiensprache. Jetzt

liegt eine ungeordnete Anordnung vor Ihnen. Unser Ziel ist es, diese ungeordnete Anordnung in aufsteigende oder absteigende Reihenfolge zu bringen

.

Nehmen wir als Beispiel die aufsteigende Reihenfolge: Da das Array ungeordnet ist, müssen wir

mit der Sortierung

ab dem zweiten Element des Arrays beginnen. Warum nicht die erste? Denn wenn es nur eine Zahl gibt, kann man sie nicht mit anderen Elementen vergleichen. Wenn es also nur ein Element gibt, wird es standardmäßig geordnet.

Nachdem wir verstanden haben, warum wir ab dem zweiten Element sortieren müssen, müssen wir nun die Elemente der Reihe nach einfügen und sortieren . Das erste ist das Einfügen und Sortieren des zweiten Elements. Im Bild unten sehen wir, dass das zweite Element 44 ist. 44 ist um 3 größer als das erste Element, sodass das zweite Element nicht verschoben werden muss. Als nächstes folgt das Einfügen und Sortieren des dritten Elements. Wir haben festgestellt, dass das dritte Element 38 kleiner als das zweite Element 44 ist, was unsere Erwartungen an die aufsteigende Reihenfolge nicht erfüllt, also verschieben wir 44 an die Position 38. Zwischen dem zweiten und Dritte Elemente. Nach der Sortierung haben wir festgestellt, dass 38 größer als 3 ist, das heißt, das erste und das zweite Element sind ebenfalls in Ordnung, sodass die Position des ersten Elements nicht verschoben werden muss 38 sollte sich im zweiten Element im Array-Element befinden, daher fügen wir einfach 38 an der Position des zweiten Elements ein. Ich glaube, dass die Freunde, die das gesehen haben, das Einfügen und Sortieren nachfolgender Elemente in der Hand haben sollten. Wie können wir in Bezug auf den Code das Einfügen und Sortieren der oben genannten Elemente implementieren? Wir haben zwei Hauptvariablen genommen:

"des"

und "end", des ist der Anfangsindex des Elements, das wir einfügen möchten, und end stellt den Index von ein Mit dem letzten Element der vorherigen Sequenz wird die Bewegung des Endes fortgesetzt, d. h. das Ende des -Vergleichs, der grob in zwei Fälle unterteilt ist. 🎜🎜#: ①Das durch des dargestellte Element ist größer als das durch end dargestellte Element. ②end hat das erste Element der Sequenz erreicht. Zu diesem Zeitpunkt ist des entweder das erste oder das zweite Element. Die spezifischen Bilder und Codes lauten wie folgt:

//插入排序[升序]
int* InsertSort(int* arr, int n)
{
 
	//整体排序
	for (int i = 1; i < n; i++)
	{
		int end = i - 1;
		int des = arr[i];
		//单趟排序
		while (end >= 0)
		{
			if (des >= arr[end])
				break;
			if (des < arr[end])
			{
				arr[end + 1] = arr[end];
				end--;
			}
			arr[end+1] = des;
		}
	}
}

#🎜 🎜 # Hinweis:

Zusammenfassung der Sortierfunktionen für das direkte Einfügen

①Je näher der Elementsatz an der Reihenfolge liegt, desto höher ist die Zeiteffizienz des direkten Einfügens Sortieralgorithmus

# 🎜🎜#②Zeitkomplexität: O(N^2)

③ Raumkomplexität: O(1), es ist ein stabiler Sortieralgorithmus

④ Stabiles Geschlecht: Stabilität#### 🎜🎜 ## 🎜🎜#2.1.3 Hill-Sortierung (reduzierte inkrementelle Sortierung)#🎜🎜 ## 🎜🎜 ## 🎜🎜#Die Hill-Sortiermethode wird auch als Reduktions-Inkrementalmethode bezeichnet.

Die Grundidee der Hill-Sortiermethode besteht darin: Wählen Sie zunächst eine Ganzzahl aus, teilen Sie alle Datensätze in der zu sortierenden Datei in Ganzzahlgruppen auf und platzieren Sie alle Datensätze mit einem Abstand von Datensätzen innerhalb der Gruppe sind sortiert. Wiederholen Sie dann die oben beschriebene Gruppierungs- und Sortierarbeit. Wenn die Ganzzahl gleich 1 ist, werden alle Datensätze in derselben Gruppe sortiert.

Laienhaft ausgedrückt ist

die Hill-Sortierung eine Mehrfach-Direkteinfügungssortierung

, aber mit Ausnahme der letzten Direkteinfügungssortierung unterscheidet sich die Sortierung von der ursprünglichen Direkteinfügungssortierung. Wenn einige Freunde dies sehen, fragen sie sich möglicherweise, warum mehrere Einfügungssortierungen durchgeführt werden. Was ist der Unterschied zwischen einer einzelnen Einfügungssortierung und einer normalen Einfügungssortierung? Machen Sie sich keine Sorgen, wir werden sie unten einzeln beantworten.

Erstens: Warum müssen wir die Einfügungssortierung mehrmals durchführen? Nachdem wir die obige Zusammenfassung der Merkmale der Einfügungssortierung gelesen haben, werden wir Folgendes feststellen: dann Einfügungssortierung Je höher die Zeiteffizienz

. Daher besteht der Zweck der Hill-Sortierung, mit Ausnahme der Tatsache, dass die letzte Sortierung eine normale Einfügungssortierung ist, darin, den Satz von Elementen kontinuierlich so anzupassen, dass er sich ständig der Ordnung annähert.

Der nächste Schritt ist der Unterschied zwischen Hill-Sortierung und normaler Einfügungssortierung mit Ausnahme der letzten Einfügungssortierung. Durch die obige Untersuchung der Einfügungssortierung werden wir feststellen, dass ein Element, das die richtige Position erreichen möchte, einzeln mit anderen Elementen verglichen, dh schrittweise verschoben werden muss Dies ist in Ordnung, wenn die Anzahl der Elemente im Array klein ist. Wenn die Anzahl der Elemente im Array jedoch groß ist, stellen Sie sich in aufsteigender Reihenfolge vor, dass sich das größte Element im Array an der ersten Position des Arrays befindet Es ist notwendig, dass dieses Element die letzte Position des Arrays erst erreicht, nachdem es einzeln mit den anderen Elementen im Array verglichen wurde. Wenn wir jedoch die Geschwindigkeit des Vergleichs erhöhen, d. h. den Abstand zwischen den Elementen erhöhen zwei verglichene Elemente, dann Kann dieses Element schneller dort ankommen, wo es sein sollte

. In der Situation des fliegenden Schachs wirft die Einfügungssortierung jedes Mal 1, und die Hash-Sortierung, mit Ausnahme der letzten Einfügungssortierung, wirft einen Punkt von 1, die restlichen Einfügungssortierungswürfe sind alle größer als 1. Daher ist es denkbar, dass die Hash-Sortierung erfolgt kann das Ende der Sortierung schneller erreichen.

Um das Verständnis von Freunden zu erleichtern, ist dieser Teil des Codes in zwei Teile unterteilt: ① Direkteinfügungssortierung mit festem Schritt ② Hash-Sortierung.

先是固定步伐的直接插入排序，先让我们通过图片来直观的看到数组数组内的元素通过这种操作后的变化。

//固定步伐的直接插入排序[升序]
void ShellSort(int* arr, int n)
{
	int gap = 3;
	int end;
	//有两种写法，看你要控制end，还是des
	/*for (int i=0; i < n-gap; i++)
	{
		int end = i;
		int des = arr[end + gap];
		while (end >= 0)
		{
			if (des >= arr[end])
				break;
			if (des < arr[end])
			{
				arr[end + gap] = arr[end];
				end -= gap;
			}
			arr[end + gap] = des;
		}
	}*/
 
	for (int i = gap; i < n ; i++)
	{
		int end = i-gap;
		int des = arr[end + gap];
		while (end >= 0)
		{
			if (des >= arr[end])
				break;
			if (des < arr[end])
			{
				arr[end + gap] = arr[end];
				end -= gap;
			}
			arr[end + gap] = des;
		}
	}
}

接着就是希尔排序

上述的代码是gap=3的情况下的直接插入排序，那么对于希尔排序而言，我们该对gap该如何选择呢？对于不同gap值的插入排序来说，我们会发现：gap越大，元素跳得越快，数组越不接近有序；而gap越小，元素跳的越慢，数组越接近有序。由于数组的大小不定，因此希尔排序也没有一个合适gap值适用于所有数组，显然，这个gap值一定是动态变化的。

对于gap的动态变化，常见的有两种：

①令gap等于数组的元素个数，每次插入排序后令gap除等2

②另一种则是令gap等于数组的元素个数，不过每次插入排序后令gap除以3再加1

无论哪种处理都能使gap动态变化并最后等于1，对数组进行一次插入排序，达到最后想要的效果。

代码如下：

//希尔排序
void ShellSortPlus(int* arr, int n)
{
	int gap=n;
	int end;
	while (gap > 1)
	{
	gap = gap / 2;
		
		for (int i=0; i < n - gap;i++)//有两种写法，看你要控制end，还是des
		{
			int end = i;
			int des = arr[end + gap];
			while (end >= 0)
			{
				if (des >= arr[end])
					break;
				if (des < arr[end])
				{
					arr[end + gap] = arr[end];
					end -= gap;
				}
				arr[end + gap] = des;
			}
		}
 
	}
}

二、测试代码

为了方便小伙伴们测试排序后的效果，为大家提供了测试的代码并包含排序的具体代码和包含的头文件。

#include 
#include 
#include 
 
//插入排序[升序]
int* InsertSort(int* arr, int n)
{
 
	//整体排序
	for (int i = 1; i < n; i++)
	{
		int end = i - 1;
		int des = arr[i];
		//单趟排序
		while (end >= 0)
		{
			if (des >= arr[end])
				break;
			if (des < arr[end])
			{
				arr[end + 1] = arr[end];
				end--;
			}
			arr[end+1] = des;
		}
	}
}
 
//固定步伐的直接插入排序[升序]
void ShellSort(int* arr, int n)
{
	int gap = 3;
	int end;
	//有两种写法，看你要控制end，还是des
	/*for (int i=0; i < n-gap; i++)
	{
		int end = i;
		int des = arr[end + gap];
		while (end >= 0)
		{
			if (des >= arr[end])
				break;
			if (des < arr[end])
			{
				arr[end + gap] = arr[end];
				end -= gap;
			}
			arr[end + gap] = des;
		}
	}*/
 
	for (int i = gap; i < n ; i++)
	{
		int end = i-gap;
		int des = arr[end + gap];
		while (end >= 0)
		{
			if (des >= arr[end])
				break;
			if (des < arr[end])
			{
				arr[end + gap] = arr[end];
				end -= gap;
			}
			arr[end + gap] = des;
		}
	}
}
 
 
//希尔排序
void ShellSortPlus(int* arr, int n)
{
	int gap=n;
	int end;
	while (gap > 1)
	{
	gap = gap / 2;
		
		for (int i=0; i < n - gap;i++)//有两种写法，看你要控制end，还是des
		{
			int end = i;
			int des = arr[end + gap];
			while (end >= 0)
			{
				if (des >= arr[end])
					break;
				if (des < arr[end])
				{
					arr[end + gap] = arr[end];
					end -= gap;
				}
				arr[end + gap] = des;
			}
		}
 
	}
}
 
//打印排序好的数组
void PrintSort(int*arr,int n)
{
	for(int i=0;i
Nach dem Login kopieren

Das obige ist der detaillierte Inhalt vonSo implementieren Sie Einfügungssortierung und Hill-Sortierung in einer Java-Datenstruktur. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!