Explication et comparaison de huit algorithmes de tri

Présentation

Le soi-disant tri consiste à organiser les éléments de données dans l'ordre selon l'ordre croissant ou décroissant du code de tri, de sorte qu'un ensemble d'éléments disposés arbitrairement devienne un ensemble d'éléments ordonnés linéairement selon leur code de tri. Cet article présentera les idées de base et la mise en œuvre des huit algorithmes de tri interne les plus classiques et les plus couramment utilisés, notamment le tri par insertion (tri par insertion directe, tri Hill), le tri par sélection (tri par sélection directe, tri par tas), le tri par échange (tri à bulles, tri rapide) Tri), le tri par fusion, le tri par affectation (tri par base) et donne la complexité temporelle, la complexité spatiale et la stabilité de divers algorithmes.

Rappel amical :

Si les lecteurs ont besoin du code complet lié à cet article de blog, veuillez vous rendre sur mon Github pour l'obtenir vous-même. Le nom du projet est DataStructure (l'algorithme spécifique est implémenté dans le package cn.tju.edu.rico.sort) et le. L'adresse du lien du projet est : https://github .com/githubofrico/DataStructure.

Aperçu des algorithmes de tri

Le soi-disant tri consiste à organiser les éléments de données dans l'ordre croissant ou décroissant du code de tri, de sorte qu'un ensemble d'éléments disposés arbitrairement devienne un ensemble d'éléments ordonnés linéairement selon leur code de tri. Cet article présente les huit algorithmes de tri interne les plus classiques et les plus couramment utilisés, notamment le tri par insertion (tri par insertion directe, tri Hill), le tri par sélection (tri par sélection directe, tri par tas), le tri par échange (tri à bulles, tri rapide) et par fusion. sort , tri de distribution (tri par base). En effet, qu'il s'agisse d'une méthode de tri basique (tri par insertion directe, tri par sélection directe, tri à bulles) ou d'une méthode de tri efficace (tri rapide, tri par tas, tri par fusion), etc., elles ont toutes leurs propres atouts et usages spécifiques. scénarios. Par conséquent, dans les applications pratiques, nous devons faire le choix le plus approprié en fonction des caractéristiques de la tâche réelle et des caractéristiques des différents algorithmes de tri. Généralement, les indicateurs que nous utilisons pour mesurer un algorithme comprennent :

