Préface : L'idée originale de tomber amoureux de Java n'a jamais été oubliée : « Partager mes résultats d'apprentissage, quelle que soit la profondeur de la technologie ultérieure, il est important de jeter de bonnes bases.
Classe d'outils Swapper, cette classe d'outils sera utilisée dans les algorithmes ultérieurs :
Copiez le code comme suit :
paquet com.meritit.sortord.util;
/**
* Un utilitaire pour échanger l'élément de remorquage du tableau
*
* @auteur ysjian
* @version 1.0
* @email [email protected]
* @QQ646633781
* @téléphone 18192235667
* @csdnBlog http://blog.csdn.net/ysjian_pingcx
* @createTime 20/12/2013
* @copyRight Mérite
*/
Échangeur de classe publique {
privéSwapper() {
}
/**
* Échanger les éléments de remorquage du tableau
*
* @param oneIndex
* un indice
* @param un autreIndex
* un autre indice
* Tableau @param
* le tableau à échanger
* @exception NullPointerException
* si le tableau est nul
*/
public static <T extends Comparable<T>> void swap(int oneIndex,
int anotherIndex, tableau T[]) {
si (tableau == null) {
throw new NullPointerException("entrée de valeur nulle");
}
checkIndexs(oneIndex, anotherIndex, array.length);
T temp = tableau[oneIndex];
tableau[unIndex] = tableau[un autreIndex];
array[anotherIndex] = temp;
}
/**
* Échanger les éléments de remorquage du tableau
*
* @param oneIndex
* un indice
* @param un autreIndex
* un autre indice
* Tableau @param
* le tableau à échanger
* @exception NullPointerException
* si le tableau est nul
*/
public static void swap (int oneIndex, int anotherIndex, tableau int[]) {
si (tableau == null) {
throw new NullPointerException("entrée de valeur nulle");
}
checkIndexs(oneIndex, anotherIndex, array.length);
int temp = tableau[unIndex];
tableau[unIndex] = tableau[un autreIndex];
array[anotherIndex] = temp;
}
/**
* Vérifiez l'index s'il est dans l'arrangement
*
* @param oneIndex
* un indice
* @param un autreIndex
* un autre indice
* @param arrayLength
* la longueur du tableau
* @exception IllegalArgumentException
* si l'index est hors plage
*/
checkIndexs de vide statique privé (int oneIndex, int anotherIndex,
int longueur du tableau) {
si (oneIndex < 0 || anotherIndex < 0 || oneIndex >= arrayLength
|| un autreIndex >= longueur du tableau) {
lancer une nouvelle IllegalArgumentException (
"Arguments illégaux pour les index de remorquage [" + oneIndex + ","
+ unIndex + "]");
}
}
}
Tri par insertion directe, InsertionSortord :
Copiez le code comme suit :
package com.meritit.sortord.insertion;
/**
* Ordre de tri des insertions, la complexité temporelle est O(n2)
*
* @auteur ysjian
* @version 1.0
* @email [email protected]
* @QQ646633781
* @téléphone 18192235667
* @csdnBlog http://blog.csdn.net/ysjian_pingcx
* @createTime 31/12/2013
* @copyRight Mérite
* @depuis 1.5
*/
classe publique InsertionSortord {
private static final InsertionSortord INSTANCE = new InsertionSortord();
Private InsertionSortord() {
}
/**
* Obtenez l'instance de InsertionSortord, une seule instance
*
* @return la seule instance
*/
public static InsertionSortord getInstance() {
retourner INSTANCE ;
}
/**
* Trier le tableau de <code>int</code> avec l'ordre de tri par insertion
*
* Tableau @param
* le tableau de int
*/
public void doSort(int... tableau) {
if (array != null && array.length > 0) {
int longueur = tableau.longueur;
// la circulation commence à 1, la valeur de l'indice 0 est référence
pour (int i = 1; i < longueur; i++) {
si (tableau[i] < tableau[i - 1]) {
// si la valeur à l'index i est inférieure à la valeur à l'index i-1
int poste vacant = i; // enregistre le poste vacant comme i
// définit une sentinelle comme valeur à l'index i
int sentinelle = tableau[i];
// circulation des clés, à partir de l'index i-1,
pour (int j = i - 1; j >= 0; j--) {
if (array[j] > sentinelle) {
/*
* si la valeur actuelle de l'indice dépasse la
* Sentinelle, puis reculez, enregistrez le nouveau
*poste vacant en tant que j
*/
tableau[j + 1] = tableau[j];
poste vacant = j;
}
}
// définit la sentinelle sur le nouveau poste vacant
array[vacance] = sentinelle;
}
}
}
}
/**
* Trier le tableau de <code>T</code> générique avec ordre de tri par insertion
*
* Tableau @param
* la gamme de génériques
*/
public <T extends Comparable<T>> void doSortT(T[] array) {
if (array != null && array.length > 0) {
int longueur = tableau.longueur;
pour (int i = 1; i < longueur; i++) {
if (array[i].compareTo(array[i - 1]) < 0) {
T sentinelle = tableau[i];
poste vacant int = i ;
pour (int j = i - 1; j >= 0; j--) {
if (array[j].compareTo(sentry) > 0) {
tableau[j + 1] = tableau[j];
poste vacant = j;
}
}
array[vacance] = sentinelle;
}
}
}
}
}
Test TestInsertionSortord :
Copiez le code comme suit :
package com.meritit.sortord.insertion;
importer java.util.Arrays ;
/**
* Tester l'ordre de tri des insertions
*
* @auteur ysjian
* @version 1.0
* @email [email protected]
* @QQ646633781
* @téléphone 18192235667
* @createTime 31/12/2013
* @copyRight Mérite
*/
classe publique TestInsertionSortord {
public static void main (String[] arguments) {
InsertionSortord insertSort = InsertionSortord.getInstance();
tableau int[] = { 3, 5, 4, 2, 6 };
System.out.println(Arrays.toString(array));
insertSort.doSort(array);
System.out.println(Arrays.toString(array));
System.out.println("---------------");
Entier[] tableau1 = { 3, 5, 4, 2, 6 } ;
System.out.println(Arrays.toString(array1));
insertSort.doSortT(array1);
System.out.println(Arrays.toString(array1));
}
}