stabilité (stabilité)
Un algorithme de tri est stable, c'est-à-dire que lorsqu'il y a deux enregistrements égaux des clés R et S et que R apparaît avant S dans la liste d'origine, R apparaîtra également avant S dans la liste triée.
Classification de l'algorithme de tri
Les plus courants incluent l'insertion (tri par insertion/tri Hill), l'échange (tri à bulles/tri rapide), la sélection (tri par sélection), la fusion (tri par fusion), etc.
1. Tri par insertion
Le tri par insertion (Tri par insertion) fonctionne en construisant une séquence ordonnée pour les données non triées, il analyse d'avant en arrière dans la séquence triée pour trouver la position correspondante et l'insérer. Dans la mise en œuvre du tri par insertion, le tri sur place est généralement utilisé (c'est-à-dire un tri qui n'utilise que l'espace supplémentaire O(1). Par conséquent, pendant le processus de numérisation d'arrière en avant, il est nécessaire de décaler de manière répétée et progressive le tri par insertion. éléments triés vers l'arrière, fournissant un espace d'insertion pour le dernier élément.
De manière générale, le tri par insertion est implémenté sur les tableaux en utilisant sur place. L'algorithme spécifique est décrit comme suit :
A partir du premier élément, les éléments peuvent être considérés comme triés.
Obtenez l'élément suivant et numérisez d'arrière en avant dans la séquence d'éléments triés.
Si l'élément (trié) est plus grand que le nouvel élément, déplacez l'élément à la position suivante.
Répétez l'étape 3 jusqu'à ce que vous trouviez une position où l'élément trié est inférieur ou égal au nouvel élément.
Après avoir inséré le nouvel élément à cette position.
Répétez les étapes 2 à 5.
Copiez le code comme suit :
public static void insertionSort (int[] données) {
pour (int index = 1; index < data.length; index++) {
clé int = données[index];
int position = indice ;
// décale les valeurs plus grandes vers la droite
while (position > 0 && data[position - 1] > clé) {
données[position] = données[position - 1] ;
position--;
}
données[position] = clé ;
}
}
2. Tri en colline
Shell Sort est un type de tri par insertion. Il s'agit d'une amélioration de l'algorithme de tri par insertion directe. Cette méthode est également appelée réduction du tri incrémentiel, car DL. Shell doit son nom à sa proposition en 1959.
Le tri Hill propose une méthode améliorée basée sur les deux propriétés suivantes du tri par insertion :
Le tri par insertion est très efficace lorsqu'il fonctionne sur des données presque triées, c'est-à-dire qu'il peut atteindre l'efficacité du tri linéaire.
Mais le tri par insertion est généralement inefficace car le tri par insertion ne peut déplacer les données qu'un bit à la fois.
Copiez le code comme suit :
static <E extends Comparable<? super E>> void shellSort(List<E> a) {
entier h = 1 ;
tandis que (h < a.size()/3) h = h*3 + 1; // <O(n^(3/2)) par Knuth,1973> : 1, 4, 13, 40, 121, . ..
pour (; h >= 1; h /= 3)
pour (int i = h; i < a.size(); i++)
pour (int j = i; j >= h && a.get(j).compareTo(a.get(jh)) < 0; j-=h)
Collections.swap(a, j, jh);
}
3. Tri des bulles
Bubble Sort (Bubble Sort, traduit de Taiwan par : Bubble Sort ou Bubble Sort) est un algorithme de tri simple. Il parcourt à plusieurs reprises la séquence à trier, en comparant deux éléments à la fois et en les échangeant s'ils sont dans le mauvais ordre. Le travail de visite du tableau est répété jusqu'à ce qu'aucun échange ne soit plus nécessaire, ce qui signifie que le tableau a été trié. Le nom de cet algorithme vient du fait que les éléments plus petits « flotteront » lentement vers le haut du tableau grâce à l’échange.
L'algorithme de tri à bulles fonctionne comme suit :
Comparez les éléments adjacents et si le premier est supérieur au second, échangez-les tous les deux.
Faites de même pour chaque paire d’éléments adjacents, en commençant par la première paire et en terminant par la dernière paire, auquel cas le dernier élément doit être le plus grand nombre.
Répétez les étapes ci-dessus pour tous les éléments sauf le dernier.
Continuez à répéter les étapes ci-dessus pour de moins en moins d'éléments à chaque fois jusqu'à ce qu'il ne reste plus de paires de nombres à comparer.
Copiez le code comme suit :
public static void bubbleSort(int[] données) {
température int = 0 ;
pour (int i = data.length - 1; i > 0; --i) {
booléen isSort = faux ;
pour (int j = 0; j < i; ++j) {
si (données[j + 1] < données[j]) {
temp = données[j];
données[j] = données[j + 1] ;
données[j + 1] = temp;
estSort = vrai ;
}
}
// Si un échange se produit dans une boucle interne, continuez la comparaison ; si aucun échange ne se produit dans une boucle interne, il est considéré comme trié.
si (!isSort)
casser;
}
}
4. Tri rapide
Le tri rapide est une amélioration du tri à bulles. Proposé par CAR 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.
Le tri rapide utilise la stratégie diviser pour régner pour diviser une liste en deux sous-listes.
Les étapes sont les suivantes :
La sélection d'un élément de la séquence s'appelle un "pivot".
Réorganisez le tableau de sorte que tous les éléments plus petits que la valeur de base soient placés devant la base et que tous les éléments plus grands que la valeur de base soient placés derrière la base (le même nombre peut aller de chaque côté). Une fois cette partition terminée, la base se trouve au milieu de la séquence. C'est ce qu'on appelle une opération de partition.
Triez de manière récursive le sous-tableau d'éléments inférieurs à la valeur de base et le sous-tableau d'éléments supérieurs à la valeur de base.
Copiez le code comme suit :
/*
* des outils plus efficaces pour le tri rapide <br />
* utilisez la valeur médiane gauche, centrale et droite (@see #median()) pour le pivot, et
* la boucle interne plus efficace pour le cœur de l'algorithme.
*/
classe publique Tri rapide {
public static final int CUTOFF = 11 ;
/**
* algorithme de tri rapide <br />
*
* @param arr un tableau d'éléments comparables <br />
*/
public static <T extends Comparable<? super T>> void quicksort(T[] arr) {
quickSort(arr, 0, arr.length - 1);
}
/**
* obtenir la médiane de gauche, du centre et de droite <br />
* commandez-les et masquez le pivot en le plaçant à la fin du tableau <br />
*
* @param arr un tableau d'éléments comparables <br />
* @param a quitté l'index le plus à gauche du sous-tableau <br />.
* @param right l'index le plus à droite du sous-tableau.<br />
* @retour T
*/
public static <T extends Comparable<? super T>> T médian(T[] arr, int gauche, int droite) {
int centre = (gauche + droite) / 2;
si (arr[gauche].compareTo(arr[centre]) > 0)
swapRef(arr, gauche, centre);
si (arr[gauche].compareTo(arr[droite]) > 0)
swapRef(arr, gauche, droite);
si (arr[centre].compareTo(arr[right]) > 0)
swapRef(arr, centre, droite);
swapRef(arr, centre, droite - 1);
return arr[droite - 1];
}
/**
* méthode interne pour trier le tableau avec un algorithme de tri rapide <br />
*
* @param arr un tableau d'éléments comparables <br />
* @param a quitté l'index le plus à gauche du sous-tableau.
* @param right l'index le plus à droite du sous-tableau.
*/
private static <T extends Comparable<? super T>> void quickSort(T[] arr, int left, int right) {
si (gauche + CUTOFF <= droite) {
// trouver le pivot
T pivot = médiane (arr, gauche, droite) ;
// démarre le partitionnement
int i = gauche, j = droite - 1 ;
pour (;;) {
while (arr[++i].compareTo(pivot) < 0);
while (arr[--j].compareTo(pivot) > 0);
si (i < j)
swapRef(arr, je, j);
autre
casser;
}
// échange la référence pivot vers la petite collection.
swapRef(arr, je, droite - 1);
quickSort(arr, left, i - 1); // trie la petite collection.
quickSort(arr, i + 1, right); // trie la grande collection.
} autre {
// si le nombre total est inférieur à CUTOFF, nous utilisons le tri par insertion
// à la place (car c'est beaucoup plus efficace).
Trier(arr, insertion à gauche, à droite) ;
}
}
/**
* méthode pour échanger des références dans un tableau.<br />
*
* @param arr un tableau d'objets <br />
* @param idx1 l'index du premier élément <br />
* @param idx2 l'index du deuxième élément <br />
*/
public static <T> void swapRef(T[] arr, int idx1, int idx2) {
T tmp = arr[idx1];
arr[idx1] = arr[idx2];
arr[idx2] = tmp;
}
/**
* méthode pour trier un sous-tableau du début à la fin avec le tri par insertion
*algorithme.<br />
*
* @param arr un tableau d'éléments comparables <br />
* @param démarre la position de départ <br />
* @param termine la position finale.
*/
public static <T extends Comparable<? super T>> void insertionSort(T[] arr, int start, int end) {
int je;
pour (int j = début + 1; j <= fin; j++) {
T tmp = arr[j];
pour (i = j; i > start && tmp.compareTo(arr[i - 1]) < 0; i--) {
arr[i] = arr[i - 1];
}
arr[je] = tmp;
}
}
private static void printArray(Integer[] c) {
pour (int i = 0; i < c.length; i++)
System.out.print(c[i] + ",");
System.out.println();
}
public static void main (String[] arguments) {
Données entières[] = {10, 4, 9, 23, 1, 45, 27, 5, 2} ;
System.out.println("bubbleSort...");
printArray(données);
tri rapide (données);
printArray(données);
}
}
5. Tri de sélection
Le tri par sélection est un algorithme de tri simple et intuitif. Voici comment cela fonctionne. Tout d’abord, recherchez le plus petit (grand) élément de la séquence non triée et stockez-le au début de la séquence triée. Ensuite, continuez à rechercher le plus petit (grand) élément parmi les éléments non triés restants, puis placez-le à la fin de la séquence. séquence triée. Et ainsi de suite jusqu'à ce que tous les éléments soient triés.
Étant donné que chaque processus de détermination des éléments aura un sous-processus de sélection de la valeur minimale, les gens appellent cela le tri par sélection.
Par exemple, dans la séquence 5 8 5 2 9, nous savons que le premier élément 5 sera échangé avec 2 lors du premier passage. Ensuite, l'ordre relatif des deux 5 dans la séquence d'origine sera détruit, donc le tri de sélection est. pas stable.
Copiez le code comme suit :
public static void selectSort(int[] données) {
int minIndex = 0 ;
température int = 0 ;
pour (int i = 0; i < data.length; i++) {
minIndex = i; //L'index minimum du tableau de données de la zone non ordonnée
for (int j = i + 1; j < data.length; j++) { // Recherche la plus petite donnée dans la zone non ordonnée et enregistre son indice de tableau
si (données[j] < données[minIndex]) {
minIndex = j;
}
}
if (minIndex != i) { // Si la position minimale de la zone non ordonnée n'est pas la première donnée par défaut, échangez-la.
temp = données[i];
données[i] = données[minIndex];
données[minIndex] = temp;
}
}
}
6. Fusionner le tri
Le tri par fusion est un algorithme de tri efficace basé sur des opérations de fusion. Cet algorithme est une application très typique utilisant la méthode diviser pour régner (Divide and Conquer).
Le processus de l’opération de fusion est le suivant :
Demandez de l'espace pour que sa taille soit la somme des deux séquences triées. Cet espace est utilisé pour stocker la séquence fusionnée.
Définissez deux pointeurs, les positions initiales sont les positions de départ des deux séquences triées.
Comparez les éléments pointés par les deux pointeurs, sélectionnez l'élément relativement petit et placez-le dans l'espace de fusion, puis déplacez le pointeur vers la position suivante.
Répétez l'étape 3 jusqu'à ce qu'un pointeur atteigne la fin de la séquence.
Copie tous les éléments restants de l'autre séquence directement à la fin de la séquence fusionnée.
Copiez le code comme suit :
public static int[] mergeSort(int[] arr) {//Merge sort--récursion
si (longueur arr. == 1) {
retour arr;
}
int moitié = arr.length / 2;
int[] arr1 = new int[half];
int[] arr2 = new int[arr.length - half];
System.arraycopy(arr, 0, arr1, 0, arr1.length);
System.arraycopy(arr, moitié, arr2, 0, arr2.length);
arr1 = mergeSort(arr1);
arr2 = mergeSort(arr2);
return mergeSortSub(arr1, arr2);
}
private static int[] mergeSortSub(int[] arr1, int[] arr2) {//Fusionner le sous-programme de tri
int[] résultat = nouveau int[arr1.length + arr2.length];
int je = 0;
entier j = 0 ;
entier k = 0 ;
tandis que (vrai) {
si (arr1[i] < arr2[j]) {
résultat[k] = arr1[i];
si (++i > arr1.length - 1) {
casser;
}
} autre {
résultat[k] = arr2[j];
si (++j > arr2.length - 1) {
casser;
}
}
k++;
}
pour (; je < arr1.length; i++) {
résultat[++k] = arr1[i];
}
pour (; j < arr2.length; j++) {
résultat[++k] = arr2[j];
}
renvoyer le résultat ;
}
Code complet (sauf QuickSort)
Copiez le code comme suit :
paquet com.clzhang.sample.thinking ;
importer java.util.* ;
/**
* Implémentation Java de plusieurs algorithmes de tri courants
* @auteur acer
*
*/
classe publique CommonSort {
/**
* L'algorithme spécifique du tri par insertion est décrit comme suit :
* 1. A partir du premier élément, l'élément peut être considéré comme trié
* 2. Retirez l'élément suivant et numérisez d'arrière en avant dans la séquence d'éléments triés.
* 3. Si l'élément (trié) est plus grand que le nouvel élément, déplacez l'élément à la position suivante
* 4. Répétez l'étape 3 jusqu'à ce que vous trouviez la position où l'élément trié est inférieur ou égal au nouvel élément
* 5. Après avoir inséré le nouvel élément dans cette position
* 6. Répétez les étapes 2 à 5
*/
public static void insertionSort (int[] données) {
pour (int index = 1; index < data.length; index++) {
clé int = données[index];
int position = indice ;
// décale les valeurs plus grandes vers la droite
while (position > 0 && data[position - 1] > clé) {
données[position] = données[position - 1] ;
position--;
}
données[position] = clé ;
}
}
/**
* Tri en colline, veuillez vous référer à Wikipédia pour des idées d'implémentation d'algorithmes adaptées à un grand nombre d'opérations de tri ;
*/
static <E extends Comparable<? super E>> void shellSort(List<E> a) {
entier h = 1 ;
tandis que (h < a.size()/3) h = h*3 + 1; // <O(n^(3/2)) par Knuth,1973> : 1, 4, 13, 40, 121, . ..
pour (; h >= 1; h /= 3)
pour (int i = h; i < a.size(); i++)
pour (int j = i; j >= h && a.get(j).compareTo(a.get(jh)) < 0; j-=h)
Collections.swap(a, j, jh);
}
/**
* Le fonctionnement de l'algorithme de tri à bulles est le suivant :
* 1. Comparez les éléments adjacents. Si le premier est plus grand que le second, échangez-les tous les deux.
* 2. Faites le même travail pour chaque paire d'éléments adjacents, de la première paire au début à la dernière paire à la fin. À ce stade, le dernier élément doit être le plus grand nombre.
* 3. Répétez les étapes ci-dessus pour tous les éléments sauf le dernier.
* 4. Continuez à répéter les étapes ci-dessus pour de moins en moins d'éléments à chaque fois jusqu'à ce qu'il n'y ait plus de paires de nombres à comparer. [1]
*/
public static void bubbleSort (int[] données) {
température int = 0 ;
pour (int i = data.length - 1; i > 0; --i) {
booléen isSort = faux ;
pour (int j = 0; j < i; ++j) {
si (données[j + 1] < données[j]) {
temp = données[j];
données[j] = données[j + 1] ;
données[j + 1] = temp;
estSort = vrai ;
}
}
// Si un échange se produit dans une boucle interne, continuez la comparaison ; si aucun échange ne se produit dans une boucle interne, il est considéré comme trié.
si (!isSort)
casser;
}
}
/**
* L'idée de base du tri par sélection est :
* 1. Pendant le processus de parcours du tableau, si i représente le numéro de séquence actuel qui doit être trié, vous devez trouver la valeur minimale parmi les [i+1...n-1] restants.
* 2.Échangez ensuite la valeur minimale trouvée avec la valeur indiquée par i.
* Étant donné que chaque processus de détermination des éléments aura un sous-processus de sélection de la valeur minimale, les gens l'appellent clairement tri par sélection.
* Données @param
*/
public static void selectSort (int[] données) {
int minIndex = 0 ;
température int = 0 ;
pour (int i = 0; i < data.length; i++) {
minIndex = i; //L'index minimum du tableau de données de la zone non ordonnée
for (int j = i + 1; j < data.length; j++) { // Recherche la plus petite donnée dans la zone non ordonnée et enregistre son indice de tableau
si (données[j] < données[minIndex]) {
minIndex = j;
}
}
if (minIndex != i) { // Si la position minimale de la zone non ordonnée n'est pas la première donnée par défaut, échangez-la.
temp = données[i];
données[i] = données[minIndex];
données[minIndex] = temp;
}
}
}
/**
* Le processus de l'opération de fusion est le suivant :
* 1. Demandez de l'espace pour que sa taille soit la somme des deux séquences triées. Cet espace est utilisé pour stocker la séquence fusionnée.
* 2. Définissez deux pointeurs, les positions initiales sont les positions de départ des deux séquences triées.
* 3. Comparez les éléments pointés par les deux pointeurs, sélectionnez l'élément relativement petit et placez-le dans l'espace de fusion, puis déplacez le pointeur vers la position suivante.
* 4. Répétez l'étape 3 jusqu'à ce qu'un pointeur atteigne la fin de la séquence
* 5. Copiez tous les éléments restants de l'autre séquence directement à la fin de la séquence fusionnée
*/
public static int[] mergeSort(int[] arr) {//Merge sort--récursion
si (longueur arr. == 1) {
retour arr;
}
int moitié = arr.length / 2;
int[] arr1 = new int[half];
int[] arr2 = new int[arr.length - half];
System.arraycopy(arr, 0, arr1, 0, arr1.length);
System.arraycopy(arr, moitié, arr2, 0, arr2.length);
arr1 = mergeSort(arr1);
arr2 = mergeSort(arr2);
return mergeSortSub(arr1, arr2);
}
private static int[] mergeSortSub(int[] arr1, int[] arr2) {//Fusionner le sous-programme de tri
int[] résultat = nouveau int[arr1.length + arr2.length];
int je = 0;
entier j = 0 ;
entier k = 0 ;
tandis que (vrai) {
si (arr1[i] < arr2[j]) {
résultat[k] = arr1[i];
si (++i > arr1.length - 1) {
casser;
}
} autre {
résultat[k] = arr2[j];
si (++j > arr2.length - 1) {
casser;
}
}
k++;
}
pour (; je < arr1.length; i++) {
résultat[++k] = arr1[i];
}
pour (; j < arr2.length; j++) {
résultat[++k] = arr2[j];
}
renvoyer le résultat ;
}
privé statique void printArray(int[] c) {
pour (int i = 0; i < c.length; i++)
System.out.print(c[i] + ",");
System.out.println();
}
public static void main(String []args){
int[] données = {10,4,9,23,1,45,27,5,2} ;
System.out.println("bubbleSort...");
int[] a = data.clone();
printArray(a);
bubbleSort(a);
printArray(a);
System.out.println("selectSort...");
int[] b = data.clone();
printArray(b);
selectTri(b);
printArray(b);
System.out.println("insertionSort...");
int[] c = data.clone();
printArray(c);
insertionSort(c);
printArray(c);
System.out.println("shellSort...");
List<Integer> list = new ArrayList<Integer>();
pour(int i=0;i<data.length;i++)
list.add(data[i]);
System.out.println(liste);
shellSort(liste);
System.out.println(liste);
System.out.println("mergeSort...");
int[] d = data.clone();
printArray(d);
printArray(mergeSort(d));
}
}