Cet article présente principalement des exemples de code de divers algorithmes de tri implémentés en Java. Il est relativement complet et peut être utilisé pour des tests personnels. S'il y a des lacunes, veuillez laisser un message pour le signaler.
Tri par demi-insertion
Le tri par demi-insertion est une simple amélioration du tri par insertion directe. La demi-insertion introduite ici consiste en fait à déterminer rapidement la
position d'insertion du i-ième élément en le pliant continuellement en deux. Il s'agit en fait d'un algorithme de recherche : la demi-recherche. La méthode binaireSearch() dans la classe Arrays de Java est l'implémentation de la recherche binaire. Elle est utilisée pour trouver l'élément spécifié dans le tableau spécifié, à condition que le tableau soit déjà dans un état ordonné. L'effet est le même que le tri par insertion directe, sauf qu'il est plus rapide, car
est un tri par demi-insertion qui peut déterminer la position d'insertion du i-ième élément plus rapidement
package interview; /** * @author Administrator * 折半插入排序 */ public class BinaryInsertSort { public static void binaryInsertSort(DataWrap[] data) { System.out.println("开始排序"); int arrayLength = data.length; for (int i = 1; i < arrayLength; i++) { DataWrap temp = data[i]; int low = 0; int high = i - 1; while (low <= high) { int mid = (low + high) / 2; if (temp.compareTo(data[mid]) > 0) { low = mid + 1; } else { high = mid - 1; } } for (int j = i; j > low; j--) { data[j] = data[j - 1]; } data[low] = temp; System.out.println(java.util.Arrays.toString(data)); } } public static void main(String[] args) { DataWrap[] data = { new DataWrap(9, ""), new DataWrap(-16, ""), new DataWrap(21, "*"), new DataWrap(23, ""), new DataWrap(-30, ""), new DataWrap(-49, ""), new DataWrap(21, ""), new DataWrap(30, "*"), new DataWrap(30, "")}; System.out.println("排序之前:\n" + java.util.Arrays.toString(data)); binaryInsertSort(data); System.out.println("排序之后:\n" + java.util.Arrays.toString(data)); } }Résultat :
排序之前: [9, -16, 21*, 23, -30, -49, 21, 30*, 30] 开始排序 [-16, 9, 21*, 23, -30, -49, 21, 30*, 30] [-16, 9, 21*, 23, -30, -49, 21, 30*, 30] [-16, 9, 21*, 23, -30, -49, 21, 30*, 30] [-30, -16, 9, 21*, 23, -49, 21, 30*, 30] [-49, -30, -16, 9, 21*, 23, 21, 30*, 30] [-49, -30, -16, 9, 21, 21*, 23, 30*, 30] [-49, -30, -16, 9, 21, 21*, 23, 30*, 30] [-49, -30, -16, 9, 21, 21*, 23, 30, 30*] 排序之后: [-49, -30, -16, 9, 21, 21*, 23, 30, 30*]
Tri à bulles
package interview; /** * @author Administrator * 冒泡排序 */ public class BubbleSort { public static void bubbleSort(DataWrap[] data) { System.out.println("开始排序"); int arrayLength = data.length; for (int i = 0; i < arrayLength - 1; i++) { boolean flag = false; for (int j = 0; j < arrayLength - 1 - i; j++) { if (data[j].compareTo(data[j + 1]) > 0) { DataWrap temp = data[j + 1]; data[j + 1] = data[j]; data[j] = temp; flag = true; } } System.out.println(java.util.Arrays.toString(data)); if (!flag) break; } } public static void main(String[] args) { DataWrap[] data = { new DataWrap(9, ""), new DataWrap(-16, ""), new DataWrap(21, "*"), new DataWrap(23, ""), new DataWrap(-30, ""), new DataWrap(-49, ""), new DataWrap(21, ""), new DataWrap(30, "*"), new DataWrap(30, "")}; System.out.println("排序之前:\n" + java.util.Arrays.toString(data)); bubbleSort(data); System.out.println("排序之后:\n" + java.util.Arrays.toString(data)); } }Résultat de l'exécution :
排序之前: [9, -16, 21*, 23, -30, -49, 21, 30*, 30] 开始排序 [-16, 9, 21*, -30, -49, 21, 23, 30*, 30] [-16, 9, -30, -49, 21*, 21, 23, 30*, 30] [-16, -30, -49, 9, 21*, 21, 23, 30*, 30] [-30, -49, -16, 9, 21*, 21, 23, 30*, 30] [-49, -30, -16, 9, 21*, 21, 23, 30*, 30] [-49, -30, -16, 9, 21*, 21, 23, 30*, 30] 排序之后: [-49, -30, -16, 9, 21*, 21, 23, 30*, 30]
Tri par seau
Code :
<.>
Résultat
package interview; import java.util.Arrays; /** * @author Administrator * 桶式排序 */ public class BucketSort { public static void bucketSort(DataWrap[] data, int min, int max) { System.out.println("开始排序"); int arrayLength = data.length; DataWrap[] temp = new DataWrap[arrayLength]; int[] buckets = new int[max - min]; for (int i = 0; i < arrayLength; i++) { buckets[data[i].data - min]++; } System.out.println(Arrays.toString(buckets)); for (int i = 1; i < max - min; i++) { buckets[i] = buckets[i] + buckets[i - 1]; } System.out.println(Arrays.toString(buckets)); System.arraycopy(data, 0, temp, 0, arrayLength); for (int k = arrayLength - 1; k >= 0; k--) { data[--buckets[temp[k].data - min]] = temp[k]; } } public static void main(String[] args) { DataWrap[] data = { new DataWrap(9, ""), new DataWrap(5, ""), new DataWrap(-1, ""), new DataWrap(8, ""), new DataWrap(5, "*"), new DataWrap(7, ""), new DataWrap(3, ""), new DataWrap(-3, ""), new DataWrap(1, ""),new DataWrap(3, "*")}; System.out.println("排序之前:\n" + java.util.Arrays.toString(data)); bucketSort(data, -3, 10); System.out.println("排序之后:\n" + java.util.Arrays.toString(data)); } }
排序之前: [9, 5, -1, 8, 5*, 7, 3, -3, 1, 3*] 开始排序 [1, 0, 1, 0, 1, 0, 2, 0, 2, 0, 1, 1, 1] [1, 1, 2, 2, 3, 3, 5, 5, 7, 7, 8, 9, 10] 排序之后: [-3, -1, 1, 3, 3*, 5, 5*, 7, 8, 9]
Tri par tas Code :
Résultat :
package interview; /** * @author Administrator * 堆排序 */ public class HeapSort { public static void heapSort(DataWrap[] data) { System.out.println("开始排序"); int arrayLength = data.length; // 循环建堆 for (int i = 0; i < arrayLength - 1; i++) { // 建堆 builMaxdHeap(data, arrayLength - 1 - i); // 交换堆顶和最后一个元素 swap(data, 0, arrayLength - 1 - i); System.out.println(java.util.Arrays.toString(data)); } } // 对data数组从0到lastIndex建大顶堆 private static void builMaxdHeap(DataWrap[] data, int lastIndex) { // 从lastIndex处节点(最后一个节点)的父节点开始 for (int i = (lastIndex - 1) / 2; i >= 0; i--) { // k保存当前正在判断的节点 int k = i; // 如果当前k节点的子节点存在 while (k * 2 + 1 <= lastIndex) { // k节点的左子节点的索引 int biggerIndex = 2 * k + 1; // 如果biggerIndex小于lastIndex,即biggerIndex +1 // 代表k节点的右子节点存在 if (biggerIndex < lastIndex) { // 如果右子节点的值较大 if (data[biggerIndex].compareTo(data[biggerIndex + 1]) < 0) { // biggerIndex总是记录较大子节点的索引 biggerIndex++; } } // 如果k节点的值小于其较大子节点的值 if (data[k].compareTo(data[biggerIndex]) < 0) { // 交换它们 swap(data, k, biggerIndex); // 将biggerIndex赋给k,开始while循环的下一次循环 // 重新保证k节点的值大于其左、右节点的值 k = biggerIndex; } else { break; } } } } // 交换data数组中i、j两个索引处的元素 private static void swap(DataWrap[] data, int i, int j) { DataWrap temp = data[i]; data[i] = data[j]; data[j] = temp; } public static void main(String[] args) { DataWrap[] data = { new DataWrap(9, ""), new DataWrap(-16, ""), new DataWrap(21, "*"), new DataWrap(23, ""), new DataWrap(-30, ""), new DataWrap(-49, ""), new DataWrap(21, ""), new DataWrap(30, "*"), new DataWrap(30, "")}; System.out.println("排序之前:\n" + java.util.Arrays.toString(data)); heapSort(data); System.out.println("排序之后:\n" + java.util.Arrays.toString(data)); } }
排序之前: [9, -16, 21*, 23, -30, -49, 21, 30*, 30] 开始排序 [-16, 30, 21*, 23, -30, -49, 21, 9, 30*] [-16, 23, 21*, 9, -30, -49, 21, 30, 30*] [21, 9, 21*, -16, -30, -49, 23, 30, 30*] [-49, 9, 21*, -16, -30, 21, 23, 30, 30*] [-30, 9, -49, -16, 21*, 21, 23, 30, 30*] [-30, -16, -49, 9, 21*, 21, 23, 30, 30*] [-49, -30, -16, 9, 21*, 21, 23, 30, 30*] [-49, -30, -16, 9, 21*, 21, 23, 30, 30*] 排序之后: [-49, -30, -16, 9, 21*, 21, 23, 30, 30*]
Tri par insertion directe
Résultats
package interview; public class InsertSort { public static void insertSort(DataWrap[] data){ System.out.println("开始排序"); int arrayLength = data.length; for(int i = 1;i < arrayLength;i++){ DataWrap temp = data[i]; if(data[i].compareTo(data[i-1]) < 0){ int j = i -1; for(;j >= 0 && data[j].compareTo(temp) > 0;j--){ data[j +1] = data[j]; } data[j + 1] = temp; } System.out.println(java.util.Arrays.toString(data)); } } public static void main(String[] args) { DataWrap[] data = { new DataWrap(9, ""), new DataWrap(-16, ""), new DataWrap(21, "*"), new DataWrap(23, ""), new DataWrap(-30, ""), new DataWrap(-49, ""), new DataWrap(21, ""), new DataWrap(30, "*"), new DataWrap(30, "")}; System.out.println("排序之前:\n" + java.util.Arrays.toString(data)); insertSort(data); System.out.println("排序之后:\n" + java.util.Arrays.toString(data)); } }
排序之前: [9, -16, 21*, 23, -30, -49, 21, 30*, 30] 开始排序 [-16, 9, 21*, 23, -30, -49, 21, 30*, 30] [-16, 9, 21*, 23, -30, -49, 21, 30*, 30] [-16, 9, 21*, 23, -30, -49, 21, 30*, 30] [-30, -16, 9, 21*, 23, -49, 21, 30*, 30] [-49, -30, -16, 9, 21*, 23, 21, 30*, 30] [-49, -30, -16, 9, 21*, 21, 23, 30*, 30] [-49, -30, -16, 9, 21*, 21, 23, 30*, 30] [-49, -30, -16, 9, 21*, 21, 23, 30*, 30] 排序之后: [-49, -30, -16, 9, 21*, 21, 23, 30*, 30]
Tri par fusionEfficacité temporelle de l'algorithme : l'algorithme de fusion doit se décomposer et fusionner de manière récursive à chaque fois qu'un tri par fusion est effectué. , merge() est requis Méthode une fois, chaque exécution de merge() nécessite n fois de comparaison, ce qui est pire et nécessite une séquence auxiliaire de la même taille que la séquence d'origine. Stabilité de l'algorithme : Stable
Code :
Résultat :
package interview; /** * @author Administrator * 归并排序 */ public class MergeSort { public static void mergeSort(DataWrap[] data) { // 归并排序 sort(data, 0, data.length - 1); } // 将索引从left到right范围的数组元素进行归并排序 private static void sort(DataWrap[] data, int left, int right) { if(left < right){ //找出中间索引 int center = (left + right)/2; sort(data,left,center); sort(data,center+1,right); //合并 merge(data,left,center,right); } } // 将两个数组进行归并,归并前两个数组已经有序,归并后依然有序 private static void merge(DataWrap[] data, int left, int center, int right) { DataWrap[] tempArr = new DataWrap[data.length]; int mid = center + 1; int third = left; int temp = left; while (left <= center && mid <= right) { if (data[left].compareTo(data[mid]) <= 0) { tempArr[third++] = data[left++]; } else { tempArr[third++] = data[mid++]; } } while (mid <= right) { tempArr[third++] = data[mid++]; } while (left <= center) { tempArr[third++] = data[left++]; } while (temp <= right) { data[temp] = tempArr[temp++]; } } public static void main(String[] args) { DataWrap[] data = { new DataWrap(9, ""), new DataWrap(-16, ""), new DataWrap(21, "*"), new DataWrap(23, ""), new DataWrap(-30, ""), new DataWrap(-49, ""), new DataWrap(21, ""), new DataWrap(30, "*"), new DataWrap(30, "") }; System.out.println("排序之前:\n" + java.util.Arrays.toString(data)); mergeSort(data); System.out.println("排序之后:\n" + java.util.Arrays.toString(data)); } }
排序之前: [9, -16, 21*, 23, -30, -49, 21, 30*, 30] 排序之后: [-49, -30, -16, 9, 21*, 21, 23, 30*, 30]
Tri RadixLe tri Radix n'est plus une méthode de tri classique, il s'agit plutôt d'un tri L'application de la méthode, le tri par base doit dépendre d’une autre méthode de tri.
L'idée générale du tri par base est de diviser les données à trier en plusieurs mots-clés pour le tri. En d'autres termes, l'essence du tri par base est le tri multi-mots-clés.
. . . Ensuite, triez les données à trier selon les sous-mots-clés. Il existe deux solutions lors du tri multi-mots clés :
Méthode d'ordre le moins élevé LSD
Comparez la méthode MSD et la méthode LSD. De manière générale, la méthode LSD est plus simple que la méthode MSD, car la méthode LSD alloue et collecte plusieurs fois du début à la fin. Le nombre d'exécutions
dépend de la méthode. mots-clés constitutifs. Quels sont les composants de la valeur ? La règle MSD peut être plus compliquée à gérer le tri indépendant de chaque séquence et sous-séquence.
Code :
Résultat
package interview; import java.util.Arrays; /** * @author Administrator * 基数排序 */ public class MultiKeyRadixSort { public static void radixSort(int[] data, int radix, int d) { System.out.println("开始排序:"); int arrayLength = data.length; int[] temp = new int[arrayLength]; int[] buckets = new int[radix]; for (int i = 0, rate = 1; i < d; i++) { // 重置count数组,开始统计第二个关键字 Arrays.fill(buckets, 0); // 当data数组的元素复制到temp数组中进行缓存 System.arraycopy(data, 0, temp, 0, arrayLength); for (int j = 0; j < arrayLength; j++) { int subKey = (temp[j] / rate) % radix; buckets[subKey]++; } for (int j = 1; j < radix; j++) { buckets[j] = buckets[j] + buckets[j - 1]; } for (int m = arrayLength - 1; m >= 0; m--) { int subKey = (temp[m] / rate) % radix; data[--buckets[subKey]] = temp[m]; } System.out.println("对" + rate + "位上子关键字排序:" + java.util.Arrays.toString(data)); rate *= radix; } } public static void main(String[] args) { int[] data = { 1100, 192, 221, 12, 13 }; System.out.println("排序之前:\n" + java.util.Arrays.toString(data)); radixSort(data, 10, 4); System.out.println("排序之后:\n" + java.util.Arrays.toString(data)); } }
排序之前: [1100, 192, 221, 12, 13] 开始排序: 对1位上子关键字排序:[1100, 221, 192, 12, 13] 对10位上子关键字排序:[1100, 12, 13, 221, 192] 对100位上子关键字排序:[12, 13, 1100, 192, 221] 对1000位上子关键字排序:[12, 13, 192, 221, 1100] 排序之后: [12, 13, 192, 221, 1100]
Tri rapideCode :
Résultat
package interview; /** * @author Administrator * 快速排序 */ public class QuickSort { private static void swap(DataWrap[] data, int i, int j) { DataWrap temp = data[i]; data[i] = data[j]; data[j] = temp; } private static void subSort(DataWrap[] data, int start, int end) { if (start < end) { DataWrap base = data[start]; int i = start; int j = end + 1; while (true) { while (i < end && data[++i].compareTo(base) <= 0) ; while (j > start && data[--j].compareTo(base) >= 0) ; if (i < j) { swap(data, i, j); } else { break; } } swap(data, start, j); subSort(data, start, j - 1); subSort(data, j + 1, end); } } public static void quickSort(DataWrap[] data){ subSort(data,0,data.length-1); } public static void main(String[] args) { DataWrap[] data = { new DataWrap(9, ""), new DataWrap(-16, ""), new DataWrap(21, "*"), new DataWrap(23, ""), new DataWrap(-30, ""), new DataWrap(-49, ""), new DataWrap(21, ""), new DataWrap(30, "*"), new DataWrap(30, "") }; System.out.println("排序之前:\n" + java.util.Arrays.toString(data)); quickSort(data); System.out.println("排序之后:\n" + java.util.Arrays.toString(data)); } }
排序之前: [9, -16, 21*, 23, -30, -49, 21, 30*, 30] 排序之后: [-49, -30, -16, 9, 21, 21*, 23, 30*, 30]
Tri par sélection directeCode :
package interview; /** * @author Administrator * 直接选择排序 */ public class SelectSort { public static void selectSort(DataWrap[] data) { System.out.println("开始排序"); int arrayLength = data.length; for (int i = 0; i < arrayLength - 1; i++) { for (int j = i + 1; j < arrayLength; j++) { if (data[i].compareTo(data[j]) > 0) { DataWrap temp = data[i]; data[i] = data[j]; data[j] = temp; } } System.out.println(java.util.Arrays.toString(data)); } } public static void main(String[] args) { DataWrap[] data = { new DataWrap(9, ""), new DataWrap(-16, ""), new DataWrap(21, "*"), new DataWrap(23, ""), new DataWrap(-30, ""), new DataWrap(-49, ""), new DataWrap(21, ""), new DataWrap(30, "*"), new DataWrap(30, "") }; System.out.println("排序之前:\n" + java.util.Arrays.toString(data)); selectSort(data); System.out.println("排序之后:\n" + java.util.Arrays.toString(data)); } }
排序之前: [9, -16, 21*, 23, -30, -49, 21, 30*, 30] 开始排序 [-49, 9, 21*, 23, -16, -30, 21, 30*, 30] [-49, -30, 21*, 23, 9, -16, 21, 30*, 30] [-49, -30, -16, 23, 21*, 9, 21, 30*, 30] [-49, -30, -16, 9, 23, 21*, 21, 30*, 30] [-49, -30, -16, 9, 21*, 23, 21, 30*, 30] [-49, -30, -16, 9, 21*, 21, 23, 30*, 30] [-49, -30, -16, 9, 21*, 21, 23, 30*, 30] [-49, -30, -16, 9, 21*, 21, 23, 30*, 30] 排序之后: [-49, -30, -16, 9, 21*, 21, 23, 30*, 30]
Tri des collines Code :
Résultat :
package interview; /** * @author Administrator * Shell排序 */ public class ShellSort { public static void ShellSort(DataWrap[] data) { System.out.println("开始排序"); int arrayLength = data.length; int h = 1; /** * 将数组分割成若干个子序列 */ while (h <= arrayLength / 3) { h = h * 3 + 1; System.out.println("h的结果:" + h); } while (h > 0) { System.out.println("===h的值:" + h + "==="); /** * 将分成的若干子序列进行直接插入排序 */ for (int i = h; i < arrayLength; i++) { DataWrap temp = data[i]; if (data[i].compareTo(data[i - h]) < 0) { int j = i - h; for (; j >= 0 && data[j].compareTo(temp) > 0; j -= h) { data[j + h] = data[j]; } data[j + h] = temp; } System.out.println(java.util.Arrays.toString(data)); } h = (h - 1) / 3; } } public static void main(String[] args) { DataWrap[] data = { new DataWrap(9, ""), new DataWrap(-16, ""), new DataWrap(21, "*"), new DataWrap(23, ""), new DataWrap(-30, ""), new DataWrap(-49, ""), new DataWrap(21, ""), new DataWrap(30, "*"), new DataWrap(30, "")}; System.out.println("排序之前:\n" + java.util.Arrays.toString(data)); ShellSort(data); System.out.println("排序之后:\n" + java.util.Arrays.toString(data)); } }
排序之前: [9, -16, 21*, 23, -30, -49, 21, 30*, 30] 开始排序 h的结果:4 ===h的值:4=== [-30, -16, 21*, 23, 9, -49, 21, 30*, 30] [-30, -49, 21*, 23, 9, -16, 21, 30*, 30] [-30, -49, 21*, 23, 9, -16, 21, 30*, 30] [-30, -49, 21*, 23, 9, -16, 21, 30*, 30] [-30, -49, 21*, 23, 9, -16, 21, 30*, 30] ===h的值:1=== [-49, -30, 21*, 23, 9, -16, 21, 30*, 30] [-49, -30, 21*, 23, 9, -16, 21, 30*, 30] [-49, -30, 21*, 23, 9, -16, 21, 30*, 30] [-49, -30, 9, 21*, 23, -16, 21, 30*, 30] [-49, -30, -16, 9, 21*, 23, 21, 30*, 30] [-49, -30, -16, 9, 21*, 21, 23, 30*, 30] [-49, -30, -16, 9, 21*, 21, 23, 30*, 30] [-49, -30, -16, 9, 21*, 21, 23, 30*, 30] 排序之后: [-49, -30, -16, 9, 21*, 21, 23, 30*, 30]
Outils requis :
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!