cari

Rumah >Tutorial sistem >LINUX >Penjelasan dan perbandingan lapan algoritma pengisihan

Penjelasan dan perbandingan lapan algoritma pengisihan

PHPz
PHPzke hadapan
2024-01-03 15:59:431122semak imbas
Pengenalan Apa yang dipanggil pengisihan adalah untuk menyusun elemen data mengikut susunan mengikut susunan kod pengisihan yang meningkat atau menurun, supaya satu set elemen yang disusun secara sewenang-wenangnya menjadi satu set elemen tersusun secara linear mengikut kod pengisihannya. Artikel ini akan memperkenalkan idea asas dan pelaksanaan lapan algoritma pengisihan dalaman yang paling klasik dan biasa digunakan, termasuk isihan sisipan (isih sisipan langsung, jenis bukit), isihan pemilihan (isih pemilihan langsung, isihan timbunan), isihan pertukaran (isih gelembung, Isih cepat) Isih), isih gabung, isih tugasan (isih radix), dan beri kerumitan masa, kerumitan ruang dan kestabilan pelbagai algoritma.
Peringatan mesra:

Jika pembaca memerlukan kod lengkap yang berkaitan dengan catatan blog ini, sila pergi ke Github saya untuk mendapatkannya sendiri Nama projek ialah DataStructure (algoritma khusus dilaksanakan dalam pakej cn.tju.edu.rico.sort), dan alamat pautan projek ialah: https://github .com/githubofrico/DataStructure.

Gambaran keseluruhan algoritma pengisihan

Apa yang dipanggil pengisihan adalah untuk menyusun elemen data mengikut susunan mengikut susunan kod pengisihan yang meningkat atau menurun, supaya satu set elemen yang disusun secara sewenang-wenangnya menjadi satu set elemen tersusun secara linear mengikut kod pengisihannya. Artikel ini akan memperkenalkan lapan algoritma pengisihan dalaman yang paling klasik dan biasa digunakan, termasuk isihan sisipan (isih sisipan langsung, isihan bukit), isihan pemilihan (isih pemilihan langsung, isihan timbunan), isihan pertukaran (isih gelembung, isihan cepat) dan cantuman. sort. , sort distribution (isih radix). Malah, sama ada kaedah pengisihan asas (isihan sisipan langsung, isihan pemilihan langsung, isihan gelembung) atau kaedah isihan yang cekap (isih cepat, isihan timbunan, isihan gabungan), dsb., semuanya mempunyai kekuatan dan penggunaan khusus masing-masing. senario. Oleh itu, dalam aplikasi praktikal, kita mesti membuat pilihan yang paling sesuai berdasarkan ciri-ciri tugas sebenar dan ciri-ciri pelbagai algoritma pengisihan. Secara amnya, penunjuk yang kami gunakan untuk mengukur algoritma termasuk:

  • Kerumitan masa (bilangan perbandingan dan pertukaran diperlukan semasa pengisihan)
  • Kerumitan ruang (ruang simpanan tambahan diperlukan semasa pengisihan)
  • Kestabilan (Sama ada pelaksanaan algoritma boleh menjamin susunan awal elemen yang sama selepas pengisihan, selagi terdapat pelaksanaan algoritma yang boleh menjamin ciri ini, maka algoritma adalah stabil)
  • Isihan dalaman/isihan luaran (sama ada elemen data berada dalam ingatan sepenuhnya semasa proses pengisihan)

Dalam artikel ini, penulis akan menumpukan pada idea dan pelaksanaan lapan algoritma pengisihan di atas, dan menganalisis serta mengklasifikasikan setiap algoritma mengikut penunjuk di atas untuk membiasakan diri dengan senario aplikasi masing-masing.

2. Isih sisipan

Idea asas isihan sisipan: Dalam setiap langkah, elemen yang hendak diisih dimasukkan ke dalam kumpulan elemen yang telah diisih sebelumnya mengikut saiz kod isihannya, sehingga semua elemen dimasukkan. Di sini, kami memperkenalkan tiga algoritma isihan sisipan khusus: isihan sisipan langsung, isihan bukit dan isihan sisipan separuh jalan.

1. Isih sisipan terus