• Complexité temporelle (nombre de comparaisons et d'échanges nécessaires lors du tri)
• Complexité spatiale (espace de stockage auxiliaire nécessaire lors du tri)
• Stabilité (Que l'implémentation de l'algorithme puisse garantir l'ordre initial des éléments égaux après le tri, tant qu'il existe une implémentation de l'algorithme qui peut garantir cette fonctionnalité, alors l'algorithme est stable)
• Tri interne/tri externe (si les éléments de données sont complètement en mémoire pendant le processus de tri)

Dans cet article, l'auteur se concentrera sur les idées et la mise en œuvre des huit algorithmes de tri ci-dessus, et analysera et classifiera chaque algorithme en fonction des indicateurs ci-dessus afin de se familiariser davantage avec leurs scénarios d'application respectifs.

2. Tri par insertion

L'idée de base du tri par insertion : A chaque étape, un élément à trier est inséré dans un groupe d'éléments préalablement triés selon la taille de son code de tri, jusqu'à ce que tous les éléments soient insérés. Ici, nous introduisons trois algorithmes de tri par insertion spécifiques : le tri par insertion directe, le tri Hill et le tri par insertion à mi-chemin.

1. Tri par insertion directe

L'idée du tri par insertion directe : Lors de l'insertion de l'élément i (i>=1), les éléments i-1 précédents tels que V[0],...,V[i-1] sont déjà en ordre. À ce stade, le i-ième élément est comparé aux i-1 éléments précédents V[i-1],...,V[0] dans l'ordre, et V[i] est inséré lorsque la position d'insertion est trouvée. Dans le même temps, les éléments à la position d'origine sont insérés séquentiellement vers l'arrière. Ici, la recherche à la position d'insertion est une recherche séquentielle. Le tri par insertion directe est un algorithme de tri stable, et sa mise en œuvre est la suivante :

/**        
 * Title: 插入排序中的直接插入排序，依赖于初始序列    
 * Description: 在有序序列中不断插入新的记录以达到扩大有序区到整个数组的目的
 *              时间复杂度：最好情形O(n)，平均情形O(n^2)，最差情形O(n^2)
 *              空间复杂度：O(1)
 *              稳    定   性：稳定
 *              内部排序(在排序过程中数据元素完全在内存)
 * @author rico       
 * @created 2017年5月20日 上午10:40:00    
 */      
public class StraightInsertionSort {

    public static int[] insertSort(int[] target){

        if(target != null && target.length != 1){   // 待排序数组不为空且长度大于1
            for (int i = 1; i  0; j--) {    // 向有序序列中插入新的元素
                    if(target[j]  
<span style="color: #1e1e1e; letter-spacing: 2px; border-left: #FF3030 3px solid; border-right: #FF3030 3px solid; padding-left: 8px; padding-right: 8px; font-size: 12pt;"><strong>2. Tri en colline</strong></span>
<p><span style="color: red;"><strong>L'idée du tri Hill : </strong></span>Supposons que la séquence à trier comporte n éléments au total, prenez d'abord un écart entier<n comme intervalle divisez tous les en sous-s d avec un et effectuez traitement direct sur chaque ensuite r l ci-dessus jusqu ce que diminue stade sont dans le m ordre ordonn parce qu est grand contient moins la vitesse de tri plus rapide phase ult du devient petit mais plupart des fondamentalement donc encore relativement lente. g colline une instable sa mise suivante :>
<pre class="brush:php;toolbar:false">/**        
 * Title: 插入排序中的希尔排序，依赖于初始序列    
 * Description: 分别对间隔为gap的gap个子序列进行直接插入排序，不断缩小gap,直至为 1 
 * 
 *              刚开始时，gap较大，每个子序列元素较少，排序速度较快；
 *              待到排序后期，gap变小，每个子序列元素较多，但大部分元素基本有序，所以排序速度仍较快。                
 * 
 *              时间复杂度：O(n) ~ O(n^2)
 *              空间复杂度：O(1)
 *              稳    定   性：不稳定
 *              内部排序(在排序过程中数据元素完全在内存)
 * @author rico       
 * @created 2017年5月20日 上午10:40:00    
 */      
public class ShellSort {

    public static int[] shellSort(int[] target){
        if(target != null && target.length != 1){
            int gap = target.length;       // gap个大小为gap的子序列
            do{
                gap = gap/3 + 1;     // 不断缩小gap直至为1
                for (int i = 0 + gap; i = 0 && target[j] > temp);  // 向前比较的终止条件
                        target[j + gap] = temp;         // 将待插入值插入合适的位置
                    }
                }
            }while(gap > 1);
        }
        return target;
    }
}

3. Tri par insertion à mi-chemin

L'idée du tri par demi-insertion : Lors de l'insertion de l'élément i (i>=1), les éléments i-1 précédents tels que V[0],...,V[i-1] sont déjà en ordre. À ce stade, recherchez en deux la position d'insertion du i-ème élément dans les i-1 éléments précédents V[i-1],...,V[0], puis insérez directement V[i], tandis que les éléments à la position d'origine sont déplacés vers Déplacer plus tard. Différent du tri par insertion directe, le tri par demi-insertion réduit considérablement le nombre de comparaisons entre les mots-clés par rapport au tri par insertion directe, mais le nombre de déplacements ne change pas. Par conséquent, la complexité temporelle du tri par demi-insertion et du tri par insertion est la même, soit O(N^2), mais elle réduit le nombre de comparaisons, de sorte que l'algorithme est toujours meilleur que le tri par insertion directe. Le tri par insertion à mi-chemin est un algorithme de tri stable, et sa mise en œuvre est la suivante :

/**        
 * Title: 插入排序中的折半插入排序，依赖于初始序列  
 * Description: 折半搜索出插入位置，并直接插入;与直接插入搜索的区别是，后者的搜索要快于顺序搜索
 *              时间复杂度：折半插入排序比直接插入排序明显减少了关键字之间的比较次数，但是移动次数是没有改变。所以，
 *              折半插入排序和插入排序的时间复杂度相同都是O（N^2），在减少了比较次数方面它确实相当优秀，所以该算法仍然比直接插入排序好。
 *              空间复杂度：O(1)
 *              稳    定   性：稳定
 *              内部排序(在排序过程中数据元素完全在内存)
 * @author rico       
 * @created 2017年5月25日 下午12:03:23    
 */      
public class BinaryInsertSort {
    public static int[] binaryInsertSort(int[] target) {
        if (target != null && target.length > 1) {
            for (int i = 1; i  temp){
                            right = mid - 1;    // 缩小插入区间
                        }else{        // 待插入值与有序序列中的target[mid]相等，保证稳定性的处理
                            left = left + 1;   
                        }
                    }

                    // left及其后面的数据顺序向后移动，并在left位置插入
                    for (int j = i; j > left; j--) {
                        target[j] = target[j-1];
                    }
                    target[left] = temp;
                }
            }
        }
        return target;
    }
}

三. 选择排序

选择排序的基本思想：每一趟 (例如第i趟，i = 0,1,…)在后面第n-i个待排序元素中选出最小元素作为有序序列的第i个元素，直到第n-1趟结束后，所有元素有序。在这里，我们介绍两种具体的选择排序算法：直接选择排序与堆排序。

1、直接选择排序

直接选择排序的思想：第一次从R[0]~R[n-1]中选取最小值，与R[0]交换，第二次从R1~R[n-1]中选取最小值，与R1交换，….，第i次从R[i-1]~R[n-1]中选取最小值，与R[i-1]交换，…..，第n-1次从R[n-2]~R[n-1]中选取最小值，与R[n-2]交换，总共通过n-1次，得到一个按排序码从小到大排列的有序序列。直接选择排序是一种不稳定的排序算法，其实现如下：

/**        
 * Title: 选择排序中的直接选择排序，依赖于初始序列     
 * Description: 每一趟 (例如第i趟，i = 0,1,...)在后面第n-i个待排序元素中选出最小元素作为有序序列的第i个元素
 *              时间复杂度：最好情形O(n^2)，平均情形O(n^2)，最差情形O(n^2)
 *              空间复杂度：O(1)
 *              稳    定   性：不稳定
 *              内部排序(在排序过程中数据元素完全在内存)
 * @author rico       
 * @created 2017年5月20日 上午10:40:00    
 */      
public class StraightSelectSort {
    public static int[] selectSort(int[] target){
        if(target != null && target.length != 1){
            for (int i = 0; i  target[j]){
                        min_index = j;
                    }
                }
                if(target[min_index] != target[i]){  // 导致不稳定的因素：交换
                    int min = target[min_index];
                    target[min_index] = target[i];
                    target[i] = min;
                }
            }
        }
        return target;
    }
}

