8つのソートアルゴリズムの説明と比較-Linux-php.cn

＃＃＃導入＃＃＃いわゆる並べ替えとは、並べ替えコードの昇順または降順に従ってデータ要素を並べ替えることで、ランダムに配置された要素のセットが並べ替えに従って線形に並べられた要素のセットになります。コード。この記事では、挿入ソート (直接挿入ソート、ヒルソート)、選択ソート (直接選択ソート、ヒープソート)、交換ソート (バブルソート、クイックソート（クイックソート）ソート）、マージソート、代入ソート（基数ソート）、およびさまざまなアルゴリズムの時間計算量、空間計算量、および安定性を与えます。 フレンドリーなリマインダー:

読者がこのブログ投稿に関連する完全なコードを必要とする場合は、私の Github にアクセスしてご自身で入手してください。プロジェクト名は DataStructure です (特定のアルゴリズムは cn.tju.edu.rico.sort パッケージに実装されています)。プロジェクトのリンクアドレスは https://github.com/githubofrico/DataStructure です。

並べ替えアルゴリズムの概要

いわゆるソートとは、データ要素をソートコードの昇順または降順に従って並べ替えることで、任意に配置された要素のセットがソートコードに従って線形に順序付けされた要素のセットになります。この記事では、挿入ソート (直接挿入ソート、ヒルソート)、選択ソート (直接選択ソート、ヒープソート)、交換ソート (バブルソート、クイックソート)、マージを含む、最も古典的で一般的に使用される 8 つの内部ソートアルゴリズムを紹介します。ソート、分布ソート（基数ソート）。実際、基本的なソート方法 (直接挿入ソート、直接選択ソート、バブルソート) であっても、効率的なソート方法 (クイックソート、ヒープソート、マージソート) などであっても、それぞれに独自の長所と具体的な使用方法があります。シナリオ。したがって、実際のアプリケーションでは、実際のタスクの特性とさまざまなソートアルゴリズムの特性に基づいて、最適な選択を行う必要があります。一般に、アルゴリズムを測定するために使用する指標には次のものが含まれます:

時間の複雑さ (ソート中に必要な比較と交換の回数)
スペースの複雑さ (仕分け中に必要な補助保管スペース)
安定性 (アルゴリズムの実装がソート後の等しい要素の初期順序を保証できるかどうか。この機能を保証できるアルゴリズムの実装がある限り、アルゴリズムは安定しています)
内部ソート/外部ソート (ソートプロセス中にデータ要素が完全にメモリ内にあるかどうか)

この記事では、著者は上記の 8 つの並べ替えアルゴリズムのアイデアと実装に焦点を当て、それぞれのアプリケーションシナリオをさらに理解するために、上記の指標に従って各アルゴリズムを分析および分類します。

2. 挿入ソート

挿入ソートの基本的な考え方: 各ステップで、ソート対象の要素は、ソートコードサイズに従って、以前にソートされた要素のグループに挿入されます。すべての要素は挿入されるまで有効です。ここでは、直接挿入ソート、ヒルソート、および途中挿入ソートの 3 つの具体的な挿入ソートアルゴリズムを紹介します。

1. 直接挿入ソート

直接挿入ソートの考え方: i 番目 (i>=1) の要素を挿入するとき、前の V[0],...,V [i-1] i-1 個の要素がソートされるまで待ちます。このとき、i 番目の要素とそれ以前の i-1 個の要素 V[i-1],...,V[0] を順に比較し、挿入位置が見つかったら V[i] を挿入します。同時に、元の位置にある要素が後方に向かって順次挿入されます。ここで、挿入位置の検索は逐次検索である。直接挿入ソートは安定したソートアルゴリズムであり、その実装は次のとおりです:

リーリー 2. ヒルソート

ヒルソートの考え方: ソート対象のシーケンスに合計 n 個の要素があると仮定します。まず、間隔として整数のギャップリーリー 3. 途中挿入ソート

半挿入ソートの考え方: i 番目 (i>=1) の要素を挿入するとき、前の V[0],...,V [i-1] i-1 個の要素がソートされるまで待ちます。このとき、直前の i-1 要素 V[i-1],...,V[0] の中から i 番目の要素の挿入位置を半分に探し、V[i] を直接挿入します。元の位置にある要素は後で移動に移動されます。直接挿入ソートと異なり、半挿入ソートは直接挿入ソートよりもキーワード間の比較回数を大幅に減らしますが、移動回数は変わりません。したがって、半挿入ソートと挿入ソートの時間計算量は同じ O(N^2) ですが、比較の回数が減るため、アルゴリズムは依然として直接挿入ソートよりも優れています。途中挿入ソートは安定したソートアルゴリズムであり、その実装は次のとおりです。

/**        
 * 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="8つのソートアルゴリズムの説明と比較"></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)，也是不稳定的。它们对规模较大的元素序列很有效。

Hill ソートの効率は基本ソート法と効率的ソート法の中間であり、不安定なソートアルゴリズムです。それぞれに独自の強みと特定の使用シナリオがあります。基数ソートの時間計算量は直線的に増加しますが、実際のコストはクイックソートよりはるかに小さいわけではなく、そのアプリケーションは比較的広く普及していません。

したがって、実際のアプリケーションでは、実際のタスクの特性とさまざまなソートアルゴリズムの特性に基づいて、最適な選択を行う必要があります。

8. 詳細

マージソートとクイックソートはどちらも典型的な再帰アルゴリズムであるため、理解と実装が比較的簡単です。再帰的なアイデアとコノテーションの詳細な分析については、ブログ投稿「アルゴリズム設計方法: 再帰のコノテーションと古典的なアプリケーション」を参照してください。

以上が8つのソートアルゴリズムの説明と比較の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。