Interview de Meituan : S'il vous plaît, écrivez à la main un programme rapide, j'ai été choqué !

Aujourd'hui, l'intervieweur m'a demandé d'écrire un tri rapide sur place. La scène est la suivante :

Intervieweur : Continuons à parler de structures de données et d'algorithmes. (Tout en parlant, il a retourné mon CV et m'a tendu un stylo, ce qui signifie qu'il m'a demandé d'écrire au dos de mon CV)

Rookie moi : Que veux-tu dire ? L'écrire ici ? (Montrant le CV)

Intervieweur : Ouais

Moi recrue : Non

Intervieweur : D'accord, c'est tout pour l'interview d'aujourd'hui

Moi recrue : (Je suis très en colère, je veux le mettre sur mon plan de gestion du travail reprendre Écrire du code ? ) Shadiao

Intervieweur : (Avec le recul, confus)

Pensez-y, je suis encore trop jeune, ce ne serait pas comme ça maintenant. Écrivez simplement, ce n’est qu’un morceau de papier de toute façon.

En fait, bien que la file d'attente rapide soit simple, je suppose que beaucoup de gens ne peuvent pas l'écrire à la main. Est-ce difficile ? Il y a beaucoup de gens qui peuvent l'écrire à la main sur place de plusieurs manières.

Je suis un débutant, mais je peux encore écrire à la main. Après tout, avant l'entretien, j'ai juste délibérément préparé "Écriture rapide par dictée".

Maintenant, analysons et analysons ---- tri rapide.

Contexte

De l'Encyclopédie :

Le tri rapide a été proposé par C. A. R. Hoare en 1962. Son idée de base est de diviser les données à trier en deux parties indépendantes via un tri. Toutes les données d'une partie sont plus petites que toutes les données de l'autre partie, puis d'utiliser cette méthode pour séparer rapidement les deux parties des données. . Tri, l'ensemble du processus de tri peut être effectué [de manière récursive], de sorte que l'ensemble des données devienne une séquence ordonnée.

C’est assez difficile de comprendre ce concept.

Cela peut être compris comme ceci :

Le tri rapide est une version améliorée du tri à bulles. L'ensemble du processus consiste à supprimer et à réparer les éléments, à les démolir et à les réparer, à les démolir et à les réparer, jusqu'à ce que tous les éléments atteignent un état ordonné.

Idée de base :

Prenez d'abord un nombre de la séquence comme numéro de base, puis effectuez un partitionnement par taille ;

Dans le processus de partitionnement, tous les nombres supérieurs à ce nombre sont placés à sa droite, et les nombres inférieurs à ce nombre ; ou égal à celui-ci sont Mettez-les tous à gauche ;

Répétez la deuxième étape pour les intervalles gauche et droit jusqu'à ce qu'il n'y ait qu'un seul nombre dans chaque intervalle et que le tri soit terminé.

Cas de mise en œuvre

Démontons-le étape par étape à travers des images et des textes.

Prenons [4,1,6,2,9,3]ce tableau comme exemple.

Premier passage :

• Divisez d'abord [4,1,6,2,9,3] et sélectionnez l'élément 4 comme point pivot
• Vérifiez si 1 < 4 (point pivot)
• Vérifiez si 6 < (point pivot)
• Vérifiez si 2 < 4 (point pivot)
• 2 < 4 (point pivot) est vrai, échangez l'index 2 avec l'index stocké 6
• Vérifiez si 9 < (point pivot)
• Vérifiez si 3 < 4 (point pivot)
• 3 < 4 (point pivot) Si vrai, stockez les index 3 et 6 Effectuez l'échange
• Échangez le point pivot 4 et le stockage index 3
• À ce moment, le côté gauche du point pivot 4 est inférieur à 4 et le côté droit est supérieur à 4

L'ordre actuel du tableau est [3, 1, 2, 4, 9, 6].

Étape suivante :

• Triez d'abord le côté gauche
• Sélectionnez l'élément 3 comme point pivot
• Vérifiez si 1 < (point pivot)
• Échangez le point pivot 3 et la valeur de l'index de stockage 2
• Maintenant, le point pivot a été divisé à la position triée
• [2,1] Sélectionnez 2 comme point pivot
• Vérifiez si 1 <2 (point pivot)
• Le parcours à gauche est terminé, et le point pivot 2 et l'index de stockage 1 sont échangés
• Il en va de même pour le côté droit...à éviter visuel Je ne décrirai pas la fatigue une par une, mais vous pouvez voir l'image de démonstration dynamique ci-dessous.