2、堆排序

堆排序的核心是堆调整算法。首先根据初始输入数据，利用堆调整算法shiftDown()形成初始堆；然后，将堆顶元素与堆尾元素交换，缩小堆的范围并重新调整为堆，如此往复。堆排序是一种不稳定的排序算法，其实现如下：

/**        
 * Title: 堆排序(选择排序)，升序排序(最大堆)，依赖于初始序列     
 * Description: 现将给定序列调整为最大堆，然后每次将堆顶元素与堆尾元素交换并缩小堆的范围，直到将堆缩小至1
 * 时间复杂度：O(nlgn)
 * 空间复杂度：O(1) 
 * 稳 定 性：不稳定
 * 内部排序(在排序过程中数据元素完全在内存)
 * @author rico       
 * @created 2017年5月25日 上午9:48:06    
 */      
public class HeapSort {

    public static int[] heapSort(int[] target) {
        if (target != null && target.length > 1) {

            // 调整为最大堆
            int pos = (target.length - 2) / 2;
            while (pos >= 0) {
                shiftDown(target, pos, target.length - 1);
                pos--;
            }

            // 堆排序
            for (int i = target.length-1; i > 0; i--) {
                int temp = target[i];
                target[i] = target[0];
                target[0] = temp;
                shiftDown(target, 0, i-1);
            }
            return target;
        }
        return target;
    }

