Explication détaillée du tri rapide en JavaScript

Cet article parle du tri rapide en JavaScript Si vous ne connaissez pas le tri rapide en JavaScript ou si vous êtes intéressé par le tri rapide en JavaScript, jetons un coup d'œil à cet article. Arrêtez les bêtises et allez droit au but

Le tri rapide est une autre application typique de l'idée diviser pour régner dans les algorithmes de tri. Essentiellement, le tri rapide doit être considéré comme une méthode récursive diviser pour mieux régner basée sur le tri à bulles.

Le nom du tri rapide est simple et grossier, car dès que vous entendrez ce nom, vous connaîtrez le sens de son existence, qui est rapide et efficace, c'est l'un des algorithmes de tri les plus rapides pour le traitement ! grandes données. Bien que la complexité temporelle du pire cas ait atteint O(n²), elle est excellente et, dans la plupart des cas, fonctionne mieux que l'algorithme de tri avec une complexité temporelle moyenne de O(n log n). Mais pourquoi, je ne le fais pas ? sais non plus. . . Heureusement, mon trouble obsessionnel-compulsif est réapparu. Après avoir vérifié de nombreuses informations, j'ai finalement trouvé une réponse satisfaisante sur le "Concours d'Art Algorithmique et Informatique" :

La pire situation de fonctionnement du tri rapide est O(n²) , comme le tri rapide des nombres séquentiels. Mais son temps attendu amorti est O(n log n), et le facteur constant implicite dans la notation O(n log n) est très petit, ce qui est bien plus petit que le tri par fusion dont la complexité est stable et égale à O(n log n). n). Par conséquent, pour la plupart des séquences de nombres aléatoires avec un ordre faible, le tri rapide est toujours meilleur que le tri par fusion.

Démonstration d'animation de tri rapide

Implémentation du code JavaScript de tri rapide :

function quickSort(arr, left, right) {  
    var len = arr.length,  
        partitionIndex,  
        left = typeof left != 'number' ? 0 : left,  
        right = typeof right != 'number' ? len - 1 : right;  
  
    if (left < right) {  
        partitionIndex = partition(arr, left, right);  
        quickSort(arr, left, partitionIndex-1);  
        quickSort(arr, partitionIndex+1, right);  
    }  
    return arr;}function partition(arr, left ,right) {     //分区操作  
    var pivot = left,                      //设定基准值（pivot）  
        index = pivot + 1;  
    for (var i = index; i <= right; i++) {  
        if (arr[i] < arr[pivot]) {  
            swap(arr, i, index);  
            index++;  
        }          
    }  
    swap(arr, pivot, index - 1);  
    return index-1;}function swap(arr, i, j) {  
    var temp = arr[i];  
    arr[i] = arr[j];  
    arr[j] = temp;}

Ce qui précède est tout le contenu de cet article, Si vous n’y connaissez pas encore grand-chose, vous pouvez facilement le maîtriser en mettant davantage en œuvre les deux côtés !

Recommandations associées :

Explication détaillée du tri à bulles Js et du tri rapide

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!