So fügen Sie Elemente in ein Java-Array ein und sortieren sie schnell

1. Arbeiten Sie vom zweiten Element des Arrays aus. Wenn Sie feststellen, dass das Element davor größer ist als dieses, verschieben Sie das Element davor nach hinten, bis das Element, auf das cur zeigt, größer oder gleich dem vorherigen Element ist . Zu diesem Zeitpunkt cur Die spitze Position 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;
 
}

2. 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;
 
}

Das obige ist der detaillierte Inhalt vonSo fügen Sie Elemente in ein Java-Array ein und sortieren sie schnell. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!