    /**     
     * @description 自上而下调整为最大堆
     * @author rico       
     * @created 2017年5月25日 上午9:45:40     
     * @param target
     * @param start
     * @param end     
     */
    private static void shiftDown(int[] target, int start, int end) {
        int i = start;
        int j = 2 * start + 1;
        int temp = target[i];
        while (j  target[j]) {  //找出较大子女
                j = j + 1;
            }
            if (target[j] 
<strong>四. 交换排序</strong>
<p><span style="color: red;"><strong>交换排序的基本思想：</strong></span>根据序列中两个元素的比较结果来对换这两个记录在序列中的位置，也就是说，将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。</p>
<span style="color: #1e1e1e; letter-spacing: 2px; border-left: #FF3030 3px solid; border-right: #FF3030 3px solid; padding-left: 8px; padding-right: 8px; font-size: 12pt;"><strong>1、冒泡排序</strong></span>
<p><span style="color: red;"><strong>冒泡排序的思想：</strong></span>根据序列中两个元素的比较结果来对换这两个记录在序列中的位置，将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。因此，每一趟都将较小的元素移到前面，较大的元素自然就逐渐沉到最后面了，也就是说，最大的元素最后才能确定，这就是冒泡。冒泡排序是一种稳定的排序算法，其实现如下：</p>
<pre class="brush:php;toolbar:false">/**
 * Title: 交换排序中的冒泡排序 ，一般情形下指的是优化后的冒泡排序，最多进行n-1次比较，依赖于初始序列  
 * Description:因为越大的元素会经由交换慢慢"浮"到数列的顶端(最后位置)，最大的数最后才确定下来，所以称为冒泡排序
 * 时间复杂度：最好情形O(n)，平均情形O(n^2)，最差情形O(n^2) 
 * 空间复杂度：O(1) 
 * 稳 定 性：稳定
 * 内部排序(在排序过程中数据元素完全在内存)
 * 
 * @author rico
 * @created 2017年5月20日 上午10:40:00
 */
public class BubbleSort {

    /**     
     * @description 朴素冒泡排序(共进行n-1次比较)
     * @author rico         
     */
    public static int[] bubbleSort(int[] target) {
        int n = target.length;
        if (target != null && n != 1) {
            // 最多需要进行n-1躺，每一趟将比较小的元素移到前面，比较大的元素自然就逐渐沉到最后面了，这就是冒泡
            for (int i = 0; i  i; j--) {
                    if(target[j]  i; j--) {
                    if(target[j] 
<span style="color: #1e1e1e; letter-spacing: 2px; border-left: #FF3030 3px solid; border-right: #FF3030 3px solid; padding-left: 8px; padding-right: 8px; font-size: 12pt;"><strong>2、快速排序</strong></span>
<p><span style="color: red;"><strong>快速排序的思想：</strong></span>通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小(划分过程)，然后再按此方法对这两部分数据分别进行快速排序(快速排序过程)，整个排序过程可以递归进行，以此达到整个数据变成有序序列。快速排序是一种不稳定的排序算法。</p>
<pre class="brush:php;toolbar:false">/**
 * Title: 交换排序中的快速排序，目前应用最为广泛的排序算法，是一个递归算法，依赖于初始序列  
 * Description:快速排序包括两个过程：划分 和 快排
 * "划分"是指将原序列按基准元素划分两个子序列
 * "快排"是指分别对子序列进行快排
 * 
 * 就平均计算时间而言，快速排序是所有内部排序方法中最好的一个
 * 
 * 对大规模数据排序时，快排是快的；对小规模数据排序时，快排是慢的，甚至慢于简单选择排序等简单排序方法
 * 
 * 快速排序依赖于原始序列，因此其时间复杂度从O(nlgn)到O(n^2)不等
 * 时间复杂度：最好情形O(nlgn)，平均情形O(nlgn)，最差情形O(n^2)
 * 
 * 递归所消耗的栈空间
 * 空间复杂度：O(lgn)
 * 
 * 可选任一元素作为基准元素
 * 稳 定 性：不稳定
 * 
 * 
 * 内部排序(在排序过程中数据元素完全在内存)
 * 
 * @author rico
 * @created 2017年5月20日 上午10:40:00
 */
public class QuickSort {

    /**     
     * @description 快排算法(递归算法)：在递去过程中就把问题解决了
     * @author rico       
     * @created 2017年5月20日 下午5:12:06     
     * @param target
     * @param left
     * @param right
     * @return     
     */
    public static int[] quickSort(int[] target, int left, int right) {

        if(right > left){     // 递归终止条件
            int base_index = partition(target,left, right);  // 原序列划分后基准元素的位置
            quickSort(target, left, base_index-1);    // 对第一个子序列快速排序，不包含基准元素！
            quickSort(target, base_index+1, right);   // 对第二个子序列快速排序，不包含基准元素！
            return target;
        }
        return target;
    }

    /**     
     * @description 序列划分，以第一个元素为基准元素
     * @author rico       
     * @created 2017年5月20日 下午5:10:54     
     * @param target  序列
     * @param left 序列左端
     * @param right  序列右端
     * @return     
     */
    public static int partition(int[] target, int left, int right){

        int base = target[left];   // 基准元素的值
        int base_index = left;    // 基准元素最终应该在的位置

        for (int i = left+1; i 
<strong>五. 归并排序</strong>
<p><span style="color: red;"><strong>归并排序包含两个过程：”归”和”并”。</strong></span>其中，”归”是指将原序列分成半子序列，分别对子序列进行递归排序；”并”是指将排好序的各子序列合并成原序列。归并排序算法是一个典型的递归算法，因此也是概念上最为简单的排序算法。与快速排序算法相比，归并排序算法不依赖于初始序列，并且是一种稳定的排序算法，但需要与原序列一样大小的辅助存储空间。</p>
<pre class="brush:php;toolbar:false">/**
 * Title: 归并排序 ，概念上最为简单的排序算法，是一个递归算法，不依赖于初始序列  
 * Description:归并排序包括两个过程：归 和 并
 * "归"是指将原序列分成半子序列，分别对子序列进行递归排序
 * "并"是指将排好序的各子序列合并成原序列
 * 
 * 归并排序的主要问题是：需要一个与原待排序数组一样大的辅助数组空间
 * 
 * 归并排序不依赖于原始序列，因此其最好情形、平均情形和最差情形时间复杂度都一样
 * 时间复杂度：最好情形O(n)，平均情形O(n^2)，最差情形O(n^2) 
 * 空间复杂度：O(n) 
 * 稳 定 性：稳定
 * 内部排序(在排序过程中数据元素完全在内存)
 * 
 * @author rico
 * @created 2017年5月20日 上午10:40:00
 */
public class MergeSort {

    /**     
     * @description 归并排序算法(递归算法)：递去分解，归来合并
     * @author rico       
     * @created 2017年5月20日 下午4:04:52     
     * @param target 待排序序列
     * @param left  待排序序列起始位置
     * @param right  待排序序列终止位置
     * @return     
     */
    public static int[] mergeSort(int[] target, int left, int right) {

        if(right > left){           // 递归终止条件
            int mid = (left + right)/2;
            mergeSort(target, left, mid);   // 归并排序第一个子序列
            mergeSort(target, mid+1, right);   // 归并排序第二个子序列
            return merge(target,left,mid,right);  // 合并子序列成原序列
        }
        return target;
    }

    /**     
     * @description 两路归并算法
     * @author rico       
     * @created 2017年5月20日 下午3:59:16     
     * @param target 用于存储归并结果
     * @param left 第一个有序表的第一个元素所在位置
     * @param mid  第一个有序表的最后一个元素所在位置
     * @param right  第二个有序表的最后一个元素所在位置
     * @return     
     */
    public static int[] merge(int[] target, int left, int mid, int right){

        // 需要一个与原待排序数组一样大的辅助数组空间
        int[] temp = Arrays.copyOf(target, target.length);

        // s1,s2是检查指针，index 是存放指针
        int s1 = left;
        int s2 = mid + 1;
        int index = left;

        // 两个表都未检查完，两两比较
        while(s1 
<p>Ps : 归并排序和快速排序都是典型的递归算法，因此它们比较容易理解和实现。关于递归思想和内涵深度剖析，请见博文《算法设计方法：递归的内涵与经典应用》。</p>
<strong>六. 分配排序(基数排序)</strong>
<p><span style="color: red;"><strong>分配排序的基本思想</strong></span>：用空间换时间。在整个排序过程中，无须比较关键字，而是通过用额外的空间来”分配”和”收集”来实现排序，它们的时间复杂度可达到线性阶：O(n)。其中，基数排序包括两个过程：首先，将目标序列各元素分配到各个桶中(分配过程)；然后，将各个桶中的元素按先进先出的顺序再放回去(收集过程)，如此往复，一共需要进行d趟，d为元素的位数。</p>
<pre class="brush:php;toolbar:false">/**        
 * Title: 分配排序中的基数排序，不依赖于初始序列  
 * Description: 不是在对元素进行比较的基础上进行排序，而是采用 "分配 + 收集" 的办法 
 * 
 *              首先，将目标序列各元素分配到各个桶中；
 *              其次，将各个桶中的元素按先进先出的顺序再放回去
 *              如此往复...             
 * 
 *              时间复杂度：O(d*(r+n))或者 O(dn),d 的大小一般会受到 n的影响
 *              空间复杂度：O(rd + n)或者 O(n)
 *              稳    定   性：稳定
 *              内部排序(在排序过程中数据元素完全在内存)
 * @author rico       
 * @created 2017年5月20日 上午10:40:00    
 */   
public class RadixSort {

    /**     
     * @description 分配 + 收集
     * @author rico       
     * @created 2017年5月21日 下午9:25:52     
     * @param target 待排序数组
     * @param r 基数
     * @param d 元素的位数
     * @param n 待排序元素个数
     * @return     
     */
    public static int[] radixSort(int[] target, int r, int d, int n){
        if (target != null && target.length != 1 ) {

            int[][] bucket = new int[r][n];  // 一共有基数r个桶，每个桶最多放n个元素
            int digit;  // 获取元素对应位上的数字，即装入那个桶
            int divisor = 1;   // 定义每一轮的除数，1, 10, 100, ...
            int[] count = new int[r];   // 统计每个桶中实际存放元素的个数

            for (int i = 0; i 
<strong>七. 总结</strong>
<p><img src="https://img.php.cn/upload/article/000/000/164/170426878460228.jpg" alt="Explication et comparaison de huit algorithmes de tri"></p>
<span style="color: #1e1e1e; letter-spacing: 2px; border-left: #FF3030 3px solid; border-right: #FF3030 3px solid; padding-left: 8px; padding-right: 8px; font-size: 12pt;"><strong>1、直接插入排序 Vs. 折半插入排序 Vs. 希尔排序</strong></span>
<p>这三种排序方法都属于插入排序的范畴。与直接插入排序的顺序搜索插入位置相比，折半插入排序通过折半搜索的方法搜索插入位置，因此，在搜索插入位置方面，折半插入排序要快于直接插入排序。实际上，折半插入排序比直接插入排序只是减少了关键字之间的比较次数，但是移动次数是没有改变。所以，折半插入排序和插入排序的时间复杂度相同都是O（n^2），但减少了比较次数，所以该算法要比直接插入排序好一点。希尔排序可以看作是对直接插入排序的一种优化，它将全部元素分为间隔为gap的gap个子序列并对每一个子序列进行直接插入排序，同时不断缩小间隔gap，直至所有元素位于同一个序列。使用这种方式可以保证排序效率，因为刚开始时，gap较大，每个子序列元素较少，排序速度较快；待到排序后期，gap变小，每个子序列元素较多，但大部分元素基本有序，所以排序速度仍较快。因此，希尔排序比直接插入排序 、折半插入排序都要高效，但它不是稳定的。</p>
<span style="color: #1e1e1e; letter-spacing: 2px; border-left: #FF3030 3px solid; border-right: #FF3030 3px solid; padding-left: 8px; padding-right: 8px; font-size: 12pt;"><strong>2、直接选择排序 Vs. 堆排序</strong></span>
<p>这两种排序方法都属于插入选择排序的范畴，它们的核心思想都是每一趟都选择一个极值元素放在靠前/靠后位置，直到序列有序。与直接选择排序不同的是，堆排序不是“蛮力选择”，而是不断进行堆调整以取得每趟中的极值。因此，堆排序比直接选择排序要高效，不过它们都是不稳定的。</p>
<span style="color: #1e1e1e; letter-spacing: 2px; border-left: #FF3030 3px solid; border-right: #FF3030 3px solid; padding-left: 8px; padding-right: 8px; font-size: 12pt;"><strong>3、冒泡排序 Vs. 快速排序</strong></span>
<p>这两种排序方法都属于选择排序的范畴，它们的核心思想都是元素的交换，冒泡排序中每一趟相邻元素互相比较，并将较小的交换到前面(较大的自然沉到后面)位置，快速排序则是以基准点为基础，将比它小的元素和比它大的元素分别交换到它的两边。因此，快速排序比冒泡排序要高效，但它不是稳定的。</p>
<span style="color: #1e1e1e; letter-spacing: 2px; border-left: #FF3030 3px solid; border-right: #FF3030 3px solid; padding-left: 8px; padding-right: 8px; font-size: 12pt;"><strong>4、归并排序 Vs. 快速排序</strong></span>
<p>这两种排序方法都属于递归算法的范畴，因此，它们都比较容易让人理解和实现。与快速排序相比，归并排序不但是稳定的，还是与原始序列无关的(不依赖于原始序列的顺序，时间复杂度总是O(nlgn))，但是需要与原始序列一样大小的空间；而快速排序则一般情况下都要比其他高效排序算法（包括归并排序）快，而且空间复杂度只为O(1)。另外，我们从算法实现中可以看出这两种递归算法有以下区别和联系：</p>

• 二者的递归终止条件相同；
• 二者的实现结构较为类似，归并排序是先归后并，快速排序是先分后排；
• 归并排序的核心实现在于有序子序列的合并，而快速排序的核心实现在于对原始序列的划分；

5、小结

直接插入排序、直接选择排序和冒泡排序是基本的排序方法，它们平均情况下的时间复杂度都是O(n^2)，实现也比较简单，它们对规模较小的元素序列很有效。

快速排序、堆排序和归并排序是高效的排序方法，它们平均情况下的时间复杂度都是O(nlgn)，其中快速排序是最通用的高效排序算法，但其是不稳定的；归并排序是上述几种排序算法中唯一与初始序列无关的，而且时间复杂度总是O(nlgn)，但其空间复杂度是O(n)，是一种稳定的排序算法；堆排序的时间复杂度总是O(nlgn)，空间复杂度是O(1)，也是不稳定的。它们对规模较大的元素序列很有效。

L'efficacité du tri Hill se situe entre la méthode de tri de base et la méthode de tri efficace, et il s'agit d'un algorithme de tri instable. Ils ont chacun leurs propres atouts et scénarios d’utilisation spécifiques. Bien que le tri par base ait une complexité temporelle croissante de manière linéaire, son coût réel n'est pas beaucoup plus faible que celui du tri rapide et son application est relativement moins répandue.

Par conséquent, dans les applications pratiques, nous devons faire le choix le plus approprié en fonction des caractéristiques de la tâche réelle et des caractéristiques des différents algorithmes de tri.

8. Plus

Le tri par fusion et le tri rapide sont tous deux des algorithmes récursifs typiques, ils sont donc relativement faciles à comprendre et à mettre en œuvre. Pour une analyse approfondie des idées et connotations récursives, veuillez consulter l'article de blog « Méthodes de conception d'algorithmes : la connotation et les applications classiques de la récursion ».

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!