Java-Algorithmus (1) – primärer Sortieralgorithmus
- 黄舟Original
- 2017-03-01 11:15:051322Durchsuche
Programm = Datenstruktur + Algorithmus. Bei den Frameworks, die Projekte erstellen, die nicht von uns geschrieben wurden, kann das Niveau eines Projekts wirklich beurteilt werden, ob die von uns angepassten Datenstrukturen praktisch, prägnant und gering gekoppelt sind und effektiv, weniger fehleranfällig. Wenn Sie nicht jeden Tag von morgens bis abends Steine verschieben möchten, ist das Erlernen von Algorithmen und das Analysieren von Datenstrukturen definitiv die einzige Möglichkeit für Sie, Ihr Niveau zu verbessern.
(1) Sortieralgorithmus
Algorithmen und Programmiersprachen sind eng miteinander verbunden, hängen jedoch nicht nur von einer bestimmten Sprache ab. Ohne Berücksichtigung der Implementierungssprache haben wir normalerweise die folgenden Sortiermethoden:
Auswahlsortierung
Einfügungssortierung
Hügelsortierung
Zusammenführungssortierung
Schnellsortierung
Wir sprechen nicht nur über diese Sortiermethoden im Allgemeinen. Nachdem wir die fünf Sortieralgorithmen vorgestellt haben, werden wir diese Methoden zusammenfassen und sie mit JavaAPI verbinden. Um die Implementierung dieser Sortiermethoden zu erleichtern, verwenden wir jetzt einige Hilfsmethoden. Diese Hilfsmethoden sind sehr einfach und dienen dazu, unseren Code prägnant zu gestalten.
/**
* 比较两个大小不同的数字，如果第一个参数比较小则返回true。
*
* @param v 第一个数字
* @param w 第二个数字
* @return 返回比较结果
*/
public static boolean less(int v , int w){ if(v<w) return true; return false;
} /**
* 交换数组中两个索引的内容
*
* @param arr 数组
* @param v 第一个索引
* @param w 第二个索引
*/
public static void exch(int[] arr,int v ,int w){ int temp=arr[v];
arr[v]= arr[w];
arr[w] = temp;
} /**
* 打印数组
*
* @param arr 要显示的数组
*/
public static void show(int[] arr){ for(int i=0;i<arr.length;i++)
System.out.println(arr[i]);
}(2) Sortierkostenmodell
In Java sind die überwiegende Mehrheit der Elemente Objekte, und die Beschreibung der Primärschlüssel dieser Objekte erfolgt durch Comparable Es wird durch den Mechanismus implementiert. Nur mit Comparable können wir die Konzepte der Ordnung und Sortierung haben. Wie kann man also untersuchen, ob eine Sortiermethode schnell oder langsam ist, wie schnell sie ist und wie effizient sie ist? Wir werden die Kosten jedes Sortieralgorithmus unter folgenden Aspekten untersuchen.
Vergleichen und austauschen (Wir müssen die Anzahl der Vergleiche und Austausche berechnen, um die Sortierkosten beurteilen zu können)
Zeit (die von einem Sortieralgorithmus benötigte Zeit oder die in einer bestimmten Situation benötigte Zeit)
Zusätzliche Speichernutzung (Einige Sortiermethoden erfordern zusätzlichen Speicherplatz, andere nicht)
Wir werden spezielle Methoden zur Kostenschätzung für einige spezielle Sortieralgorithmen angeben. Die meisten Sortiermethoden werden wir diskutieren am Ende, wenn diese Methode geeignet ist - schließlich sind diese unnützen Sortierungen längst abgeschafft.
(3) Auswahlsortierung
Auswahlsortierung ist der einfachste Sortieralgorithmus unter allen Sortierungen. Die Kernidee der Auswahlsortierung ist:
Behalten Sie ein geordnetes Unterarray am vorderen Ende des Arrays bei, suchen Sie jedes Mal das kleinste Element in der zweiten Hälfte des ungeordneten Arrays und kombinieren Sie es mit das erste Element nach dem Ende des Frontends. Tauschen Sie ein ungeordnetes Element aus, um dieses Element geordnet zu machen. Die Sortierung ist abgeschlossen, wenn die sortierten Teilarrayelemente der Gesamtzahl der Elemente entsprechen.
Laienhaft ausgedrückt: Wir finden zuerst das kleinste Element im Array und tauschen es mit dem ersten Element aus. Wenn das erste Element das kleinste Element ist, dann tauschen wir es selbst aus . Dann finden wir das kleinste Element vom zweiten Element bis zum Ende, tauschen es mit dem zweiten Element des Arrays aus und so weiter, wobei wir kontinuierlich das kleinste Element unter den verbleibenden Elementen auswählen.
1. Vergleich und Austausch
Auswahlsortierung hat eine feste Anzahl von VergleichenN2/2 und a feste Anzahl der AustauscheN.
In Bezug auf die Anzahl der Vergleiche muss bei der Auswahlsortierung zum ersten Mal ein Vergleich vom ersten bis zum letzten Element durchgeführt werden, um zu wissen, welches das kleinste Element ist. Beim zweiten Mal sind N-1 Vergleiche erforderlich, um das kleinste Element zu ermitteln. Insgesamt sind N+(N-1)+(N-2)+ ··· + 1 = N2/2 Mal erforderlich.
Denn aufgrund der Programmierung des Algorithmus müssen wir, selbst wenn das kleinste Element bereits an der richtigen Position ist, seine Position immer noch mit sich selbst austauschen, sodass die Anzahl der Austausche ebenfalls auf N-mal festgelegt ist.
2. Zeit
Die Laufzeit der Auswahlsortierung ist festgelegt, etwa N2/2 Mal des Vergleichs (N2 /2, wir können die N-Zeiten des Austauschs grundsätzlich ignorieren). Wenn wir die Laufzeit einer Sortiermethode nicht abschätzen können, kennen wir jetzt mindestens eine garantierte Sortiermethode. Solange Ihre Sortiermethode ordnungsgemäß verwendet wird, wird ihre Laufzeit niemals N2/2 Vergleichszeiten überschreiten .
3.java实现
package Sort;/**
*
* @author QuinnNorris 选择排序
*/public class Sort1 {
/**
* @param args
*/
public static void main(String[] args) { // TODO Auto-generated method stub
int[] arr = { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 }; // 测试数组
sort(arr); // 调用排序算法
Tool.show(arr); // 打印
} /**
* 用选择排序将arr升序排列
*
* @param arr
* 所要排列的数组
*/
public static void sort(int[] arr) {
for (int i = 0; i < arr.length; i++) {
int min = i;
for (int j = i + 1; j < arr.length; j++)
if (Tool.less(arr[j], arr[min]))
min = j;
Tool.exch(arr, min, i);
}
}
}4.特点
选择排序非常简单，他有两个很鲜明的特点：
1.运行时间和输入无关
运行时间和输入无关，好听的讲就是无论多么乱的数据都会在固定的时间之内完成排序，但是更多的情况下，这种前一遍比较不能为后一遍比较提供任何价值的算法是非常费时的。夸张的讲，如果我们要完成某个几乎接近有序的数组的排序，你会发现，使用选择排序所需的时间和去排序那些无序的数组竟然是完全一样的。这在很多情况下是大家不能接受的。
2.数据移动最少
为了保证最少的交换数据，我们不断的进行比较，每次的交换都会百分之百的把一个数字放在正确的位置上。其他的任何排序方法都不具备这个特性。
（四）插入排序
在选择排序中，一个几乎有序的数组和一个完全无序的数组所需时间是一样的。插入排序则完美的解决了这个问题：
从数组的头部开始，通过不断的一次一位的比较和交换，让每个数据都能插入前端有序部分中自己合理的位置，当所有的元素都完成一遍操作后，排序完成。
我们将要排序的那个元素和前面一位元素比较，如果比前面的元素小，则交换位置，这个元素继续和再前面的元素比较，如果仍然小则继续交换，知道前面的元素小于该元素位置。这个时候，这个不断交换的元素就在这个数组中达到了自己合适的位置，刚才其他被交换的元素，都像是“向后移动一个位置”，为这个元素挪出了空间，这就是插入排序。这种排序很类似我们在打桥牌时整理牌的方法，不断地将牌按照大小从后向前插入。
1.比较和交换
在一个随机排序而且主键不重复的数组中，平均情况下插入排序需要N2/4次比较以及N2/4次交换。在最坏的情况下需要N2/2次比较和N2/2次交换，最好情况下需要N-1次比较和0次交换。
这个平均情况是怎么计算得出的呢？通常情况下，我们认为数组中的一个数字在整个数组中会被移动半个数组的长度（在平均情况下，每个数字都会移动到有序部分的中间位置，在这种情况下，数字自己的移动和被向后“推”的移动加起来长度为半个数组），在半个数组的移动算作平均情况下，我们得到N2/4的比较和交换次数。
2.时间
我们可以看出，用插入排序算法排序的时间和这个数组情况有很大关系，如果数组是非常无序的，它的速度要慢于选择排序，但是如果我们现在要排序的数组是几乎完全有序的，那么它的时间将会非常的小。就像我们手中握着一副全都排好顺序的扑克牌，这时你抽到一张梅花9，你可以非常快的将它插到你的手牌中。
数组中每个元素距离他的最终位置不远
一个有序数组的大数组接一个小数组
数组中只有几个元素的位置不正确
上述的三种情况下，使用插入算法会非常非常有效。事实上，当顺序错误的数量很少的时候，插入排序会比其他任何排序算法都快。
3.java实现
package Sort;/**
*
* @author QuinnNorris 插入排序
*/public class Sort2 {
/**
* @param args
*/
public static void main(String[] args) { // TODO Auto-generated method stub
int[] arr = { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 }; // 测试数组
sort(arr); // 调用排序算法
Tool.show(arr); // 打印
} /**
* 用插入排序将arr升序排列
*
* @param arr
* 所要排列的数组
*/
public static void sort(int[] arr) {
for (int i = 0; i < arr.length; i++)
for (int j = i; j > 0; j--)
if (Tool.less(arr[j], arr[j - 1]))
Tool.exch(arr, j, j - 1);
}
}4.特点
在插入排序中，因为他的速度和原有的序列有很大关系。在这里，我们将在原序列中位置顺序颠倒的一对数字叫做倒置，这只是我们起的一个名字，它表示两个数字的位置是错误的（a应该在b的前面，但是在数组中a在b的后面，无论a与b相隔多远，都可以称a、b是一个倒置）。插入排序具有以下几点特性：
交换和比较的次数相同
比较的次数大于等于倒置的数量
比较的次数小于等于倒置数量加上数组的大小再减一
除此之外，插入排序作为一种初级排序算法，会在之后的高级排序算法中作为一个中间算法频频出现，我们会在以后再见到他。
（五）选择算法和插入算法比较
这两种算法是如此的相似，以至于我们非常好奇想将他们比较一番。对于随机排序无重复的数组，插入排序和选择排序的运行时间都是平方级别的，所以两者只比应该是一个较小的常数。
(6) Hill-Sortierung
Der Sortieralgorithmus, den wir als Nächstes vorstellen werden, ist kein primärer Sortieralgorithmus, sondern nutzt tatsächlich die Technologie des Einfügungsalgorithmus Dann besprechen Sie es hier. Hill-Sortierung bezieht sich auf:
Durch die Formulierung eines konstanten h-Werts von groß nach klein und das Einfügen einer Sortierung werden die Elemente mit einem beliebigen h-Intervall im Array geordnet. Reduzieren Sie die Größe von h weiter, bis h=1 ist, sodass das gesamte Array geordnet ist.
Nehmen wir Bridge als Vergleich. Am Anfang haben Sie ein Kartenspiel in ungeordneter Reihenfolge, aber dann haben Sie plötzlich das Gefühl, dass diese Methode zu langsam ist Daher planen Sie zunächst eine grobe Überprüfung. Sie bringen einige Karten in die richtige Reihenfolge, aber andere Karten sind nicht in der richtigen Reihenfolge. Auf diese Weise sichten Sie Ihre Karten mehrmals und bringen schließlich alle Karten in Ihrer Hand in die richtige Reihenfolge. Das ist Hill-Sorte.
Wenn wir Zehntausende Arrays sortieren müssen, können wir normalerweise die Hill-Sortierung verwenden.
Bei der Hill-Sortierung definieren wir zunächst ein h. Wir verwenden h als Intervall zum Teilen eines Subarrays. Wir verwenden den Einfügealgorithmus, um dieses Subarray zu sortieren. Dann verkleinern wir h weiter und sortieren das neue Array. Wenn h schließlich 1 ist, sorgt diese Sortierung dafür, dass alle Daten in Ordnung bleiben.
1. Vorteile
Was sind also die Vorteile der Hill-Sortierung? Wir wissen, dass der Vorteil der Einfügungssortierung darin besteht, dass sie beim Sortieren teilweise geordneter Sequenzen extrem schnell und beim Sortieren kleiner Arrays sehr schnell ist. Unsere Hügelsortierung vereint diese beiden Vorteile. Wenn h groß ist, ist das gesamte Array relativ klein und die Einfügungssortierung ist schneller. Wenn h klein ist, ist das gesamte Array allmählich geordneter. Zu diesem Zeitpunkt ist die Verwendung der Einfügungssortierung ebenfalls eine sehr gute Wahl. Man kann sagen, dass die Hill-Sortierung diese beiden Vorteile kombiniert und die Gesamtzeit relativ schnell ist.
2. Zeit
Für die Hill-Sortierung beabsichtigen wir aus folgenden Gründen nicht, sie gemäß unserer oben genannten Analysemethode zu analysieren. Erstens ist es sehr schwierig, die Hill-Sortierung durch Austausch und Vergleich zu untersuchen, da der Schlüsselfaktor h ist, h eine Konstante ist und wir das Intervall dieses Sprungs ändern können, indem wir unterschiedliche h festlegen. Und es gibt keine klare Erklärung: Welcher Regel folgt h, um den besten Effekt zu erzielen (normalerweise können wir 3*h+1 verwenden, das heißt: 1, 4, 13, 40, 121, 364 ... Diese Zahlengruppe ist verwendet als h). Da h nicht bestimmt werden kann, gibt es keinen optimalen Zeitpunkt.
3. Praktische Anwendung
Erfahrene Programmierer verwenden manchmal die Hill-Sortierung, da die Laufzeit der Hill-Sortierung für mittelgroße Arrays akzeptabel ist. Die Codemenge ist sehr gering und es wird kein zusätzlicher Speicherplatz beansprucht. Vielleicht haben wir schnellere Algorithmen, aber für große N sind sie wahrscheinlich nur weniger als doppelt so schnell wie die Hill-Sortierung. Und es ist sehr kompliziert. Wenn Sie sortieren müssen, aber keine systematische Sortierfunktion haben, können Sie die Hill-Sortierung in Betracht ziehen und dann überlegen, ob Sie sie durch eine erweiterte Sortiermethode ersetzen möchten.
Programm = Datenstruktur + Algorithmus. Bei den Frameworks, die Projekte erstellen, die nicht von uns geschrieben wurden, kann das Niveau eines Projekts wirklich beurteilt werden, ob die von uns angepassten Datenstrukturen praktisch, prägnant und gering gekoppelt sind und effektiv, weniger fehleranfällig. Wenn Sie nicht jeden Tag von morgens bis abends Steine verschieben möchten, ist das Erlernen von Algorithmen und das Analysieren von Datenstrukturen definitiv die einzige Möglichkeit für Sie, Ihr Niveau zu verbessern.
Das Obige ist der Inhalt des Java-Algorithmus (1) – primärer Sortieralgorithmus. Weitere verwandte Inhalte finden Sie auf der chinesischen PHP-Website (www.php.cn).