Comment utiliser le tri bitmap Java

Copiez le code comme suit :

/**
* Effectue un tri sur la section du tableau entre les indices donnés
* en utilisant un tri par fusion avec un algorithme de recherche exponentielle (dans lequel la fusion
* est effectué par recherche exponentielle). Les performances n*log(n) sont garanties.
* et dans le cas moyen, ce sera plus rapide que n'importe quel tri par fusion dans lequel le
* la fusion s'effectue par recherche linéaire.
*
* @param dans -
* le tableau à trier.
* @param dehors -
* le résultat, tableau trié.
* @param début
* l'indice de départ
* @param fin
* l'indice de fin + 1
*/
@SuppressWarnings("non coché")
private static void mergeSort(Object[] in, Object[] out, int start,
avoir l'intention) {
int len ​​​​= fin - début ;
// utilise le tri par insertion pour les petits tableaux
si (len <= SIMPLE_LENGTH) {
pour (int i = début + 1; i < fin; i++) {
Comparable<Object> current = (Comparable<Object>) out[i];
Objet précédent = out[i - 1];
if (current.compareTo(prev) < 0) {
int j = je;
faire {
out[j--] = précédent;
} while (j > démarrer
&& current.compareTo(prev = out[j - 1]) < 0);
out[j] = courant ;
}
}
retour;
}
int med = (fin + début) >>> 1;
mergeSort(out, in, start, med);
mergeSort(out, in, med, end);

// fusion

// si les tableaux sont déjà triés - pas de fusion
if (((Comparable<Object>) in[med - 1]).compareTo(in[med]) <= 0) {
System.arraycopy(in, start, out, start, len);
retour;
}
int r = med, je = début ;

// utilise la fusion avec la recherche exponentielle
faire {
Comparable<Object> fromVal = (Comparable<Object>) in[start];
Comparable<Object> rVal = (Comparable<Object>) in[r];
si (fromVal.compareTo(rVal) <= 0) {
int l_1 = find(in, rVal, -1, start + 1, med - 1);
int toCopy = l_1 - début + 1 ;
System.arraycopy(in, start, out, i, toCopy);
i += toCopier ;
out[i++] = rVal;
r++;
début = l_1 + 1 ;
} autre {
int r_1 = find(in, fromVal, 0, r + 1, end - 1);
int toCopie = r_1 - r + 1;
System.arraycopy(in, r, out, i, toCopy);
i += toCopier ;
out[i++] = fromVal;
démarrer++ ;
r = r_1 + 1 ;
}
} while ((end - r) > 0 && (med - start) > 0);

// copie le reste du tableau
si ((fin - r) <= 0) {
System.arraycopy(in, start, out, i, med - start);
} autre {
System.arraycopy(in, r, out, i, end - r);
}
}

Copiez le code comme suit :

classe publique javaUniqueSort {
public static int[] temp = new int[1000001];
public static List<Integer> tempList = new ArrayList<Integer>();
nombre d'ints statiques publics ;

public static void main (final String[] arguments) {
List<Integer> firstNum = new ArrayList<Integer>();
List<Integer> secondNum = new ArrayList<Integer>();

pour (int i = 1; i <= 1000000; i++) {
firstNum.add(i);
secondNum.add(i);
}

Collections.shuffle(firstNum);
Collections.shuffle(secondNum);

getStartTime();
Collections.sort(firstNum);
getEndTime("exécution du tri Java ");

getStartTime();
secondNum = uniqueSort(secondNum);
getEndTime("Exécution uniqueSort ");

}

public static List<Integer> uniqueSort(final List<Integer> uniqueList) {
javaUniqueSort.tempList.clear();
pour (int i = 0; i < javaUniqueSort.temp.length; i++) {
javaUniqueSort.temp[i] = 0;
}
pour (int i = 0; i < uniqueList.size(); i++) {
javaUniqueSort.temp[uniqueList.get(i)] = 1;
}
pour (int i = 0; i < javaUniqueSort.temp.length; i++) {
if (javaUniqueSort.temp[i] == 1) {
javaUniqueSort.tempList.add(i);
}
}

renvoie javaUniqueSort.tempList ;
}

public static void getStartTime() {
javaShuffle.start = System.nanoTime();
}

public static void getEndTime (final String s) {
javaShuffle.end = System.nanoTime();
System.out.println(s + ": " + (javaShuffle.end - javaShuffle.start) + "ns");
}
}

Durée de fonctionnement :

Temps d'exécution du tri Java : 1257737334ns
Durée d'exécution de uniqueSort : 170228290ns
Temps d'exécution du tri Java : 1202749828ns
Durée d'exécution de uniqueSort : 169327770ns

Copiez le code comme suit :

classe publique javaDuplicateSort {
public static List<Integer> tempList = new ArrayList<Integer>();
nombre d'ints statiques publics ;

public static void main (final String[] arguments) {
Aléatoire aléatoire = nouveau Aléatoire();
List<Integer> firstNum = new ArrayList<Integer>();
List<Integer> secondNum = new ArrayList<Integer>();

pour (int je = 1; je <= 100000; i++) {
firstNum.add(i);
secondNum.add(i);
firstNum.add(random.nextInt(i + 1));
secondNum.add(random.nextInt(i + 1));
}
Collections.shuffle(firstNum);
Collections.shuffle(secondNum);

getStartTime();
Collections.sort(firstNum);
getEndTime("exécution du tri Java ");

getStartTime();
secondNum = uniqueSort(secondNum);
getEndTime("Exécution uniqueSort ");

}

public static List<Integer> uniqueSort(final List<Integer> uniqueList) {
javaDuplicateSort.tempList.clear();
int[] temp = nouveau int[200002];
pour (int i = 0; i < temp.length; i++) {
temp[i] = 0;
}
pour (int i = 0; i < uniqueList.size(); i++) {
temp[uniqueList.get(i)]++;
}
pour (int i = 0; i < temp.length; i++) {
pour (int j = temp[i]; j > 0; j--) {
javaDuplicateSort.tempList.add(i);
}
}

renvoie javaDuplicateSort.tempList ;
}

public static void getStartTime() {
javaShuffle.start = System.nanoTime();
}

public static void getEndTime (final String s) {
javaShuffle.end = System.nanoTime();
System.out.println(s + ": " + (javaShuffle.end - javaShuffle.start) + "ns");
}
}