L'algorithme de tri est utilisé dans de nombreux endroits. J'ai récemment revu l'algorithme et je l'ai simplement implémenté moi-même. Je l'enregistre par la présente pour sauvegarder du matériel pour une révision future.
Sans plus tarder, examinons un par un les algorithmes de tri classiques :
1 Tri par sélection
L'idée de base du tri par sélection est de parcourir. le tableau avec i représente le numéro de séquence actuel qui doit être trié, vous devez trouver la valeur minimale parmi les [i...n-1] restants, puis échanger la valeur minimale trouvée avec la valeur pointée par i. Étant donné que chaque processus de détermination des éléments aura un sous-processus de sélection de la valeur maximale, les gens appellent cela le tri par sélection. Prenons un exemple :
Initial : [38, 17, 16, 16, 7, 31, 39, 32, 2, 11]
i = 0 : [2, 17, 16 , 16, 7, 31, 39, 32, 38, 11] (0e [38]<->8e [2])
i = 1 : [2, 7, 16, 16, 17 , 31, 39, 32, 38, 11] (1er [38]<->4e [17])
i = 2 : [2, 7, 11, 16, 17, 31, 39 , 32, 38, 16 ] (2e [11]<->9e [16])
i = 3 : [2, 7, 11, 16, 17, 31, 39, 32, 38 , 16] (aucun échange requis)
i = 4 : [2, 7, 11, 16, 16, 31, 39, 32, 38, 17] (4e [17]<-> 9e [16])
i = 5 : [2, 7, 11, 16, 16, 17, 39, 32, 38, 31] (5e [31]<->9e [17] )
i = 6 : [2, 7, 11, 16, 16, 17, 31, 32, 38, 39] (6e [39]<->9e [31])
i = 7 : [2, 7, 11, 16, 16, 17, 31, 32, 38, 39] (aucun échange requis)
i = 8 : [2, 7, 11, 16 , 16, 17, 31, 32, 38, 39] (aucun échange requis)
i = 9 : [2, 7, 11, 16, 16, 17, 31, 32, 38, 39] ( aucun échange requis Exchange)
Comme le montre l'exemple, au fur et à mesure que le tri progresse (i augmente progressivement), le nombre de comparaisons deviendra de moins en moins, mais que le tableau soit initialement ordonné ou non, le le tri par sélection commencera à partir de i Une comparaison de sélection est effectuée jusqu'à la fin du tableau, donc pour un tableau d'une longueur donnée, le nombre de comparaisons dans le tri par sélection est fixe : 1 2 3 .... n = n * (n 1) / 2, et le nombre d'échanges est le même que l'ordre du tableau initial. De manière pertinente, si l'ordre initial du tableau est aléatoire, alors dans le pire des cas, les éléments du tableau seront échangés n fois, et dans le meilleur des cas. Dans ce cas, cela peut être 0 fois (le tableau lui-même est ordonné).
On peut en déduire que la complexité temporelle et la complexité spatiale du tri par sélection sont respectivement O(n2) et O(1) (le tri par sélection ne nécessite qu'un espace supplémentaire pour l'échange d'éléments de tableau).
Code d'implémentation :
/**
* Selection Sorting
*/
SELECTION(new Sortable() {
public <T extends Comparable<T>> void sort(T[] array, boolean ascend) {
int len = array.length;
for (int i = 0; i < len; i++) {
int selected = i;
for (int j = i + 1; j < len; j++) {
int compare = array[j].compareTo(array[selected]);
if (compare != 0 && compare < 0 == ascend) {
selected = j;
}
}
exchange(array, i, selected);
}
}
})Copier après la connexion
2. Tri par insertion
L'idée de base du tri par insertion est que pendant le processus de parcours du tableau, supposez que l'élément avant que le numéro de séquence i soit [ 0..i-1], tous ont été triés. Cette fois, nous devons trouver la position correcte k de l'élément x "libère la position", et enfin attribuer la valeur d'élément correspondant à k à x. . Le tri par insertion est également nommé en fonction des caractéristiques du tri.
Ce qui suit est un exemple. Les nombres marqués en rouge sont les nombres insérés. Les nombres barrés sont les éléments qui ne participent pas à ce tri. Les éléments entre les nombres marqués en rouge et les barrés. les numéros sont un par un. Les éléments qui sont déplacés plus tard, par exemple, les éléments qui participent au deuxième tri sont [11, 31, 12], et l'élément qui doit être inséré est 12, mais 12 ne l'est pas actuellement. dans la bonne position, nous devons donc le déplacer avec les éléments précédents 31 et 11 dans l'ordre, déplacer les éléments comparés tout en comparant et arrêter de comparer lorsque vous trouvez le premier élément 11 qui est plus petit que 12. À ce stade, l'index 1 correspondant à 31 est la position où 12 doit être inséré.
Initial : [11, 31, 12, 5, 34, 30, 26, 38, 36, 18]
Premier voyage : [11, 31, 12, 5, 34, 30 , 26, 38, 36, 18] (aucun élément mobile)
Deuxième passage : [11, 12, 31, 5, 34, 30, 26, 38, 36, 18] (31 pour reculer)
Le troisième voyage : [5, 11, 12, 31, 34, 30, 26, 38, 36, 18] (11, 12, 31 reculent tous)
Le quatrième passage : [5, 11, 12, 31, 34, 30, 26, 38, 36, 18] (aucun élément mobile)
La cinquième passe : [5, 11, 12, 30, 31, 34, 26, 38, 36, 18] (31, 34 recule)
Le sixième voyage : [5, 11, 12, 26, 30, 31, 34, 38, 36, 18] (30, 31 , 34 reculé)
Septième voyage : [5, 11, 12, 26, 30, 31, 34, 38, 36, 18] (aucun élément mobile)
Le huitième voyage : [5, 11, 12, 26, 30, 31, 34, 36, 38, 18] (38 recule)
Le neuvième voyage : [5, 11, 12, 18, 26, 30, 31 , 34, 36, 38] (26, 30, 31, 34, 36, 38 recule)
插入排序会优于选择排序，理由是它在排序过程中能够利用前部分数组元素已经排好序的一个优势，有效地减少一些比较的次数，当然这种优势得看数组的初始顺序如何，最坏的情况下（给定的数组恰好为倒序）插入排序需要比较和移动的次数将会等于 1 + 2 + 3… + n = n * (n + 1) / 2 ，这种极端情况下，插入排序的效率甚至比选择排序更差。因此插入排序是一个不稳定的排序方法，插入效率与数组初始顺序息息相关。一般情况下，插入排序的时间复杂度和空间复杂度分别为 O(n2 ) 和 O(1) 。
实现代码：
/**
* Insertion Sorting
*/
INSERTION(new Sortable() {
public <T extends Comparable<T>> void sort(T[] array, boolean ascend) {
int len = array.length;
for (int i = 1; i < len; i++) {
T toInsert = array[i];
int j = i;
for (; j > 0; j–) {
int compare = array[j - 1].compareTo(toInsert);
if (compare == 0 || compare < 0 == ascend) {
break;
}
array[j] = array[j - 1];
}
array[j] = toInsert;
}
}
})Copier après la connexion
3. 冒泡排序
冒泡排序可以算是最经典的排序算法了，记得小弟上学时最先接触的也就是这个算法了，因为实现方法最简单，两层 for 循环，里层循环中判断相邻两个元素是否逆序，是的话将两个元素交换，外层循环一次，就能将数组中剩下的元素中最小的元素“浮”到最前面，所以称之为冒泡排序。
照例举个简单的实例吧：
初始状态： [24, 19, 26, 39, 36, 7, 31, 29, 38, 23]
内层第一趟： [24, 19, 26, 39, 36, 7, 31, 29, 23 , 38 ] （ 9th [23]<->8th [38 ）
内层第二趟： [24, 19, 26, 39, 36, 7, 31, 23 , 29 , 38] （ 8th [23]<->7th [29] ）
内层第三趟： [24, 19, 26, 39, 36, 7, 23 , 31 , 29, 38] （ 7th [23]<->6th [31] ）
内层第四趟： [24, 19, 26, 39, 36, 7, 23, 31, 29, 38] （ 7 、 23 都位于正确的顺序，无需交换）
内层第五趟： [24, 19, 26, 39, 7 , 36 , 23, 31, 29, 38] （ 5th [7]<->4th [36] ）
内层第六趟： [24, 19, 26, 7 , 39 , 36, 23, 31, 29, 38] （ 4th [7]<->3rd [39] ）
内层第七趟： [24, 19, 7 , 26 , 39, 36, 23, 31, 29, 38] （ 3rd [7]<->2nd [26] ）
内层第八趟： [24, 7 , 19 , 26, 39, 36, 23, 31, 29, 38] （ 2nd [7]<->1st [19] ）
内层第九趟： [7 , 24 , 19, 26, 39, 36, 23, 31, 29, 38] （ 1st [7]<->0th [24] ）
……… .
其实冒泡排序跟选择排序比较相像，比较次数一样，都为 n * (n + 1) / 2 ，但是冒泡排序在挑选最小值的过程中会进行额外的交换（冒泡排序在排序中只要发现相邻元素的顺序不对就会进行交换，与之对应的是选择排序，只会在内层循环比较结束之后根据情况决定是否进行交换），所以在我看来，选择排序属于冒泡排序的改进版。
实现代码：
/**
* Bubble Sorting, it's very similar with Insertion Sorting
*/
BUBBLE(new Sortable() {
public <T extends Comparable<T>> void sort(T[] array, boolean ascend) {
int length = array.length;
int lastExchangedIdx = 0;
for (int i = 0; i < length; i++) {
// mark the flag to identity whether exchange happened to false
boolean isExchanged = false;
// last compare and exchange happened before reaching index i
int currOrderedIdx = lastExchangedIdx > i ? lastExchangedIdx : i;
for (int j = length – 1; j > currOrderedIdx; j–) {
int compare = array[j - 1].compareTo(array[j]);
if (compare != 0 && compare > 0 == ascend) {
exchange(array, j – 1, j);
isExchanged = true;
lastExchangedIdx = j;
}
}
// if no exchange happen means array is already in order
if (isExchanged == false) {
break;
}
}
}
})Copier après la connexion
4. 希尔排序
希尔排序的诞生是由于插入排序在处理大规模数组的时候会遇到需要移动太多元素的问题。希尔排序的思想是将一个大的数组“分而治之”，划分为若干个小的数组，以 gap 来划分，比如数组 [1, 2, 3, 4, 5, 6, 7, 8] ，如果以 gap = 2 来划分，可以分为 [1, 3, 5, 7] 和 [2, 4, 6, 8] 两个数组（对应的，如 gap = 3 ，则划分的数组为： [1, 4, 7] 、 [2, 5, 8] 、 [3, 6] ）然后分别对划分出来的数组进行插入排序，待各个子数组排序完毕之后再减小 gap 值重复进行之前的步骤，直至 gap = 1 ，即对整个数组进行插入排序，此时的数组已经基本上快排好序了，所以需要移动的元素会很小很小，解决了插入排序在处理大规模数组时较多移动次数的问题。
具体实例请参照插入排序。
希尔排序是插入排序的改进版，在数据量大的时候对效率的提升帮助很大，数据量小的时候建议直接使用插入排序就好了。
实现代码：
/**
* Shell Sorting
*/
SHELL(new Sortable() {
public <T extends Comparable<T>> void sort(T[] array, boolean ascend) {
int length = array.length;
int gap = 1;
// use the most next to length / 3 as the first gap
while (gap < length / 3) {
gap = gap * 3 + 1;
}
while (gap >= 1) {
for (int i = gap; i < length; i++) {
T next = array[i];
int j = i;
while (j >= gap) {
int compare = array[j - gap].compareTo(next);
// already find its position
if (compare == 0 || compare < 0 == ascend) {
break;
}
array[j] = array[j - gap];
j -= gap;
}
if (j != i) {
array[j] = next;
}
}
gap /= 3;
}
}
})Copier après la connexion
5. 归并排序
归并排序采用的是递归来实现，属于“分而治之”，将目标数组从中间一分为二，之后分别对这两个数组进行排序，排序完毕之后再将排好序的两个数组“归并”到一起，归并排序最重要的也就是这个“归并”的过程，归并的过程中需要额外的跟需要归并的两个数组长度一致的空间，比如需要规定的数组分别为： [3, 6, 8, 11] 和 [1, 3, 12, 15] （虽然逻辑上被划为为两个数组，但实际上这些元素还是位于原来数组中的，只是通过一些 index 将其划分成两个数组，原数组为 [3, 6, 8, 11, 1, 3, 12, 15 ，我们设置三个指针 lo, mid, high 分别为 0,3,7 就可以实现逻辑上的子数组划分）那么需要的额外数组的长度为 4 + 4 = 8 。归并的过程可以简要地概括为如下：
1） 将两个子数组中的元素复制到新数组 copiedArray 中，以前面提到的例子为例，则 copiedArray = [3, 6, 8, 11, 1, 3, 12, 15] ；
2） 设置两个指针分别指向原子数组中对应的第一个元素，假定这两个指针取名为 leftIdx 和 rightIdx ，则 leftIdx = 0 （对应 copiedArray 中的第一个元素 [3] ）， rightIdx = 4 （对应 copiedArray 中的第五个元素 [1] ）；
3） 比较 leftIdx 和 rightIdx 指向的数组元素值，选取其中较小的一个并将其值赋给原数组中对应的位置 i ，赋值完毕后分别对参与赋值的这两个索引做自增 1 操作，如果 leftIdx 或 rigthIdx 值已经达到对应数组的末尾，则余下只需要将剩下数组的元素按顺序 copy 到余下的位置即可。
下面给个归并的具体实例：
第一趟：
辅助数组 [21 , 28, 39 | 35, 38] （数组被拆分为左右两个子数组，以 | 分隔开）
[21 , , , , ] （第一次 21 与 35 比较 , 左边子数组胜出， leftIdx = 0 ， i = 0 ）
第二趟：
辅助数组 [21, 28 , 39 | 35, 38]
[21 , 28, , , ] （第二次 28 与 35 比较，左边子数组胜出， leftIdx = 1 ， i = 1 ）
第三趟： [21, 28, 39 | 35 , 38]
[21 , 28 , 35, , ] （第三次 39 与 35 比较，右边子数组胜出， rightIdx = 0 ， i = 2 ）
第四趟： [21, 28, 39 | 35, 38 ]
[21 , 28 , 35 , 38, ] （第四次 39 与 38 比较，右边子数组胜出， rightIdx = 1 ， i = 3 ）
第五趟： [21, 28, 39 | 35, 38]
[21 , 28 , 35 , 38 , 39] （第五次时右边子数组已复制完，无需比较 leftIdx = 2 ， i = 4 ）
以上便是一次归并的过程，我们可以将整个需要排序的数组做有限次拆分（每次一分为二）直到分为长度为 1 的小数组为止，长度为 1 时数组已经不用排序了。在这之后再逆序（由于采用递归）依次对这些数组进行归并操作，直到最后一次归并长度为 n / 2 的子数组，归并完成之后数组排序也完成。
归并排序需要的额外空间是所有排序中最多的，每次归并需要与参与归并的两个数组长度之和相同个元素（为了提供辅助数组）。则可以推断归并排序的空间复杂度为 1 + 2 + 4 + … + n = n * ( n + 2) / 4 （忽略了 n 的奇偶性的判断），时间复杂度比较难估，这里小弟也忘记是多少了（囧）。
实现代码：
/**
* Merge sorting
*/
MERGE(new Sortable() {
public <T extends Comparable<T>> void sort(T[] array, boolean ascend) {
this.sort(array, 0, array.length – 1, ascend);
}
private <T extends Comparable<T>> void sort(T[] array, int lo, int hi, boolean ascend) {
// OPTIMIZE ONE
// if the substring's length is less than 20,
// use insertion sort to reduce recursive invocation
if (hi – lo < 20) {
for (int i = lo + 1; i <= hi; i++) {
T toInsert = array[i];
int j = i;
for (; j > lo; j–) {
int compare = array[j - 1].compareTo(toInsert);
if (compare == 0 || compare < 0 == ascend) {
break;
}
array[j] = array[j - 1];
}
array[j] = toInsert;
}
return;
}
int mid = lo + (hi – lo) / 2;
sort(array, lo, mid, ascend);
sort(array, mid + 1, hi, ascend);
merge(array, lo, mid, hi, ascend);
}
private <T extends Comparable<T>> void merge(T[] array, int lo, int mid, int hi, boolean ascend) {
// OPTIMIZE TWO
// if it is already in right order, skip this merge
// since there's no need to do so
int leftEndCompareToRigthStart = array[mid].compareTo(array[mid + 1]);
if (leftEndCompareToRigthStart == 0 || leftEndCompareToRigthStart < 0 == ascend) {
return;
}
@SuppressWarnings("unchecked")
T[] arrayCopy = (T[]) new Comparable[hi - lo + 1];
System.arraycopy(array, lo, arrayCopy, 0, arrayCopy.length);
int lowIdx = 0;
int highIdx = mid – lo + 1;
for (int i = lo; i <= hi; i++) {
if (lowIdx > mid – lo) {
// left sub array exhausted
array[i] = arrayCopy[highIdx++];
} else if (highIdx > hi – lo) {
// right sub array exhausted
array[i] = arrayCopy[lowIdx++];
} else if (arrayCopy[lowIdx].compareTo(arrayCopy[highIdx]) < 0 == ascend) {
array[i] = arrayCopy[lowIdx++];
} else {
array[i] = arrayCopy[highIdx++];
}
}
}
})Copier après la connexion
6. 快速排序
快速排序也是用归并方法实现的一个“分而治之”的排序算法，它的魅力之处在于它能在每次 partition （排序算法的核心所在）都能为一个数组元素确定其排序最终正确位置（一次就定位准，下次循环就不考虑这个元素了）。
更多Java中常用的6种排序算法详细分解相关文章请关注PHP中文网！
![[Web front-end] Démarrage rapide de Node.js](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