Idea penyisihan sisipan terus: Apabila elemen i (i>=1) disisipkan, elemen i-1 sebelumnya seperti V[0],...,V[i-1] sudah teratur. Pada masa ini, elemen ke-i dibandingkan dengan elemen i-1 sebelumnya V[i-1],...,V[0] dalam urutan, dan V[i] dimasukkan apabila kedudukan sisipan ditemui. Pada masa yang sama, elemen pada kedudukan asal dimasukkan secara berurutan ke belakang. Di sini, carian pada kedudukan sisipan ialah carian berurutan. Isih sisipan langsung ialah algoritma pengisihan yang stabil, pelaksanaannya adalah seperti berikut: 

/**        
 * 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. Pengasingan bukit</strong></span>
<p><span style="color: red;"><strong>Idea ​​Bukit: </strong></span>Andaikan urutan yang hendak diisih mempunyai jumlah keseluruhan n elemen Mula-mula, ambil jurang integer<n sebagai selang bahagikan semua elemen kepada jujukan jurang dengan jurang. dan lakukan pemprosesan langsung pada setiap urutan sisipan. kemudian kurangkan ulangi operasi di atas sehingga mengecil masa ini berada dalam yang sama teratur. kerana permulaannya adalah besar mempunyai lebih sedikit unsur kelajuan pengisihan cepat peringkat akhir penyisihan menjadi kecil banyak tetapi kebanyakan dasarnya disusun jadi masih agak perlahan. secara amnya ialah bukit kaedah tidak stabil pelaksanaannya seperti berikut:>
<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. Isih sisipan separuh jalan

Idea jenis sisipan separuh: Apabila memasukkan elemen i (i>=1), elemen i-1 sebelumnya seperti V[0],...,V[i-1] ialah sudah teratur. Pada masa ini, cari separuh untuk kedudukan sisipan unsur ke-i dalam unsur i-1 sebelumnya V[i-1],...,V[0], dan kemudian masukkan V[i] secara langsung, dan pada masa yang sama, elemen pada kedudukan asal dialihkan ke Move kemudian. Berbeza daripada isihan sisipan langsung, isihan separuh sisipan mengurangkan bilangan perbandingan antara kata kunci berbanding isihan sisipan langsung, tetapi bilangan pergerakan tidak berubah. Oleh itu, kerumitan masa isihan separuh sisipan dan jenis sisipan adalah sama, iaitu O(N^2), tetapi ia mengurangkan bilangan perbandingan, jadi algoritma masih lebih baik daripada jenis sisipan langsung. Isih sisipan separuh jalan ialah algoritma pengisihan yang stabil dan pelaksanaannya adalah seperti berikut: 

/**        
 * 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="Penjelasan dan perbandingan lapan algoritma pengisihan"></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)，也是不稳定的。它们对规模较大的元素序列很有效。

Kecekapan pengisihan Bukit adalah antara kaedah pengisihan asas dan kaedah pengisihan yang cekap, dan ia merupakan algoritma pengisihan yang tidak stabil. Mereka masing-masing mempunyai kekuatan sendiri dan senario penggunaan tertentu. Walaupun jenis radix mempunyai kerumitan masa yang meningkat secara linear, kos sebenarnya tidak jauh lebih kecil daripada isihan cepat, dan penggunaannya secara relatifnya kurang meluas.

Oleh itu, dalam aplikasi praktikal, kita mesti membuat pilihan yang paling sesuai berdasarkan ciri-ciri tugas sebenar dan ciri-ciri pelbagai algoritma pengisihan.

8. Lagi

Isih gabung dan isihan pantas ialah kedua-dua algoritma rekursif biasa, jadi ia agak mudah difahami dan dilaksanakan. Untuk analisis mendalam tentang idea dan konotasi rekursif, sila lihat catatan blog "Kaedah Reka Bentuk Algoritma: Konotasi dan Aplikasi Klasik Rekursi".

Atas ialah kandungan terperinci Penjelasan dan perbandingan lapan algoritma pengisihan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!

sort 递归 冒泡排序 选择排序 插入排序 希尔排序 归并排序 快速排序 堆 github 算法 https
Kenyataan：
Artikel ini dikembalikan pada:linuxprobe.com. Jika ada pelanggaran, sila hubungi admin@php.cn Padam
Artikel sebelumnya：Projek Linux: Menghirup Kehidupan Baharu ke dalam ProjekArtikel seterusnya：Projek Linux: Menghirup Kehidupan Baharu ke dalam Projek

Artikel berkaitan

Lihat lagi