algorithme java (1) : algorithme de tri principal

Programme = algorithme de structure de données. Pour les frameworks qui construisent des projets qui ne sont pas écrits par nous, ce qui peut vraiment juger du niveau d'un projet est de savoir si les structures de données que nous personnalisons sont pratiques, concises et faiblement couplées ; et efficace, moins sujet aux erreurs. Si ce que vous voulez faire n’est pas le genre de travail consistant à déplacer des briques du matin au soir chaque jour, apprendre des algorithmes et analyser des structures de données est certainement le seul moyen pour vous d’augmenter votre niveau.

(1) Algorithme de tri

Les algorithmes et les langages de programmation sont étroitement liés, mais ils ne dépendent pas seulement d'un certain langage. Sans considérer le langage d'implémentation, nous avons généralement les méthodes de tri suivantes :

1. Tri par sélection

2. Tri par insertion

3. Tri par colline

4. Tri par fusion

5. Tri rapide

Nous ne parlons pas seulement de ces méthodes de tri en général. Après avoir présenté les cinq algorithmes de tri, nous résumerons ces méthodes et les connecterons à l'API Java. De plus, afin de faciliter notre implémentation de ces méthodes de tri, nous utilisons désormais quelques méthodes auxiliaires. Ces méthodes auxiliaires sont très simples, et leur but est de rendre notre code concis.

    /**
     * 比较两个大小不同的数字，如果第一个参数比较小则返回true。
     * 
     * @param v 第一个数字
     * @param w 第二个数字
     * @return 返回比较结果
     */
    public static boolean less(int v , int w){        if(v<w) return true;        return false;
    }    /**
     * 交换数组中两个索引的内容
     * 
     * @param arr 数组
     * @param v 第一个索引
     * @param w 第二个索引
     */ 
    public static void exch(int[] arr,int v ,int w){        int temp=arr[v];
        arr[v]= arr[w];
        arr[w] = temp;
    }    /**
     * 打印数组
     * 
     * @param arr 要显示的数组
     */
    public static void show(int[] arr){        for(int i=0;i<arr.length;i++)
        System.out.println(arr[i]);
    }

(2) Modèle de coût de tri

En Java, la grande majorité des éléments sont des objets, et la description des clés primaires de ces objets se fait par Comparable Il est implémenté par le mécanisme. Ce n'est qu'avec Comparable que nous pouvons avoir les notions d'ordre et de tri. Alors comment étudier si une méthode de tri est rapide ou lente, quelle est sa rapidité et son efficacité ? Nous étudierons le coût de chaque algorithme de tri sous les aspects suivants.

