Tri rapide C#

Tri rapide C#

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace Sort
{
    class QuickSorter
    {
        private static int[] myArray;
        private static int arraySize;
        public static int[] Sort(int[] a)
        {
            arraySize = a.Length;
            QuickSort(a, 0,arraySize- 1);
	    return a;
        }
        private static void QuickSort(int[] myArray, int left, int right)
        {
            int i, j, s;
            if (left < right)
            {
                i = left - 1;
                j = right + 1;
                s = myArray[(i + j) / 2];
                while (true)
                {
                    while (myArray[++i] < s) ;
                    while (myArray[--j] > s) ;
                    if (i >= j)
                        break;
                    Swap(ref myArray[i], ref myArray[j]);
                }
                QuickSort(myArray, left, i - 1);
                QuickSort(myArray, j + 1, right);
            }
        }
        private static void Swap(ref int left, ref int right)
        {
            int temp;
            temp = left;
            left = right;
            right = temp;
        }
    }
}

L'idée du tri rapide :

Supposons que le tableau à trier soit A[0]...A[N-1], sélectionnez d'abord n'importe quelle donnée (généralement le premier numéro du tableau est sélectionné) comme données clés, puis tous les nombres plus petits sont placés devant, et tous les nombres plus grands sont placés après. Ce processus est appelé un. tri rapide. Il convient de noter que le tri rapide n'est pas un algorithme de tri stable, c'est-à-dire que les positions relatives de plusieurs valeurs identiques peuvent changer à la fin de l'algorithme.

L'algorithme de tri rapide en un seul passage est :

1) Définissez deux variables i et j Lorsque le tri commence : i=0, j=N-1 ; >2) Utilisez le premier élément du tableau comme données clés et attribuez-le à key, c'est-à-dire key=A[0]

3) Recherchez vers l'avant à partir de j, c'est-à-dire recherchez vers l'avant depuis l'arrière ; (j- -), trouvez la première valeur A[j] qui est inférieure à la clé et échangez l'élément avec la valeur clé avec A[j] ;

4) Recherchez en arrière en commençant par i, c'est-à-dire , en commençant par l'avant et en remontant vers l'arrière Recherchez (i), trouvez le premier A[i] supérieur à la clé et échangez l'élément avec la clé de valeur avec A[i]; 🎜>

6) Répétez les étapes 3, 4 et 5 jusqu'à ce que i=j ; (Aux étapes 3 et 4, aucune valeur répondant aux conditions n'est trouvée, c'est-à-dire lorsque A[j] dans 3 n'est pas inférieur à key, et A[j] dans 4 n'est pas supérieur à key Changez les valeurs de j et i de sorte que j=j-1 et i=i 1 jusqu'à ce qu'une valeur qui remplisse les conditions soit trouvée Lors de l'échange, les positions. des pointeurs i et j restent inchangés. De plus, le processus de i==j Cela doit se produire lorsque i ou j- est terminé, moment auquel la boucle se termine).

Exemple :

Prenons un tableau comme exemple et prenez le premier nombre de la plage comme numéro de base.

i = 3; j = 7 .

Partez de j et cherchez vers l'avant. Lorsque j=5, si les conditions sont remplies, déterrez a[5] et remplissez-le dans le trou précédent, a[3] = a[5] ;

Commencez à partir de i et recherchez en arrière Lorsque i=5, quittez car i==j.

À ce moment, i = j = 5, et a[5] se trouve être le trou creusé la dernière fois, alors remplissez X dans a[5]. Le tableau

devient :

Ce qui précède est le contenu du tri rapide C#. Pour plus de contenu connexe, veuillez faire attention au site Web PHP chinois (www. .php.cn) !