Comment insérer des éléments dans un tableau Java et les trier rapidement

1. Opérez à partir du deuxième élément du tableau. Si vous constatez que l'élément devant lui est plus grand que lui, déplacez l'élément devant lui jusqu'à ce que l'élément pointé par cur soit supérieur ou égal à l'élément précédent. .A ce moment cur La position pointue est la position où l'élément à insérer doit être inséré.

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. La recherche binaire réduit le nombre de comparaisons, c'est-à-dire les appels à la fonction cmp, et réduit également les appels à la fonction swap. Il est plus rapide de trouver la position où l'élément actuel doit être inséré, puis de le déplacer, ce qui améliore l'efficacité.

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

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!