Teilen von Lernvideos: Java-Video-Tutorial
Normales Einfügen: Arbeiten Sie vom zweiten Element des Arrays aus. Wenn festgestellt wird, dass das vorherige Element größer als dieses ist, führen Sie eine Austauschoperation aus.
static int[] insertSort(int[] array){
int len = array.length;
for (int begin = 1; begin < len; begin++){
int cur = begin;
while (cur > 0 && array[cur] < array[cur-1]){
int tmp = array[cur];
array[cur] = array[cur-1];
array[cur-1] = tmp;
cur--;
}
}
return array;
}Der erste Schritt der Optimierung: Arbeiten Sie vom zweiten Element des Arrays aus. Wenn festgestellt wird, dass das vorherige Element größer als dieses ist, verschieben Sie das vorherige Element zurück, bis das durch cur angezeigte Element größer oder gleich ist Das vorherige Element. Die Position, auf die cur zu diesem Zeitpunkt zeigt, ist die Position, an der das einzufügende Element eingefügt werden soll.
static int[] insertSort2(int[] array){
int len = array.length;
for (int begin = 1; begin < len; begin++){
int cur = begin;
int tmp = array[cur];
while (cur > 0 && array[cur] < array[cur-1]){
array[cur] = array[cur-1];
cur--;
}
array[cur] = tmp;
}
return array;
}Zweiter Schritt Optimierung
Der dritte Algorithmus ist im Wesentlichen derselbe wie der zweite. Beide finden die einzufügende Position und verschieben die Elemente Die binäre Suche reduziert die Anzahl der Vergleiche, also der Aufrufe der cmp-Funktion, und reduziert auch die Aufrufe der Swap-Funktion. Es ist schneller, die Position zu finden, an der das aktuelle Element eingefügt werden soll, und es dann zu verschieben, was die Effizienz verbessert.
static int[] insertSort3(int[] array){
int len = array.length;
for (int begin = 1; begin < len; begin++){
int v = array[begin];
int insertIndex = search(array,begin);
// 将 [insertIndex, begin) 范围内的元素往右边挪动一个单位
for (int i = begin; i > insertIndex; i--){
array[i] = array[i-1];
}
array[insertIndex] = v;
}
return array;
}
static int search(int[] array, int index){
int begin = 0;
int end = index;
while(begin < end){
int mid = (begin+end) >> 1;
if (array[index] < array[mid]){
end = mid;
}else{
begin = mid+1;
}
}
return begin;
}Es ist zu beachten, dass nach der Verwendung der binären Suche nur die Anzahl der Vergleiche reduziert wird, die durchschnittliche zeitliche Komplexität der Einfügungssortierung jedoch immer noch O(n^2) beträgt.
Trennung der Verschiebungsoperation Wirkung:
package com.mj.sort.cmp;import com.mj.sort.Sort;public class InsertionSort3<T extends Comparable<T>> extends Sort<T> {
// protected void sort() {// for (int begin = 1; begin < array.length; begin++) {// T v = array[begin];// int insertIndex = search(begin);// // 将 [insertIndex, begin) 范围内的元素往右边挪动一个单位 for (int i = begin - 1; i >= insertIndex; i--) { }// for (int i = begin; i > insertIndex; i--) {// array[i] = array[i - 1];// }// array[insertIndex] = v;// }// }
@Override
protected void sort() {
for (int begin = 1; begin < array.length; begin++) {
insert(begin, search(begin)); //元素索引给你，你告诉这个位置的元素往哪插
}
}
/**
* 将source位置的元素插入到dest位置
* @param source
* @param dest
*/
private void insert(int source, int dest) {
T v = array[source];
for (int i = source; i > dest; i--) {
array[i] = array[i - 1];
}
array[dest] = v;
}
/**
* 利用二分搜索找到 index 位置元素的待插入位置
* 已经排好序数组的区间范围是 [0, index)
* @param index
* @return
*/
private int search(int index) {
int begin = 0;
int end = index;
while (begin < end) {
int mid = (begin + end) >> 1;
if (cmp(array[index], array[mid]) < 0) {
end = mid;
} else {
begin = mid + 1;
}
}
return begin;
}}Verwandte Empfehlungen: Java-Einführungs-Tutorial
Das obige ist der detaillierte Inhalt vonSo optimieren Sie nach der Implementierung der Einfügungssortierung in Java weiter. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!