1. Comparer et échanger (Il faut calculer le nombre de comparaisons et d'échanges pour juger du coût du tri)

2. Temps (le temps pris par un algorithme de tri, ou le temps pris dans une certaine situation)

3. Utilisation supplémentaire de la mémoire (Certaines méthodes de tri nécessitent de l'espace mémoire supplémentaire, tandis que d'autres ne le font pas)

Nous donnerons des méthodes spéciales d'estimation des coûts pour certains algorithmes de tri spéciaux. Pour la plupart des méthodes de tri, nous discuterons à la fin, lorsque cette méthode convient - après tout, ces tris inutiles ont depuis longtemps été éliminés.

(3) Tri par sélection

Le tri par sélection est l'algorithme de tri le plus simple parmi tous les tris. L'idée centrale du tri par sélection est la suivante :

Conservez un sous-tableau ordonné à l'extrémité avant du tableau, recherchez à chaque fois le plus petit élément dans la seconde moitié du tableau non ordonné et combinez-le avec le premier élément après la fin du front-end Échange un élément non ordonné pour rendre cet élément ordonné. Le tri est terminé lorsque les éléments partiels du tableau triés sont égaux au nombre total d'éléments.

En termes simples, nous trouvons d'abord le plus petit élément du tableau et l'échangeons avec le premier élément Si le premier élément est le plus petit élément, alors il et il l'échangent vous-même . 🎜>. Ensuite, nous trouvons le plus petit élément du deuxième élément jusqu'à la fin, l'échangeons avec le deuxième élément du tableau, et ainsi de suite, en sélectionnant continuellement le plus petit élément parmi les éléments restants.

1. Comparaison et échange

Le tri de sélection a un nombre fixe de comparaisonsN²/2, et un Nombre d'échanges fixeN.

En termes de nombre de comparaisons, le tri par sélection doit comparer pour la première fois du premier élément au dernier élément pour savoir quel est le plus petit élément. Dans un deuxième temps, N-1 comparaisons sont nécessaires pour connaître le plus petit élément. Un total de N (N-1) (N-2) ··· 1 = N²/2 fois sont nécessaires.

Car du fait de la programmation de l'algorithme, même si le plus petit élément est déjà dans la bonne position, il faut quand même échanger sa position avec lui-même, donc le nombre d'échanges est également fixé à N fois.

2. Temps

Le temps d'exécution du tri par sélection est fixe, d'environ N²/2 fois de comparaison (N² /2, on peut en gros ignorer les N temps d'échange). Si nous ne pouvons pas estimer le temps d'exécution d'une méthode de tri, nous connaissons désormais au moins une méthode de tri garantie. Tant que votre méthode de tri est utilisée correctement, sa durée d'exécution ne dépassera jamais N²/2 temps de comparaison. .

3.java实现

package Sort;/**
 * 
 * @author QuinnNorris 选择排序
 */public class Sort1 {

    /**
     * @param args
     */
    public static void main(String[] args) {        // TODO Auto-generated method stub

        int[] arr = { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };        // 测试数组
        sort(arr);        // 调用排序算法
        Tool.show(arr);        // 打印
    }    /**
     * 用选择排序将arr升序排列
     * 
     * @param arr
     *            所要排列的数组
     */
    public static void sort(int[] arr) {        
    for (int i = 0; i < arr.length; i++) {            
    int min = i;            
    for (int j = i + 1; j < arr.length; j++)                
    if (Tool.less(arr[j], arr[min]))
                    min = j;
            Tool.exch(arr, min, i);
        }
    }
}

4.特点

选择排序非常简单，他有两个很鲜明的特点：
1.运行时间和输入无关
运行时间和输入无关，好听的讲就是无论多么乱的数据都会在固定的时间之内完成排序，但是更多的情况下，这种前一遍比较不能为后一遍比较提供任何价值的算法是非常费时的。夸张的讲，如果我们要完成某个几乎接近有序的数组的排序，你会发现，使用选择排序所需的时间和去排序那些无序的数组竟然是完全一样的。这在很多情况下是大家不能接受的。
2.数据移动最少
为了保证最少的交换数据，我们不断的进行比较，每次的交换都会百分之百的把一个数字放在正确的位置上。其他的任何排序方法都不具备这个特性。

（四）插入排序

在选择排序中，一个几乎有序的数组和一个完全无序的数组所需时间是一样的。插入排序则完美的解决了这个问题：

从数组的头部开始，通过不断的一次一位的比较和交换，让每个数据都能插入前端有序部分中自己合理的位置，当所有的元素都完成一遍操作后，排序完成。

我们将要排序的那个元素和前面一位元素比较，如果比前面的元素小，则交换位置，这个元素继续和再前面的元素比较，如果仍然小则继续交换，知道前面的元素小于该元素位置。这个时候，这个不断交换的元素就在这个数组中达到了自己合适的位置，刚才其他被交换的元素，都像是“向后移动一个位置”，为这个元素挪出了空间，这就是插入排序。这种排序很类似我们在打桥牌时整理牌的方法，不断地将牌按照大小从后向前插入。

1.比较和交换

在一个随机排序而且主键不重复的数组中，平均情况下插入排序需要N²/4次比较以及N²/4次交换。在最坏的情况下需要N²/2次比较和N²/2次交换，最好情况下需要N-1次比较和0次交换。
这个平均情况是怎么计算得出的呢？通常情况下，我们认为数组中的一个数字在整个数组中会被移动半个数组的长度（在平均情况下，每个数字都会移动到有序部分的中间位置，在这种情况下，数字自己的移动和被向后“推”的移动加起来长度为半个数组），在半个数组的移动算作平均情况下，我们得到N²/4的比较和交换次数。

2.时间

我们可以看出，用插入排序算法排序的时间和这个数组情况有很大关系，如果数组是非常无序的，它的速度要慢于选择排序，但是如果我们现在要排序的数组是几乎完全有序的，那么它的时间将会非常的小。就像我们手中握着一副全都排好顺序的扑克牌，这时你抽到一张梅花9，你可以非常快的将它插到你的手牌中。

1. 数组中每个元素距离他的最终位置不远

2. 一个有序数组的大数组接一个小数组

3. 数组中只有几个元素的位置不正确

上述的三种情况下，使用插入算法会非常非常有效。事实上，当顺序错误的数量很少的时候，插入排序会比其他任何排序算法都快。

3.java实现

package Sort;/**
 * 
 * @author QuinnNorris 插入排序
 */public class Sort2 {

    /**
     * @param args
     */
    public static void main(String[] args) {        // TODO Auto-generated method stub

        int[] arr = { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };        // 测试数组
        sort(arr);        // 调用排序算法
        Tool.show(arr);        // 打印
    }    /**
     * 用插入排序将arr升序排列
     * 
     * @param arr
     *            所要排列的数组
     */
    public static void sort(int[] arr) {        
    for (int i = 0; i < arr.length; i++)            
    for (int j = i; j > 0; j--)                
    if (Tool.less(arr[j], arr[j - 1]))
                    Tool.exch(arr, j, j - 1);
    }
}

4.特点

在插入排序中，因为他的速度和原有的序列有很大关系。在这里，我们将在原序列中位置顺序颠倒的一对数字叫做倒置，这只是我们起的一个名字，它表示两个数字的位置是错误的（a应该在b的前面，但是在数组中a在b的后面，无论a与b相隔多远，都可以称a、b是一个倒置）。插入排序具有以下几点特性：

1. 交换和比较的次数相同

2. 比较的次数大于等于倒置的数量

3. 比较的次数小于等于倒置数量加上数组的大小再减一

除此之外，插入排序作为一种初级排序算法，会在之后的高级排序算法中作为一个中间算法频频出现，我们会在以后再见到他。

（五）选择算法和插入算法比较

这两种算法是如此的相似，以至于我们非常好奇想将他们比较一番。对于随机排序无重复的数组，插入排序和选择排序的运行时间都是平方级别的，所以两者只比应该是一个较小的常数。

(6) Tri Hill

L'algorithme de tri que nous allons présenter ensuite n'est pas un algorithme de tri primaire, mais il utilise en fait la technologie de l'algorithme d'insertion. eh bien, discutons-en ici. Le tri Hill fait référence à :

En formulant une valeur h constante de grande à petite et en insérant un tri, les éléments avec n'importe quel intervalle de h dans le tableau sont ordonnés. Continuez à réduire la taille de h jusqu'à h=1, afin que l'ensemble du tableau soit ordonné.

Utilisons le bridge comme analogie. Au début, vous avez un jeu de cartes dans le désordre. Vous pouvez trouver les positions une par une, mais ensuite vous sentez que cette méthode est trop lente. , vous envisagez donc de faire d'abord une sélection approximative. Vous mettez certaines cartes dans l'ordre, mais d'autres cartes ne le sont pas. De cette façon, vous passez au crible vos cartes plusieurs fois et finalement vous mettez toutes les cartes de votre main dans l'ordre. C'est du genre Hill.

Lorsque nous devons trier des dizaines de milliers de tableaux, nous pouvons généralement utiliser le tri Hill.
Dans le tri Hill, nous définissons d'abord un h. Nous utilisons h comme intervalle pour diviser un sous-tableau. Nous utilisons l'algorithme d'insertion pour trier ce sous-tableau. Ensuite, nous continuons à réduire h et nous trions le nouveau tableau. Enfin, lorsque h vaut 1, ce tri maintient toutes les données dans l'ordre.

1. Avantages

Alors quels sont les avantages du tri Hill ? Nous savons que l’avantage du tri par insertion est qu’il est extrêmement rapide pour trier des séquences partiellement ordonnées, et qu’il est très rapide pour trier de petits tableaux. Notre tri Hill combine ces deux avantages. Lorsque h est grand, l'ensemble du tableau est relativement petit et le tri par insertion est plus rapide. Lorsque h est petit, l'ensemble du tableau est progressivement devenu plus ordonné. À ce stade, l'utilisation du tri par insertion est également un très bon choix. On peut dire que le tri Hill combine ces deux avantages, et le temps global est relativement rapide.

2. Temps

Pour le tri Hill, nous n'avons pas l'intention de l'analyser selon notre méthode d'analyse ci-dessus, pour les raisons suivantes. Tout d'abord, le tri de Hill est très difficile à étudier par échange et par comparaison, car le facteur clé est h, h est une constante, et nous pouvons modifier l'intervalle de ce saut en définissant un h différent. Et il n'y a pas d'explication claire : quelle règle h suit-il pour obtenir le meilleur effet (généralement on peut utiliser 3*h 1, c'est-à-dire : 1, 4, 13, 40, 121, 364... Ce groupe de nombres est utilisé cendre). Puisque h ne peut pas être déterminé, il n’y a pas de moment optimal.

3. Application pratique

Les programmeurs expérimentés utilisent parfois le tri Hill, car pour les tableaux de taille moyenne, le temps d'exécution du tri Hill est acceptable. La quantité de code est très faible et aucun espace mémoire supplémentaire n'est utilisé. Peut-être avons-nous des algorithmes plus rapides, mais pour les grands N, ils ne sont probablement que moins de deux fois plus rapides que le tri Hill. Et c'est très compliqué. Si vous avez besoin de trier mais que vous ne disposez pas d'une fonction de tri systématique, vous pouvez envisager d'utiliser le tri Hill, puis envisager de le remplacer par une méthode de tri plus avancée.

Programme = algorithme de structure de données. Pour les frameworks qui construisent des projets qui ne sont pas écrits par nous, ce qui peut vraiment juger du niveau d'un projet est de savoir si les structures de données que nous personnalisons sont pratiques, concises et faiblement couplées ; et efficace, moins sujet aux erreurs. Si ce que vous voulez faire n’est pas le genre de travail consistant à déplacer des briques du matin au soir chaque jour, apprendre des algorithmes et analyser des structures de données est certainement le seul moyen pour vous d’augmenter votre niveau.

Ce qui précède est le contenu de l'algorithme java (1) - algorithme de tri primaire Pour plus de contenu connexe, veuillez faire attention au site Web PHP chinois (www.php.cn) !