Cet article explique principalement le processus de tri des tas sous forme d'images, puis utilise du code Java pour implémenter le tri des tas et analyser la complexité temporelle. Il a une certaine valeur de référence et les amis intéressés peuvent en apprendre davantage.
1. Introduction2. Tri par tas graphique 3. Java implémentation du code et analyse de la complexité temporelle 4. Résumé
La file d'attente prioritaire peut être utilisée pour trier en un temps O(NlogN), tout comme l'idée utilisée pour résoudre le problème topK dans l'article précédent, cette idée est un tri par tas.
Si vous ne connaissez pas le tas binaire, vous pouvez jeter un œil à la file d'attente prioritaire illustrée (tas)
Nous partons du tableau Il commence à l'index 0, contrairement au tas binaire qui commence à l'index 1 du tableau.
Implémentation du code
public class Heapsort { public static void main(String[] args) { Integer[] integers = {7, 1, 13, 9, 11, 5, 8}; System.out.println("原序列:" + Arrays.toString(integers)); heapsort(integers); System.out.println("排序后:" + Arrays.toString(integers)); } public static <T extends Comparable<? super T>> void heapsort(T[] a) { if (null == a || a.length == 0) { throw new RuntimeException("数组为null或长度为0"); } //构建堆 for (int i = a.length / 2 - 1; i >= 0; i--) { percDown(a, i, a.length); } //deleteMax for (int i = a.length - 1; i > 0; i--) { swapReferences(a, 0, i); percDown(a, 0, i); } } /** * 下滤的方法 * * @param a:待排序数组 * @param i:从哪个索引开始下滤 * @param n :二叉堆的逻辑大小 * @param <T> */ private static <T extends Comparable<? super T>> void percDown(T[] a, int i, int n) { int child; T tmp; for (tmp = a[i]; leftChild(i) < n; i = child) { child = leftChild(i); if (child != n - 1 && a[child].compareTo(a[child + 1]) < 0) { child++; } if (tmp.compareTo(a[child]) < 0) { a[i] = a[child]; } else { break; } } a[i] = tmp; } private static int leftChild(int i) { return 2 * i + 1; } /** * 交换数组中两个位置的元素 * * @param a:目标数组 * @param index1 :第一个元素下标 * @param index2 :第二个元素下标 * @param <T> */ private static <T> void swapReferences(T[] a, int index1, int index2) { T tmp = a[index1]; a[index1] = a[index2]; a[index2] = tmp; } } //输出结果 //原序列:[7, 1, 13, 9, 11, 5, 8] //排序后:[1, 5, 7, 8, 9, 11, 13]
Complexité temporelle : buildHeap Utilisation O(N) temps, le filtrage des éléments nécessite O(logN) et le filtrage N-1 fois est requis, donc un total de O(N+(N-1)logN) = O(NlogN) est requis. Comme le montre le processus, quel que soit le meilleur ou le pire moment, la complexité du tri des tas est stable à O(NlogN).
Complexité spatiale : Utilisant son propre stockage, il est sans aucun doute O(1).
Cet article explique clairement le processus de tri des tas en dessinant une image Tas le tri est d'abord trié par tas, puis trié par deleteMax. Sa complexité spatiale est O(1) et sa complexité temporelle est stable à O(NlogN).
Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!