suchen

Heim >System-Tutorial >LINUX >Erklärung und Vergleich von acht Sortieralgorithmen

Erklärung und Vergleich von acht Sortieralgorithmen

PHPz
PHPznach vorne
2024-01-03 15:59:431124Durchsuche
Einführung Die sogenannte Sortierung besteht darin, die Datenelemente entsprechend der aufsteigenden oder absteigenden Reihenfolge des Sortiercodes anzuordnen, sodass aus einer Menge willkürlich angeordneter Elemente eine Menge linear geordneter Elemente entsprechend ihrem Sortiercode wird. In diesem Artikel werden die Grundideen und die Implementierung der acht klassischsten und am häufigsten verwendeten internen Sortieralgorithmen vorgestellt, darunter Einfügungssortierung (direkte Einfügungssortierung, Hill-Sortierung), Auswahlsortierung (direkte Auswahlsortierung, Heap-Sortierung), Austauschsortierung (Blasensortierung). Schnellsortierung), Zusammenführungssortierung, Zuweisungssortierung (Basissortierung) und Angabe der zeitlichen Komplexität, räumlichen Komplexität und Stabilität verschiedener Algorithmen.
Freundliche Erinnerung:

Wenn Leser den vollständigen Code für diesen Blog-Beitrag benötigen, gehen Sie bitte zu meinem Github, um ihn selbst abzurufen. Der Projektname lautet DataStructure (der spezifische Algorithmus ist im Paket cn.tju.edu.rico.sort implementiert). Die Linkadresse des Projekts lautet: https://github.com/githubofrico/DataStructure.

Übersicht über Sortieralgorithmen

Die sogenannte Sortierung besteht darin, die Datenelemente entsprechend der aufsteigenden oder absteigenden Reihenfolge des Sortiercodes anzuordnen, sodass aus einer Menge willkürlich angeordneter Elemente eine Menge linear geordneter Elemente entsprechend ihrem Sortiercode wird. In diesem Artikel werden die acht klassischsten und am häufigsten verwendeten internen Sortieralgorithmen vorgestellt, darunter Einfügungssortierung (direkte Einfügungssortierung, Hill-Sortierung), Auswahlsortierung (direkte Auswahlsortierung, Heap-Sortierung), Austauschsortierung (Blasensortierung, schnelle Sortierung) und Zusammenführung sort., Verteilungssortierung (Basissortierung). Unabhängig davon, ob es sich um eine grundlegende Sortiermethode (direkte Einfügungssortierung, direkte Auswahlsortierung, Blasensortierung) oder eine effiziente Sortiermethode (schnelle Sortierung, Heap-Sortierung, Zusammenführungssortierung) usw. handelt, haben sie alle ihre eigenen Stärken und spezifischen Verwendungszwecke Szenarien. Daher müssen wir in praktischen Anwendungen die am besten geeignete Wahl basierend auf den Merkmalen der tatsächlichen Aufgabe und den Merkmalen verschiedener Sortieralgorithmen treffen. Zu den Indikatoren, die wir zur Messung eines Algorithmus verwenden, gehören im Allgemeinen:

  • Zeitliche Komplexität (Anzahl der beim Sortieren erforderlichen Vergleiche und Austausche)
  • Platzkomplexität (zusätzlicher Lagerraum beim Sortieren erforderlich)
  • Stabilität (Ob die Implementierung des Algorithmus die anfängliche Reihenfolge gleicher Elemente nach dem Sortieren garantieren kann, solange es eine Implementierung des Algorithmus gibt, die diese Funktion garantieren kann, ist der Algorithmus stabil)
  • Interne Sortierung/externe Sortierung (ob die Datenelemente während des Sortiervorgangs vollständig im Speicher sind)

In diesem Artikel konzentriert sich der Autor auf die Ideen und Implementierung der oben genannten acht Sortieralgorithmen und analysiert und klassifiziert jeden Algorithmus anhand der oben genannten Indikatoren, um sich mit den jeweiligen Anwendungsszenarien besser vertraut zu machen.

2. Einfügungssortierung

Die Grundidee der Einfügesortierung: In jedem Schritt wird ein zu sortierendes Element entsprechend seiner Sortiercodegröße in eine Gruppe zuvor sortierter Elemente eingefügt, bis alle Elemente eingefügt sind. Hier stellen wir drei spezifische Einfügungssortierungsalgorithmen vor: direkte Einfügungssortierung, Hill-Sortierung und halbe Einfügungssortierung.

