Comment implémenter un algorithme de tri en utilisant Java

Tri instable

Tri par sélection :
Le plus petit enregistrement obtenu après le premier tour de comparaison est échangé avec la position du premier enregistrement, puis le plus petit enregistrement exclut le premier enregistrement Les enregistrements sont comparés au deuxième tour, et le plus petit enregistrement obtenu est échangé avec le deuxième enregistrement
Complexité temporelle : O(n^2)
Complexité spatiale : 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;
     }
    }

Tri rapide :
Pour un ensemble d'enregistrements donné, après chaque passe de tri, la séquence d'origine est divisée en deux parties, où tous les enregistrements de la première partie sont plus petits que tous les enregistrements de la dernière partie, puis le deux parties avant et après sont triées dans l'ordre. Tri rapide de certains enregistrements
Complexité temporelle : O(nlogn) Pire : O(n^2)
Complexité spatiale : 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);
    }

Tri par tas : arbre binaire complet
Ajustez l'arbre binaire à un grand tas supérieur, puis échangez le dernier élément du tas avec l'élément supérieur du tas (c'est-à-dire le nœud racine de l'arbre binaire). le dernier élément du tas est l'enregistrement maximum ; puis les n-1 premiers éléments dans un grand tas supérieur, puis échangez l'élément supérieur du tas avec le dernier élément du tas actuel pour obtenir le deuxième plus grand enregistrement. jusqu'à ce qu'il ne reste qu'un seul élément dans le tas ajusté, qui est l'enregistrement minimum. Une séquence ordonnée peut être obtenue lorsque
Complexité temporelle : O(nlogn)
Complexité spatiale : 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;
    }

Tri stable

Tri par insertion directe :
Le premier enregistrement peut être considéré comme une séquence ordonnée qui lui est propre, et les enregistrements restants sont appelés séquences non ordonnées. Ensuite, à partir du deuxième enregistrement, insérez l'enregistrement en cours de traitement dans la séquence ordonnée précédente dans l'ordre en fonction de la taille de l'enregistrement jusqu'à ce que le dernier enregistrement soit inséré dans la séquence ordonnée
Complexité temporelle : O(n^2)
Complexité spatiale : 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;
        }
    }

Tri des bulles :
À partir du premier enregistrement, deux enregistrements adjacents sont comparés en séquence. Lorsque l'enregistrement précédent est plus grand que l'enregistrement suivant, les positions sont inversées. Après une série de comparaison et de transposition, l'enregistrement le plus grand parmi les n enregistrements sera localisé. nième enregistrement bit, puis effectuez un deuxième tour de comparaison sur les n-1 enregistrements précédents, en répétant le processus jusqu'à ce qu'il ne reste qu'un seul enregistrement à comparer
Complexité temporelle : O(n^2)
Complexité spatiale : 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;
    }

Tri par fusion : récursivité et union : les données distinctes sont fusionnées dans l'ordre
Fusionnez toutes les deux sous-séquences adjacentes de longueur 1 pour obtenir n/2 sous-séquences ordonnées de longueur 2 ou 1, puis fusionnez les deux et répétez ce processus jusqu'à ce qu'une séquence ordonnée soit obtenue
Complexité temporelle : O(nlogn)
Complexité spatiale : 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];
        }
    }

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!