importer java.util.Random ;
/**
* Classe de test de tri
*
* La classification des algorithmes de tri est la suivante : 1. Tri par insertion (tri par insertion directe, tri par demi-insertion, tri Hill) ; 2. Tri par échange (tri à bulles, tri rapide) ;
* 3. Tri par sélection (tri par sélection directe, tri par tas) ; 4. Tri par fusion ;
*
* Concernant le choix de la méthode de tri : (1) Si n est petit (comme n≤50), un tri par insertion directe ou par sélection directe peut être utilisé.
* Lorsque la taille des enregistrements est petite, le tri par insertion directe est meilleur ; sinon, comme le nombre d'enregistrements déplacés par sélection directe est inférieur à celui de l'insertion directe, le tri par sélection directe est meilleur.
* (2) Si l'état initial du fichier est fondamentalement en ordre (en référence à un ordre positif), l'insertion directe, la bulle ou le tri rapide aléatoire doivent être utilisés ;
* (3) Si n est grand, une méthode de tri avec une complexité temporelle de O(nlgn) doit être utilisée : tri rapide, tri par tas ou tri par fusion.
*
*/
classe publique Trier {
/**
* Méthode pour initialiser le tableau de test
*
* @renvoie un tableau initialisé
*/
public int[] createArray() {
Aléatoire aléatoire = nouveau Aléatoire();
tableau int[] = nouveau int[10];
pour (int je = 0; je < 10; i++) {
array[i] = random.nextInt(100) - random.nextInt(100); // Génère deux nombres aléatoires et soustrayez-les pour vous assurer qu'il y a des nombres négatifs dans les nombres générés.
}
System.out.println("==========séquence originale==========");
printArray(tableau);
tableau de retour ;
}
/**
* Imprimer les éléments du tableau sur la console
*
* Source @param
*/
public void printArray (int[] données) {
pour (int i : données) {
System.out.print(i + " ");
}
System.out.println();
}
/**
* Échangez les positions des deux éléments spécifiés dans le tableau
*
* Données @param
* @paramx
* @param y
*/
private void swap (int[] données, int x, int y) {
int temp = données[x];
données[x] = données[y];
données[y] = temp;
}
/**
* Tri à bulles ---- un type de tri par échange
* Méthode : comparez deux éléments adjacents et échangez-les si nécessaire. Une fois chaque cycle terminé, le plus grand élément est classé en dernier (par exemple, le tri du plus petit au plus grand). Le cycle suivant effectuera des opérations similaires sur d'autres nombres.
* Performance : nombre de comparaisons O(n^2),n^2/2 ; nombre d'échanges O(n^2),n^2/4 ;
*
* Données @param
* Tableau à trier
* @param sortType
* Type de tri
* @retour
*/
public void bubbleSort(int[] données, String sortType) {
if (sortType.equals("asc")) { // Tri positif, du petit au grand
// Nombre de tours de comparaison
pour (int i = 1; i < data.length; i++) {
// Comparez deux nombres adjacents et le plus grand nombre bouillonnera.
pour (int j = 0; j < data.length - i; j++) {
si (données[j] > données[j + 1]) {
// Echange deux nombres adjacents
échanger (données, j, j + 1);
}
}
}
} else if (sortType.equals("desc")) { // Trier dans l'ordre inverse, du grand au petit
// Nombre de tours de comparaison
pour (int i = 1; i < data.length; i++) {
// Comparez deux nombres adjacents et le plus grand nombre bouillonnera.
pour (int j = 0; j < data.length - i; j++) {
si (données[j] < données[j + 1]) {
// Echange deux nombres adjacents
échanger (données, j, j + 1);
}
}
}
} autre {
System.out.println("Le type de tri que vous avez entré est erroné !");
}
printArray(data);//Afficher la valeur du tableau après le tri des bulles
}
/**
* Méthode de tri par sélection directe ---- un type de tri par sélection
* Méthode : à chaque passage, l'élément le plus petit (ou le plus grand) est sélectionné parmi les éléments de données à trier, et l'ordre est placé à la fin du tableau trié jusqu'à ce que tous les éléments de données à trier soient disposés.
* Performance : nombre de comparaisons O(n^2),n^2/2
* Nombre d'échanges O(n),n
* Le nombre d'échanges est bien inférieur à celui du tri à bulles. Puisque l'échange nécessite plus de temps CPU que la comparaison, le tri par sélection est plus rapide que le tri à bulles.
* Mais lorsque N est relativement grand, le temps CPU requis pour la comparaison domine, donc les performances à ce moment ne sont pas très différentes de celles du tri à bulles, mais elles sont sans aucun doute plus rapides.
*
* Données @param
* Tableau à trier
* @param sortType
* Type de tri
* @retour
*
*/
public void selectSort(int[] données, String sortType) {
if (sortType.equals("asc")) { // Tri positif, du petit au grand
indice int ;
pour (int i = 1; i < data.length; i++) {
indice = 0 ;
pour (int j = 1; j <= data.length - i; j++) {
si (données[j] > données[index]) {
indice = j ;
}
}
//Échangez les deux nombres à la position data.length-i et index (valeur maximale)
swap(données, données.longueur - i, index);
}
} else if (sortType.equals("desc")) { // Trier dans l'ordre inverse, du grand au petit
indice int ;
pour (int i = 1; i < data.length; i++) {
indice = 0 ;
pour (int j = 1; j <= data.length - i; j++) {
si (données[j] < données[index]) {
indice = j ;
}
}
//Échangez les deux nombres à la position data.length-i et index (valeur maximale)
swap(données, données.longueur - i, index);
}
} autre {
System.out.println("Le type de tri que vous avez entré est erroné !");
}
printArray(data);//Afficher la valeur du tableau après le tri par sélection directe
}
/**
*
* Tri par insertion
*
* Méthode : Insérer un enregistrement dans une liste ordonnée triée (éventuellement une liste vide), obtenant ainsi une nouvelle liste ordonnée avec le nombre d'enregistrements augmenté de 1.
* Performance : nombre de comparaisons O(n^2),n^2/4
* Nombre de copies O(n),n^2/4
* Le nombre de comparaisons est moyen entre les deux premiers, et la copie nécessite moins de temps CPU que l'échange, donc les performances sont plus du double de celles du tri à bulles et plus rapides que le tri par sélection.
*
* Données @param
* Tableau à trier
* @param sortType
* Type de tri
*/
public void insertSort(int[] données, String sortType) {
if (sortType.equals("asc")) { // Tri positif, du petit au grand
// Nombre de tours de comparaison
pour (int i = 1; i < data.length; i++) {
// S'assure que les premiers nombres i+1 sont triés
pour (int j = 0; j < i; j++) {
si (données[j] > données[i]) {
// Echangez les deux nombres aux positions j et i
échanger (données, je, j);
}
}
}
} else if (sortType.equals("desc")) { // Trier dans l'ordre inverse, du grand au petit
// Nombre de tours de comparaison
pour (int i = 1; i < data.length; i++) {
// S'assure que les premiers nombres i+1 sont triés
pour (int j = 0; j < i; j++) {
si (données[j] < données[i]) {
// Echangez les deux nombres aux positions j et i
échanger (données, je, j);
}
}
}
} autre {
System.out.println("Le type de tri que vous avez entré est erroné !");
}
printArray(data);//Afficher la valeur du tableau après le tri par insertion
}
/**
*
* Méthode pour inverser un tableau
*
* Données @param
* tableau source
*/
public void reverse (int[] données) {
int longueur = data.length;
int temp = 0;//variable temporaire
pour (int i = 0; i < longueur / 2; i++) {
temp = données[i];
données[i] = données[longueur - 1 - i] ;
données[longueur - 1 - i] = temp;
}
printArray(data);//Afficher la valeur dans le tableau converti
}
/**
*
* Tri rapide
*
* Le tri rapide utilise la stratégie diviser pour régner pour diviser une séquence (liste) en deux sous-séquences (sous-listes).
*
*Les étapes sont :
* 1. Choisissez un élément de la séquence, appelé "pivot",
* 2. Réorganisez la séquence 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 être placé de chaque côté). Après cette division, la donnée se trouve dans sa position finale. C'est ce qu'on appelle une opération de partition.
* 3. 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.
*
* Le cas inférieur de la récursion est lorsque la taille du tableau est zéro ou un, c'est-à-dire qu'il a toujours été trié. Bien qu'il continue de se répéter, cet algorithme se terminera toujours, car à chaque itération (itération), il déplacera au moins un élément vers sa position finale.
*
* Données @param
* Tableau à trier
* @param faible
* @param haut
* @see SortTest#qsort(int[], int, int)
* @see SortTest#qsort_desc(int[], int, int)
*
*/
public void quickSort (int[] données, String sortType) {
if (sortType.equals("asc")) { // Tri positif, du petit au grand
qsort_asc(data, 0, data.length - 1);
} else if (sortType.equals("desc")) { // Trier dans l'ordre inverse, du grand au petit
qsort_desc(data, 0, data.length - 1);
} autre {
System.out.println("Le type de tri que vous avez entré est erroné !");
}
}
/**
*
* Mise en place spécifique du tri rapide, tri dans le bon ordre
*
* Données @param
* @param faible
* @param élevé
*/
private void qsort_asc (int data[], int bas, int haut) {
int je, j, x;
if (low < high) { // Cette condition est utilisée pour mettre fin à la récursion
je = faible ;
j = élevé ;
x = données[i] ;
tandis que (i < j) {
tandis que (je < j && données[j] > x) {
j--; // Trouver le premier nombre inférieur à x de droite à gauche
}
si (je < j) {
données[i] = données[j];
je++;
}
tandis que (je < j && données[i] < x) {
i++; // Trouver le premier nombre supérieur à x de gauche à droite
}
si (je < j) {
données[j] = données[i];
j--;
}
}
données[i] = x;
qsort_asc(données, faible, i - 1);
qsort_asc(données, i + 1, élevé);
}
}
/**
*
* Implémentation spécifique du tri rapide, tri dans l'ordre inverse
*
* Données @param
* @param faible
* @param élevé
*
*/
private void qsort_desc (int data[], int bas, int haut) {
int je, j, x;
if (low < high) { // Cette condition est utilisée pour mettre fin à la récursion
je = faible ;
j = élevé ;
x = données[i] ;
tandis que (i < j) {
tandis que (je < j && données[j] < x) {
j--; // Trouver le premier nombre inférieur à x de droite à gauche
}
si (je < j) {
données[i] = données[j];
je++;
}
tandis que (je < j && données[i] > x) {
i++; // Trouver le premier nombre supérieur à x de gauche à droite
}
si (je < j) {
données[j] = données[i];
j--;
}
}
données[i] = x;
qsort_desc(données, faible, i - 1);
qsort_desc(données, i + 1, élevé);
}
}
/**
*
* Recherche binaire de la position d'un entier spécifique dans un tableau d'entiers (récursif)
*
* La liste linéaire de recherche doit être une liste ordonnée
*
* @paramdataset
* @paramdata
* @parambeginIndex
* @paramendIndex
* @returnindex
*
*/
public int binaireSearch (ensemble de données int [], données int, int startIndex, int endIndex) {
int midIndex = (beginIndex + endIndex) >>> 1; // Équivalent à mid = (low + high)
// / 2, mais l'efficacité sera plus élevée
si (données < dataset[beginIndex] || data > dataset[endIndex] ||beginIndex > endIndex)
renvoie -1 ;
si (données <ensemble de données[midIndex]) {
return binaireSearch (ensemble de données, données, startIndex, midIndex - 1);
} sinon si (données > ensemble de données[midIndex]) {
return binaireSearch (ensemble de données, données, midIndex + 1, endIndex);
} autre {
retourner midIndex ;
}
}
/**
*
* Recherche binaire de la position d'un entier spécifique dans un tableau d'entiers (non récursif)
*
* La liste linéaire de recherche doit être une liste ordonnée
*
* @paramdataset
* @paramdata
* @returnindex
*
*/
public int binaireSearch (ensemble de données int [], données int) {
int débutIndex = 0;
int endIndex = dataset.length - 1;
int midIndex = -1 ;
si (données < dataset[beginIndex] || data > dataset[endIndex] ||beginIndex > endIndex)
renvoie -1 ;
tandis que (beginIndex <= endIndex) {
midIndex = (beginIndex + endIndex) >>> 1; // Équivalent à midIndex =
// (débutIndex +
// endIndex) / 2, mais l'efficacité sera plus élevée
si (données <ensemble de données[midIndex]) {
endIndex = midIndex - 1 ;
} sinon si (données > ensemble de données[midIndex]) {
débutIndex = midIndex + 1 ;
} autre {
retourner midIndex ;
}
}
renvoie -1 ;
}
public static void main (String[] arguments) {
Trier sortTest = new Sort();
int[] array = sortTest.createArray();
System.out.println("==========Après le tri des bulles (ordre positif)==========");
sortTest.bubbleSort(array, "asc");
System.out.println("==========Après le tri des bulles (ordre inverse)==========");
sortTest.bubbleSort(array, "desc");
array = sortTest.createArray();
System.out.println("==========Après avoir inversé le tableau==========");
sortTest.reverse(array);
array = sortTest.createArray();
System.out.println("==========Après tri de sélection (ordre positif)==========");
sortTest.selectSort(array, "asc");
System.out.println("==========Après tri de sélection (ordre inverse)==========");
sortTest.selectSort(array, "desc");
array = sortTest.createArray();
System.out.println("==========Tri après insertion (séquence positive)==========");
sortTest.insertSort(array, "asc");
System.out.println("==========Après tri par insertion (ordre inverse)==========");
sortTest.insertSort(array, "desc");
array = sortTest.createArray();
System.out.println("==========Après un tri rapide (ordre positif)==========");
sortTest.quickSort(array, "asc");
sortTest.printArray(array);
System.out.println("==========Après un tri rapide (ordre inverse)==========");
sortTest.quickSort(array, "desc");
sortTest.printArray(array);
System.out.println("==========Recherche binaire dans le tableau==========");
System.out.println("Le numéro que vous recherchez est à" + sortTest.binarySearch(array, 74)
+ "sièges. (Indice calculé à partir de 0)");
}
}