1. Direkteinfügungssortierung

Die Idee der direkten Einfügungssortierung: Beim Einfügen des i-Elements (i>=1) werden die vorherigen i-1-Elemente wie V[0],...,V[i-1] berücksichtigt schon in ordnung. Zu diesem Zeitpunkt wird das i-te Element nacheinander mit den vorherigen i-1 Elementen V[i-1], ..., V[0] verglichen und V[i] eingefügt, wenn die Einfügeposition gefunden wird. Gleichzeitig werden die Elemente an der ursprünglichen Position nacheinander rückwärts eingefügt. Hier ist die Suche an der Einfügeposition eine sequentielle Suche. Die Direkteinfügungssortierung ist ein stabiler Sortieralgorithmus. Seine Implementierung ist wie folgt: 

/**        
 * 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. Hügelsortierung</strong></span>
<p><span style="color: red;"><strong>Die Idee der Hill-Sortierung: </strong></span>Angenommen, die zu sortierende Sequenz hat insgesamt n Elemente. Nehmen Sie zunächst eine ganzzahlige Lücke 
</p><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. Sortierung auf halbem Weg

Die Idee der Halbeinfügungssortierung: Beim Einfügen des i-Elements (i>=1) werden die vorherigen i-1-Elemente wie V[0],...,V[i-1] verwendet schon in Ordnung. Suchen Sie zu diesem Zeitpunkt in zwei Hälften nach der Einfügeposition des i-ten Elements in den vorherigen i-1-Elementen V [i-1], ..., V [0] und fügen Sie dann V [i] direkt ein Gleichzeitig wird das Element an der ursprünglichen Position auf „Später verschieben“ verschoben. Im Gegensatz zur Direkteinfügungssortierung reduziert die Halbeinfügungssortierung die Anzahl der Vergleiche zwischen Schlüsselwörtern erheblich als die Direkteinfügungssortierung, die Anzahl der Verschiebungen ändert sich jedoch nicht. Daher ist die zeitliche Komplexität der Halbeinfügungssortierung und der Einfügungssortierung gleich, nämlich O (N ^ 2), verringert jedoch die Anzahl der Vergleiche, sodass der Algorithmus immer noch besser ist als die Direkteinfügungssortierung. Die Sortierung auf halbem Weg ist ein stabiler Sortieralgorithmus und seine Implementierung ist wie folgt: 

/**        
 * 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="Erklärung und Vergleich von acht Sortieralgorithmen"></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)，也是不稳定的。它们对规模较大的元素序列很有效。

Die Effizienz der Hill-Sortierung liegt zwischen der grundlegenden Sortiermethode und der effizienten Sortiermethode und ist ein instabiler Sortieralgorithmus. Sie alle haben ihre eigenen Stärken und spezifischen Einsatzszenarien. Obwohl die Radix-Sortierung eine linear zunehmende Zeitkomplexität aufweist, sind ihre tatsächlichen Kosten nicht viel geringer als die der Schnellsortierung und ihre Anwendung ist relativ weniger verbreitet.

Daher müssen wir in praktischen Anwendungen die am besten geeignete Wahl basierend auf den Merkmalen der tatsächlichen Aufgabe und den Merkmalen verschiedener Sortieralgorithmen treffen.

8. Mehr

Merge-Sort und Schnellsortierung sind beide typische rekursive Algorithmen und daher relativ einfach zu verstehen und zu implementieren. Eine ausführliche Analyse rekursiver Ideen und Konnotationen finden Sie im Blogbeitrag „Algorithm Design Methods: The Connotation and Classic Applications of Recursion“.

Das obige ist der detaillierte Inhalt vonErklärung und Vergleich von acht Sortieralgorithmen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!

sort 递归 冒泡排序 选择排序 插入排序 希尔排序 归并排序 快速排序 堆 github 算法 https
Stellungnahme：
Dieser Artikel ist reproduziert unter:linuxprobe.com. Bei Verstößen wenden Sie sich bitte an admin@php.cn löschen
Vorheriger Artikel：Das Linux-Projekt: Dem Projekt neues Leben einhauchenNächster Artikel：Das Linux-Projekt: Dem Projekt neues Leben einhauchen

In Verbindung stehende Artikel

Mehr sehen