2. L'ensemble du processus de la méthode de tri rapide

3.

import java.util.Arrays;

public class QuickSortDemo {
    //四个步骤：
    //1.比较startIndex和endIndex，更喜欢理解为校验
    //2.找出基准
    //3.左边部分排序
    //4.右边排序
    public static void quickSort(int[] arr, int startIndex, int endIndex) {
        if (startIndex < endIndex) {
            //找出基准
            int partition = partition(arr, startIndex, endIndex);
            //分成两边递归进行
            quickSort(arr, startIndex, partition - 1);
            quickSort(arr, partition + 1, endIndex);
        }
    }

    //找基准
    private static int partition(int[] arr, int startIndex, int endIndex) {
        int pivot = arr[startIndex];
        
        int left = startIndex;
        int right = endIndex;
        
        //等于就没有必要排序
        while (left != right) {
            
            while (left < right && arr[right] > pivot) {
                right--;
            }
          
            while (left < right && arr[left] <= pivot) {
                left++;
            }
            //找到left比基准大，right比基准小，进行交换
            if (left < right) {
                swap(arr, left, right);
            }
        }
        //第一轮完成，让left和right重合的位置和基准交换，返回基准的位置
        swap(arr, startIndex, left);
        return left;
    }

    //两数交换
    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int[] a = {3, 1, 2, 4, 9, 6};
        quickSort(a, 0, a.length - 1);
        //输出结果
        System.out.println(Arrays.toString(a));
    }
}

Résultat de sortie :

[1, 2, 3, 4, 6, 9]

Implémentation du code, il est recommandé de le combiner avec l'animation précédente pour la rendre plus facile à comprendre.

Il existe plusieurs façons d'écrire un tri rapide. Si vous êtes intéressé, vous pouvez le rechercher vous-même. Vous pouvez également consulter la façon dont le tri rapide est introduit dans Wikipédia.

4. Analyse de la complexité

Complexité temporelle :

Le pire des cas est que l'élément récupéré à chaque fois est le plus petit/le plus grand élément du tableau. Cette situation est en fait un tri à bulles (Organisez le. ordre d'un élément à chaque fois)

Dans ce cas, la complexité temporelle est facile à calculer, qui est la complexité temporelle du tri à bulles : T[n] = n * (n-1) = n^2 + n ;

Le meilleur cas est O(nlog2n), le processus de dérivation est le suivant :

(formule de complexité temporelle de l'algorithme récursif : T[n] = aT[n/b] + f(n) )

https://img2018.cnblogs.com/blog/1258817/201903/1258817-20190326191158640-601403776.png

Donc la complexité temporelle moyenne est O(nlog2n)

Complexité spatiale :

L'espace utilisé par le tri rapide est O(1), qui est un niveau constant ; et ce qui consomme vraiment de l'espace est l'appel récursif, car chaque récursion doit conserver certaines données :

Dans le cas optimal, la complexité spatiale est : O(log2n ) ; Lorsque le groupe est divisé de manière égale à chaque fois

La complexité spatiale dans le pire des cas est : O(n) ; Elle dégénère dans le cas du tri à bulles

La complexité spatiale moyenne est donc O (log2n)

5. Résumé de la méthode de tri rapide

• Le premier élément est pris comme point pivot par défaut (la confirmation du point pivot fait la distinction entre "méthode de tri rapide" et "méthode de tri aléatoire") Deux algorithmes, tandis que le tri aléatoire classe au hasard un élément comme point pivot 
• Si deux éléments non adjacents sont échangés, plusieurs ordres inverses peuvent être éliminés avec un seul échange, accélérant ainsi le processus de tri.

Postscript

Pour finir, pensez-vous que le tri rapide est utile au travail ? Je ne l'ai jamais utilisé après avoir travaillé pendant près de dix ans, mais je connais l'idée de la file d'attente rapide. Si je ne me prépare pas avant l’entretien, je ne pourrai certainement pas l’écrire de toute façon. Et vous ?

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!