Instabile Sortierung
Auswahlsortierung:
Der nach der ersten Vergleichsrunde erhaltene kleinste Datensatz wird mit der Position des ersten Datensatzes ausgetauscht, und dann schließt der kleinste Datensatz den ersten Datensatz aus Die Datensätze werden in der zweiten Runde verglichen und der kleinste erhaltene Datensatz wird mit dem zweiten Datensatz ausgetauscht
Zeitkomplexität: O(n^2)
Raumkomplexität: O(1)
public static void selectSort(int[] arr){
if (arr == null || arr.length == 0)
return;
int len = arr.length;
for (int i = 0; i < len; i++) {
int min = arr[i];
int index = i;
for (int j = i+1; j < len; j++) {
if (arr[j] < min) {
min = arr[j];
index = j;
}
}
arr[index] = arr[i];
arr[i] = min;
}
} Schnell Sortierung:
Für einen bestimmten Satz von Datensätzen wird nach jedem Sortierdurchlauf die ursprüngliche Sequenz in zwei Teile geteilt, wobei alle Datensätze im ersten Teil kleiner sind als alle Datensätze im zweiten Teil, und dann werden die beiden Teile geteilt werden nacheinander aufgezeichnet. Schnellsortierung durchführen
Zeitkomplexität: O(nlogn) Schlimmste: O(n^2)
Raumkomplexität: O(nlogn)
public int Partition(int[] a,int start,int end){ int std = a[start];
while (start < end){
while(start < end && a[end] >= std)
end--;
a[start] = a[end];
while(start < end && a[start] <= std)
start++;
a[end] = a[start];
}
a[start] = std;
return start;
}
public void quickSort(int[] a,int start,int end){
if(start >= end){
return;
}
int index = Partition(a,start,end);
quickSort(a,start,index-1);
quickSort(a,index+1,end);
}Heap-Sortierung: vollständiger Binärbaum
wird Der Binärbaum wird an einen großen oberen Heap angepasst und dann wird das letzte Element des Heaps mit dem obersten Element des Heaps (dh dem Wurzelknoten des Binärbaums) ausgetauscht der maximale Datensatz; dann werden die ersten n-1 Elemente an den großen oberen Heap angepasst und dann das oberste Element des Heaps durch das letzte Element des aktuellen Heaps ersetzt, um den zweitgrößten Datensatz zu erhalten Element, das im angepassten Heap verbleibt. Zu diesem Zeitpunkt können Sie eine geordnete Sequenz erhalten
Zeitkomplexität: O(nlogn)
Raumkomplexität: O(1)
public void HeapSort(int[] a){
for (int i = a.length/2 - 1; i >= 0 ; i--) {
HeapAdjust(a,i,a.length-1);
}
for (int i = a.length - 1; i >= 0; i--) {
swap(a,0,i);
HeapAdjust(a,0,i-1);
}
}
private void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
public void HeapAdjust(int[] arr,int s,int len){
int tmp = arr[s];
for (int i = s * 2 + 1; i < len ; i = i * 2 + 1) {
if (i < len && arr[i] < arr[i+1]){
i++;
}
if (tmp > arr[i])
break;
arr[s] = arr[i];
s = i; //s记录被替换的子结点的索引
}
arr[s] = tmp;
} Direkte Einfügungssortierung:
Zuerst können die Datensätze als eine geordnete Sequenz betrachtet werden, und die verbleibenden Datensätze werden als ungeordnete Sequenzen bezeichnet. Fügen Sie dann ausgehend vom zweiten Datensatz den aktuell verarbeiteten Datensatz der Reihe nach entsprechend der Größe des Datensatzes in die zuvor geordnete Sequenz ein, bis der letzte Datensatz in die geordnete Sequenz eingefügt wird
Zeitkomplexität: O(n^2)
Raumkomplexität: O(1)
public static void insertSort(int[] arr){
if (arr == null || arr.length == 0)
return;
int len = arr.length;
for (int i = 1; i < len; i++) {
int curr = arr[i];
int j = i;
if (arr[j-1] > curr){
while (j > 0 && arr[j-1]> curr){
arr[j] = arr[j-1];
j--;
}
}
arr[j] = curr;
}
}Blasensortierung:
Beginnend mit dem ersten Datensatz werden zwei benachbarte Datensätze nacheinander verglichen. Wenn der vorherige Datensatz größer als der folgende Datensatz ist, werden die Positionen vertauscht. Nach einer Vergleichs- und Transpositionsrunde wird der größte Datensatz unter den n Datensätzen gefunden n-ten Datensatz. Führen Sie dann eine zweite Vergleichsrunde für die vorherigen n-1 Datensätze durch und wiederholen Sie den Vorgang, bis nur noch ein Datensatz zum Vergleich übrig ist
Zeitkomplexität: O(n^2)
Raumkomplexität: O(1)
public void bubbleSort(int[] arr){
boolean flag = true;
for (int i = 0; i < arr.length && flag; i++) {
flag = false;
for (int j = 0; j < arr.length - i - 1; j++) {
if (arr[j] > arr[j+1]){
flag = true;
swap(arr,j,j+1);
}
}
}
}
private void swap(int[] arr, int j, int i) {
int tmp = arr[j];
arr[j] = arr[i];
arr[i] = tmp;
}Sortierung zusammenführen: Rekursion und: separate Daten der Reihe nach zusammenführen
Füge alle zwei benachbarten Teilsequenzen der Länge 1 zusammen, um n/2 geordnete Teilsequenzen der Länge 2 oder 1 zu erhalten, füge dann die beiden zusammen und wiederhole diesen Vorgang, bis eine geordnete Sequenz erhalten wird
Zeitkomplexität: O(nlogn)
Raumkomplexität: O(n)
public static void mergeSort(int[] arr,int begin,int end){
int mid = (begin+end)/2;
if (begin < end){
mergeSort(arr,begin,mid);
mergeSort(arr,mid+1,end);
Merge(arr,begin,end,mid);
}
}
public static void Merge(int[] arr,int begin,int end,int mid){
int[] temp = new int[end-begin+1];
int i = begin;
int j = mid+1;
int k=0;
while (i <= mid && j <= end){
if (arr[i] < arr[j]){
temp[k++] = arr[i++];
}else{
temp[k++] = arr[j++];
}
}
while (i <= mid){
temp[k++] = arr[i++];
}
while (j <= end){
temp[k++] = arr[j++];
}
for (int m = 0;m < temp.length;m++){
arr[m+begin] = temp[m];
}
}Das obige ist der detaillierte Inhalt vonSo implementieren Sie einen Sortieralgorithmus mit Java. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!
![[Web-Frontend] Node.js-Schnellstart](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
