插入排序 订阅
插入排序,一般也被称为直接插入排序。对于少量元素的排序,它是一个有效的算法 [1]  。插入排序是一种最简单的排序方法,它的基本思想是将一个记录插入到已经排好序的有序表中,从而一个新的、记录数增1的有序表。在其实现过程使用双层循环,外层循环对除了第一个元素之外的所有元素,内层循环对当前元素前面有序表进行待插入位置查找,并进行移动 [2]  。 展开全文
插入排序,一般也被称为直接插入排序。对于少量元素的排序,它是一个有效的算法 [1]  。插入排序是一种最简单的排序方法,它的基本思想是将一个记录插入到已经排好序的有序表中,从而一个新的、记录数增1的有序表。在其实现过程使用双层循环,外层循环对除了第一个元素之外的所有元素,内层循环对当前元素前面有序表进行待插入位置查找,并进行移动 [2]  。
信息
外文名
Insertion sort
空间复杂度
O(1)
别    称
直接插入排序
分    类
排序方法
中文名
插入排序
时间复杂度
O(N^(1-2))
稳定性
稳定
插入排序基本思想
插入排序的工作方式像许多人排序一手扑克牌。开始时,我们的左手为空并且桌子上的牌面向下。然后,我们每次从桌子上拿走一张牌并将它插入左手中正确的位置。为了找到一张牌的正确位置,我们从右到左将它与已在手中的每张牌进行比较。拿在左手上的牌总是排序好的,原来这些牌是桌子上牌堆中顶部的牌 [1]  。插入排序是指在待排序的元素中,假设前面n-1(其中n>=2)个数已经是排好顺序的,现将第n个数插到前面已经排好的序列中,然后找到合适自己的位置,使得插入第n个数的这个序列也是排好顺序的。按照此法对所有元素进行插入,直到整个序列排为有序的过程,称为插入排序 [3]  。
收起全文
精华内容
下载资源
问答
  • 2021-11-25 11:24:45


    插入排序的基本思想

    插入排序是一种简单直观的排序方法,其基本思想是:每一次将一个待排记录按其关键字大小插入到前面已经排好序的有序子序列中,直到全部记录插入完成。

    由插入排序的思想可以引申出三个重要的排序算法:

    • 直接插入排序
    • 折半插入排序
    • 希尔排序


    直接插入排序

    直接插入排序的算法思想

    根据插入排序的思想,不难得出一种最简单、最直观的直接插入排序算法。
    假设在排序过程中,待排序表 L [ 1... n ] L[1...n] L[1...n]在某次排序过程中的某一时刻状态如下:
    在这里插入图片描述
    要将元素 L [ i ] L[i] L[i]插入到已经有序的子序列 L [ 1 , i + 1 ] L[1,i+1] L[1,i+1]中,需要执行以下操作:

    1、 查找出 L [ i ] L[i] L[i] L [ 1 , i + 1 ] L[1,i+1] L[1i+1]中的插入位置 k k k
    2、 将 L [ k . . . i − 1 ] L[k...i-1] L[k...i1]中的所有元素全部后移一个位置;
    3、 将 L [ i ] L[i] L[i]复制到 L [ k ] L[k] L[k]

    那么实现对一个序列 L [ 1... n ] L[1...n] L[1...n]的排序,可以将 L [ 2 ] L[2] L[2]~ L [ n ] L[n] L[n]依次插入到前面已经排好序的子序列中,初始假定 L [ 1 ] L[1] L[1]是一个已经排好序的子序列。
    上述操作执行 n − 1 n-1 n1次就能得到一个有序表。

    直接插入排序的示例:

    初始序列: 4 , 5 , 1 , 2 , 6 , 3 4,5,1,2,6,3 4,5,1,2,6,3
    第一趟:   [ 4 , 5 ] , 1 , 2 , 6 , 3 [4,5],1,2,6,3 [4,5],1,2,6,3 ( 将 5 5 5插入{ 4 4 4} )
    第二趟:   [ 1 , 4 , 5 ] , 2 , 6 , 3 [1,4,5],2,6,3 [1,4,5],2,6,3 ( 将 1 1 1插入{ 4 , 5 4,5 4,5} )
    第三趟:   [ 1 , 2 , 4 , 5 ] , 6 , 3 [1,2,4,5],6,3 [1,2,4,5],6,3 ( 将 2 2 2插入{ 1 , 4 , 5 1,4,5 1,4,5} )
    第四趟:   [ 1 , 2 , 4 , 5 , 6 ] , 3 [1,2,4,5,6],3 [1,2,4,5,6],3 ( 将 6 6 6插入{ 1 , 2 , 4 , 5 1,2,4,5 1,2,4,5} )
    第五趟:   [ 1 , 2 , 3 , 4 , 5 , 6 ] [1,2,3,4,5,6] [1,2,3,4,5,6] ( 将 3 3 3插入{ 1 , 2 , 4 , 5 , 6 1,2,4,5,6 1,2,4,5,6} )


    直接插入排序的实现代码

    //直接插入排序
    void InsertSort(SeqList &L){
        int i,j;
        for(i=2; i<L.n; i++){ //将L[2]~L[n]插入到前面已经排好序的序列中
            if(L.data[i] < L.data[i-1]){ //如果data[i]的关键码小于其前驱,那么就要找插入位置
                L.data[0] = L.data[i]; //0号为哨兵,暂存data[i]的值
                for(j=i-1; L.data[0]<L.data[j]; j--){ //从后往前查找插入位置
                    L.data[j+1] = L.data[j]; //后移
                }
                L.data[j+1] = L.data[0]; //复制到插入位置
                //由于L.data[j]刚刚比较完毕,即L.data[j]<L.data[0],
                //退出了循环,故j+1为正确的插入位置
            }
        }
    }
    

    这里再次用到了我们前面文章顺序查找中提到的“哨兵”。

    其实作用大致相同,在这里主要有两个:

    • 在找到插入位置之前暂存 L . d a t a [ i ] L.data[i] L.data[i]的值
    • 充当哨兵,即在查找插入位置的循环中,不必判断下标是否越界,因为在 j = = i j==i j==i时一定会跳出循环。

    直接插入排序算法是边比较边移动元素
    考虑到文章的可读性,直接插入排序的完整代码在文章结尾,下同。


    直接插入排序的性能分析

    空间复杂度

    仅使用了常数个辅助单元(一个用于暂存要插入元素的辅助空间 L . d a t a [ 0 ] L.data[0] L.data[0]),因而空间复杂度为 O ( 1 ) O(1) O(1)

    时间复杂度

    在排序过程中,向有序子序列中逐个地插入元素地操作进行了 n − 1 n-1 n1 趟,每趟操作都分为比较关键字移动元素,而比较次数和移动次数取决于待排序表的初始状态

    • 最好情况:表中元素已经有序(正序),此时每次插入一个元素,都只需要比较一次而不用以到元素,因此时间复杂度为 O ( n ) O(n) O(n)
      • 每趟比较1次,总共比较n-1次
      • 每趟移动0次
    • 最坏情况:表中元素顺序正好与排序结果中的元素顺序相反(逆序),总的比较次数达到最大,总的移动次数也达到最大。
      • i i i 趟比较 i + 1 i+1 i+1 次,即下标为 i i i 的元素需要与前 i i i个元素都比较一次,故总的比较次数为 2 + 3 + . . . + n = ( n − 1 ) ( n + 2 ) 2 2+3+...+n =\frac{(n-1)(n+2)}{2} 2+3+...+n=2(n1)(n+2)
      • 每比较一次都要移动一次,然后再将要插入的元素填入,故第 i i i 趟移动 i + 2 i+2 i+2 次,总的移动次数为 3 + 4 + . . . + n + 1 = ( n − 1 ) ( n + 4 ) 2 3+4+...+n+1 = \frac{(n-1)(n+4)}{2} 3+4+...+n+1=2(n1)(n+4)
    • 平均情况:考虑到待排序表中的元素是随机的,此时可以去上述最好和最坏情况下的平均值作为平均情况下的时间复杂度。
      • 总的比较次数和移动次数均约为 n 2 / 4 n^2/4 n2/4

    因此,直接插入排序算法的时间复杂度为 O ( n 2 ) O(n^2) O(n2)
    【注】虽然折半插入排序算法的时间复杂度也为 O ( n 2 ) O(n^2) O(n2),但对于数据量比较小的排序表,折半插入排序往往能表现出很好的性能。

    稳定性

    由于每次插入元素时总是从后向前先比较再移动,所以不会出现相同元素相对位置发生变化的情况,即直接插入排序是一个稳定的排序算法

    适用性

    直接插入排序适用于顺序存储和链式存储的线性表。其中链式存储时,可以从前往后查找指定元素的位置。(而大部分排序算法仅适用于顺序存储的线性表

    序列中的记录基本有序或者待排记录较少时,直接插入排序是最佳算法。


    折半插入排序

    折半插入排序的算法思想

    从直接插入排序算法中,可以看出每趟插入的过程都进行了两项工作:

    • 从前面的有序子序列中找到待插入元素应该被插入的位置
    • 给插入位置腾出空间,将待插入元素复制到表的插入位置。

    注意,直接插入排序是边比较边移动元素的

    若将比较和移动操作分离,即先折半查找出元素的待插入位置,然后统一地移动待插入位置之后的所有元素,这就是折半插入排序算法。


    折半插入排序的实现代码

    //折半插入排序
    void BinaryInsertSort(SeqList &L){
        int i,j,low,high,mid;
        for(i=2; i<L.n; i++){ //将L[2]~L[n]插入到前面已经排好序的序列中
            L.data[0] = L.data[i]; //0号为哨兵,暂存data[i]的值
            low=1;
            high = i-1; //设置折半查找的范围
            while(low<=high){ //查找插入位置
                mid = (low+high)/2;
                if(L.data[0]<L.data[mid]) high=mid-1; //查找左半子表
                else low=mid+1;  //查找右半子表
            }
            for(j=i-1; j>=high+1; j--){
                L.data[j+1] = L.data[j]; //后移元素,腾出插入位置
            }
            L.data[high+1] = L.data[0]; //插入
        }
    }
    

    折半插入排序的性能分析

    空间复杂度

    仅使用了常数个辅助单元(一个用于暂存要插入元素的辅助空间 L . d a t a [ 0 ] L.data[0] L.data[0]),因而空间复杂度为 O ( 1 ) O(1) O(1)

    时间复杂度

    时间复杂度包括在排序过程中的关键码的比较次数元素移动次数

    • 关键码的比较次数与待排序列的初始状态无关仅取决于表中的元素个数 n n n,插入第 i i i 个元素时,关键码的比较次数大约是 l o g 2 ( i + 1 ) log_2(i+1) log2(i+1),故总的比较次数约为 O ( n l o g 2 n ) O(nlog_2n) O(nlog2n)
    • 元素的移动次数取决于待排序表的初始状态,与直接插入排序相同,可参照上一部分。
      • 最好情况:移动0次
      • 最坏情况:移动 ( n − 1 ) ( n + 4 ) 2 \frac{(n-1)(n+4)}{2} 2(n1)(n+4)
      • 平均情况:移动次数约为 n 2 / 4 n^2/4 n2/4

    折半插入排序的时间复杂度仍为 O ( n 2 ) O(n^2) O(n2)

    稳定性

    不难得知,折半插入排序与直接插入排序一样,也是一种稳定的排序方法

    适用性

    n n n较大时,总关键码的比较次数比直接插入排序的最差情况要好得多。
    故折半插入排序适用于 n n n 较大的情况,并且一般为顺序存储的线性表,当线性表为链式存储时难以实现。


    希尔排序

    希尔排序的算法思想

    希尔排序又称为缩小增量排序,其算法思想为:

    每趟按照一个增量 d i d_i di 作为间隔,将全部元素序列分为 d i d_i di 个子序列,所有距离为 d i d_i di 的元素放在同一个子序列中,在每一个子序列中分别进行直接插入排序。然后缩小增量 d i d_i di,重复上面的子序列划分和排序操作,直到最后取 d i = 1 d_i=1 di=1,将所有元素放在同一个序列中排序为止。

    由于开始时, d i d_i di 的取值较大,每个子序列中的元素较少,所以排序速度较快;等到排序的后期, d i d_i di 取值逐渐变小,子序列中的元素逐个变多,但由于前面工作的基础,大多数元素已经基本有序,故排序速度依然很快。

    希尔排序的示例:

    ( 下面过程中同色为同一子序列,需要进行排序操作 )

    原始序列:     50 , 26 , 38 , 80 , 70 , 90 , 8 , 30 , 40 , 20 50,26,38,80,70,90,8,30,40,20 50,26,38,80,70,90,8,30,40,20,并且规定 d = { 5 , 3 , 1 } d=\{5,3,1\} d={5,3,1}

    第一趟(增量 5 5 5):
    在这里插入图片描述
    排序结果为:
    在这里插入图片描述

    第二趟(增量为3):
    在这里插入图片描述
    排序结果为:
    在这里插入图片描述

    第三趟(增量为1):
    在这里插入图片描述
    排序结果为:
    在这里插入图片描述


    希尔排序的实现代码

    //希尔排序
    void ShellSort(SeqList &L){
        int d,i,j;
        int n = L.n-1; //除去L.data[0],n是待排元素个数
        //前后位置记录的增量是d,不是1
        //这里的L.data[0]只是暂存单元,不是哨兵;当j<=0时,插入位置已到
        for(d=n/2; d>=1; d=d/2){
            for(i=d+1; i<=n; i++){
                if(L.data[i] < L.data[i-d]){ //说明需要将L.data[i]插入到前面的有序增量子表中
                    L.data[0] = L.data[i];  //L.data[0]暂存该值
                    for(j=i-d; j>0&&L.data[0]<L.data[j]; j-=d){ //注意每次变化是d
                        L.data[j+d] = L.data[j];  //记录后移,查找插入位置
                    }
                    L.data[j+d] = L.data[0]; //插入
                }
            }
        }
    }
    

    一般初始增量 d = n / 2 d=n/2 d=n/2,且 d i + 1 = d i / 2 d_{i+1}=d_i/2 di+1=di/2,并且最后一个增量为1。


    希尔排序的性能分析

    空间复杂度

    仅使用了常数个辅助单元(一个用于暂存要插入元素的辅助空间 L . d a t a [ 0 ] L.data[0] L.data[0]),因而空间复杂度为 O ( 1 ) O(1) O(1)

    时间复杂度

    由于希尔排序的时间复杂度依赖于增量序列的函数,这涉及数学上尚未解决的难题,所以其时间复杂度分析比较困难。
    n n n在某个特定范围时,希尔排序的时间复杂度约为 O ( n 1.3 ) O(n^{1.3}) O(n1.3),在最坏情况下希尔排序的时间复杂度为 O ( n 2 ) O(n^2) O(n2)

    稳定性

    当相同的关键字被划分到不同的子表时,可能会改变它们之间的相对次序,因此希尔排序是一种不稳定的排序方法

    适用性

    希尔排序算法仅适用于线性表为顺序存储的情况。


    完整代码

    #include<bits/stdc++.h>
    using namespace std;
    
    //设待排序序列存储在静态分配的顺序表中
    #define maxSize 20
    typedef struct{
        int data[maxSize];
        int n; //元素个数,初始为1,即留出0号位置
    }SeqList;
    
    //输入待排序列并存入顺序表中
    void CreateList(SeqList &L, int n){
        L.n = n+1; //从下标1开始存储
        for(int i=1; i<=n; i++){
            int x;
            cin>>x;
            L.data[i] = x;
        }
    }
    //输出序列
    void PrintList(SeqList L){
        for(int i=1; i<L.n; i++){ //0号预留,从1开始存储数据,故从1开始输出
            cout<<L.data[i]<<" ";
        }
        cout<<endl;
    }
    //直接插入排序
    void InsertSort(SeqList &L){
        int i,j;
        for(i=2; i<L.n; i++){ //将L[2]~L[n]插入到前面已经排好序的序列中
            if(L.data[i] < L.data[i-1]){ //如果data[i]的关键码小于其前驱,那么就要找插入位置
                L.data[0] = L.data[i]; //0号为哨兵,暂存data[i]的值
                for(j=i-1; L.data[0]<L.data[j]; j--){ //从后往前查找插入位置
                    L.data[j+1] = L.data[j]; //后移
                }
                L.data[j+1] = L.data[0]; //复制到插入位置
                //由于L.data[j]刚刚比较完毕,即L.data[j]<L.data[0],
                //退出了循环,故j+1为正确的插入位置
            }
        }
    }
    
    //折半插入排序
    void BinaryInsertSort(SeqList &L){
        int i,j,low,high,mid;
        for(i=2; i<L.n; i++){ //将L[2]~L[n]插入到前面已经排好序的序列中
            L.data[0] = L.data[i]; //0号为哨兵,暂存data[i]的值
            low=1;
            high = i-1; //设置折半查找的范围
            while(low<=high){ //查找插入位置
                mid = (low+high)/2;
                if(L.data[0]<L.data[mid]) high=mid-1; //查找左半子表
                else low=mid+1;  //查找右半子表
            }
            for(j=i-1; j>=high+1; j--){
                L.data[j+1] = L.data[j]; //后移元素,腾出插入位置
            }
            L.data[high+1] = L.data[0]; //插入
        }
    }
    
    //希尔排序
    void ShellSort(SeqList &L){
        int d,i,j;
        int n = L.n-1; //除去L.data[0],n是待排元素个数
        //前后位置记录的增量是d,不是1
        //这里的L.data[0]只是暂存单元,不是哨兵;当j<=0时,插入位置已到
        for(d=n/2; d>=1; d=d/2){
            for(i=d+1; i<=n; i++){
                if(L.data[i] < L.data[i-d]){ //说明需要将L.data[i]插入到前面的有序增量子表中
                    L.data[0] = L.data[i];  //L.data[0]暂存该值
                    for(j=i-d; j>0&&L.data[0]<L.data[j]; j-=d){ //注意每次变化是d
                        L.data[j+d] = L.data[j];  //记录后移,查找插入位置
                    }
                    L.data[j+d] = L.data[0]; //插入
                }
            }
        }
    }
    
    int main(){
        SeqList L;
        int n;
        cin>>n; //元素个数
        CreateList(L, n);
        PrintList(L);
        //直接插入排序
        InsertSort(L);
        PrintList(L);
        //折半插入排序
        BinaryInsertSort(L);
        PrintList(L);
        //希尔排序
        ShellSort(L);
        PrintList(L);
        return 0;
    }
    

    运行结果:
    在这里插入图片描述

    说明:其实在执行完直接插入排序后顺序表中的元素已经是有序的了,下面的这般排序和希尔排序只是为了验证算法的正确性。

    更多相关内容
  • c++插入排序详解

    2021-01-01 11:40:52
    说一说插入排序 插入排序的基本操作就是将一个数据插入到已经排序好序的数据中,从而得到一个新的,个数加一的有序数据,算法适用与少量的数据的排序。时间复杂度O(n^2),是稳定的排序算法。 基本思想:每步将一个待...
  • 这是插入排序算法的matlab实现。 它接受输入 1xN 向量并按升序排序。
  • 插入排序之直接插入排序.cpp
  • 插入排序

    2021-01-20 03:30:30
    根据寻找插入位置的不同方式,可将插入排序分为直接插入排序和折半插入排序,还有一种对直接插入排序的优化方案希尔排序。 直接插入排序 直接插入排序的是,将一组待排序的元素第一个元素看做是有序的,然后从第二个...
  • 10种排序算法代码+综合比较代码(直接插入排序、希尔排序、冒泡排序、快速排序、简单选择排序、堆排序、归并排序、基数排序、折半插入排序、2路插入排序),其中不仅有各种排序算法的代码,还包含10种代码在关键字...
  • 插入排序2.希尔排序 1. 插入排序 步骤: 1.从第一个元素开始,该元素可以认为已经被排序 2.取下一个元素tem,从已排序的元素序列从后往前扫描 3.如果该元素大于tem,则将该元素移到下一位 4.重复步骤3,直到找到已...


    1. 插入排序

    步骤:

    1.从第一个元素开始,该元素可以认为已经被排序
    2.取下一个元素tem,从已排序的元素序列从后往前扫描
    3.如果该元素大于tem,则将该元素移到下一位
    4.重复步骤3,直到找到已排序元素中小于等于tem的元素
    5.tem插入到该元素的后面,如果已排序所有元素都大于tem,则将tem插入到下标为0的位置
    6.重复步骤2~5

    动图演示如下:在这里插入图片描述
    思路:
      在待排序的元素中,假设前n-1个元素已有序,现将第n个元素插入到前面已经排好的序列中,使得前n个元素有序。按照此法对所有元素进行插入,直到整个序列有序。
      但我们并不能确定待排元素中究竟哪一部分是有序的,所以我们一开始只能认为第一个元素是有序的,依次将其后面的元素插入到这个有序序列中来,直到整个序列有序为止。
    在这里插入图片描述
    代码如下:

    void InsertSort(int* arr, int n)
    {
    	for (int i = 0; i < n - 1; ++i)
    	{
    		//记录有序序列最后一个元素的下标
    		int end = i;
    		//待插入的元素
    		int tem = arr[end + 1];
    		//单趟排
    		while (end >= 0)
    		{
    			//比插入的数大就向后移
    			if (tem < arr[end])
    			{
    				arr[end + 1] = arr[end];
    				end--;
    			}
    			//比插入的数小,跳出循环
    			else
    			{
    				break;
    			}
    		}
    		//tem放到比插入的数小的数的后面
    		arr[end  + 1] = tem;
    		//代码执行到此位置有两种情况:
    		//1.待插入元素找到应插入位置(break跳出循环到此)
    		//2.待插入元素比当前有序序列中的所有元素都小(while循环结束后到此)
    	}
    }
    

    时间复杂度:最坏情况下为O(N*N),此时待排序列为逆序,或者说接近逆序
          最好情况下为O(N),此时待排序列为升序,或者说接近升序。
    空间复杂度:O(1)

    2.希尔排序

    步骤:
    1.先选定一个小于N的整数gap作为第一增量,然后将所有距离为gap的元素分在同一组,并对每一组的元素进行直接插入排序。然后再取一个比第一增量小的整数作为第二增量,重复上述操作…
    2.当增量的大小减到1时,就相当于整个序列被分到一组,进行一次直接插入排序,排序完成。
    动图如下:
    在这里插入图片描述
    思路:
    希尔排序,先将待排序列进行预排序,使待排序列接近有序,然后再对该序列进行一次插入排序,此时插入排序的时间复杂度为O(N),

    代码如下:

    //希尔排序
    void ShellSort(int* arr, int n)
    {
    	int gap = n;
    	while (gap>1)
    	{
    		//每次对gap折半操作
    		gap = gap / 2;
    		//单趟排序
    		for (int i = 0; i < n - gap; ++i)
    		{
    			int end = i;
    			int tem = arr[end + gap];
    			while (end >= 0)
    			{
    				if (tem < arr[end])
    				{
    					arr[end + gap] = arr[end];
    					end -= gap;
    				}
    				else
    				{
    					break;
    				}
    			}
    			arr[end + gap] = tem;
    		}
    	}
    }
    

    时间复杂度平均:O(N^1.3)
    空间复杂度:O(1)

    3.选择排序

    思路:
    每次从待排序列中选出一个最小值,然后放在序列的起始位置,直到全部待排数据排完即可。
    实际上,我们可以一趟选出两个值,一个最大值一个最小值,然后将其放在序列开头和末尾,这样可以使选择排序的效率快一倍。

    动图如下:
    在这里插入图片描述
    代码如下:

    //选择排序
    void swap(int* a, int* b)
    {
    	int tem = *a;
    	*a = *b;
    	*b = tem;
    }
    void SelectSort(int* arr, int n)
    {
    	//保存参与单趟排序的第一个数和最后一个数的下标
    	int begin = 0, end = n - 1;
    	while (begin < end)
    	{
    		//保存最大值的下标
    		int maxi = begin;
    		//保存最小值的下标
    		int mini = begin;
    		//找出最大值和最小值的下标
    		for (int i = begin; i <= end; ++i)
    		{
    			if (arr[i] < arr[mini])
    			{
    				mini = i;
    			}
    			if (arr[i] > arr[maxi])
    			{
    				maxi = i;
    			}
    		}
    		//最小值放在序列开头
    		swap(&arr[mini], &arr[begin]);
    		//防止最大的数在begin位置被换走
    		if (begin == maxi)
    		{
    			maxi = mini;
    		}
    		//最大值放在序列结尾
    		swap(&arr[maxi], &arr[end]);
    		++begin;
    		--end;
    	}
    }
    

    时间复杂度:最坏情况:O(N^2)
          最好情况:O(N^2)
    空间复杂度:O(1)

    4.冒泡排序

    思路:
    左边大于右边交换一趟排下来最大的在右边

    动图如下:
    在这里插入图片描述
    代码如下:

    //冒泡排序
    void BubbleSort(int* arr, int n)
    {
    	int end = n;
    	while (end)
    	{
    		int flag = 0;
    		for (int i = 1; i < end; ++i)
    		{
    			if (arr[i - 1] > arr[i])
    			{
    				int tem = arr[i];
    				arr[i] = arr[i - 1];
    				arr[i - 1] = tem;
    				flag = 1;
    			}
    		}
    		if (flag == 0)
    		{
    			break;
    		}
    		--end;
    	}
    }
    

    时间复杂度:最坏情况:O(N^2)
          最好情况:O(N)
    空间复杂度:O(1)

    5.堆排序

    堆排可看之间这篇博文----->[堆排]

    6.快速排序

    5.1 hoare版本(左右指针法)

    思路:
    1、选出一个key,一般是最左边或是最右边的。
    2、定义一个begin和一个end,begin从左向右走,end从右向左走。(需要注意的是:若选择最左边的数据作为key,则需要end先走;若选择最右边的数据作为key,则需要bengin先走)。
    3、在走的过程中,若end遇到小于key的数,则停下,begin开始走,直到begin遇到一个大于key的数时,将begin和right的内容交换,end再次开始走,如此进行下去,直到begin和end最终相遇,此时将相遇点的内容与key交换即可。(选取最左边的值作为key)
    4.此时key的左边都是小于key的数,key的右边都是大于key的数
    5.将key的左序列和右序列再次进行这种单趟排序,如此反复操作下去,直到左右序列只有一个数据,或是左右序列不存在时,便停止操作,此时此部分已有序

    单趟动图如下:
    在这里插入图片描述
    代码如下:

    //快速排序   hoare版本(左右指针法)
    void QuickSort(int* arr, int begin, int end)
    {
    	//只有一个数或区间不存在
    	if (begin >= end)
    		return;
    	int left = begin;
    	int right = end;
    	//选左边为key
    	int keyi = begin;
    	while (begin < end)
    	{
    		//右边选小   等号防止和key值相等    防止顺序begin和end越界
    		while (arr[end] >= arr[keyi] && begin < end)
    		{
    			--end;
    		}
    		//左边选大
    		while (arr[begin] <= arr[keyi] && begin < end)
    		{
    			++begin;
    		}
    		//小的换到右边,大的换到左边
    		swap(&arr[begin], &arr[end]);
    	}
    	swap(&arr[keyi], &arr[end]);
    	keyi = end;
    	//[left,keyi-1]keyi[keyi+1,right]
    	QuickSort(arr, left, keyi - 1);
    	QuickSort(arr,keyi + 1,right);
    }
    

    时间复杂度:
    在这里插入图片描述
    快速排序的过程类似于二叉树其高度为logN,每层约有N个数,如下图所示:在这里插入图片描述

    5.2 挖坑法

    5.2.1 递归

    思路:
    挖坑法思路与hoare版本(左右指针法)思路类似
    1.选出一个数据(一般是最左边或是最右边的)存放在key变量中,在该数据位置形成一个坑
    2、还是定义一个L和一个R,L从左向右走,R从右向左走。(若在最左边挖坑,则需要R先走;若在最右边挖坑,则需要L先走)

    后面的思路与hoare版本(左右指针法)思路类似在此处就不说了

    单趟动图如下:
    在这里插入图片描述
    代码如下:

    //快速排序法  挖坑法
    void QuickSort1(int* arr, int begin, int end)
    {
    	if (begin >= end)
    		return;
    	int left = begin,right = end;
    	int key = arr[begin];
    	while (begin < end)
    	{
    		//找小
    		while (arr[end] >= key && begin < end)
    		{
    			--end;
    		}
    		//小的放到左边的坑里
    		arr[begin] = arr[end];
    		//找大
    		while (arr[begin] <= key && begin < end)
    		{
    			++begin;
    		}
    		//大的放到右边的坑里
    		arr[end] = arr[begin];
    	}
    	arr[begin] = key;
    	int keyi = begin;
    	//[left,keyi-1]keyi[keyi+1,right]
    	QuickSort1(arr, left, keyi - 1);
    	QuickSort1(arr, keyi + 1, right);
    }
    

    5.2.2 非递归

    //单趟排
    int PartSort(int* arr, int begin, int end)
    {
    	int key = arr[begin];
    	while (begin < end)
    	{
    		while (key <= arr[end] && begin < end)
    		{
    			--end;
    		}
    		arr[begin] = arr[end];
    		while (key >= arr[begin] && begin < end)
    		{
    			++begin;
    		}
    		arr[end] = arr[begin];
    	}
    	arr[begin] = key;
    	int meeti = begin;
    	return meeti;
    }
    
    void QuickSortNoR(int* arr, int begin, int end)
    {
    	stack<int> st;
    	//先入右边
    	st.push(end);
    	//再入左边
    	st.push(begin);
    	while (!st.empty())
    	{
    		//左区间
    		int left = st.top();
    		st.pop();
    		//右区间
    		int right = st.top();
    		st.pop();
    		//中间数
    		int mid = PartSort(arr, left, right);
    		//当左区间>=mid-1则证明左区间已经排好序了
    		if (left < mid - 1)
    		{
    			st.push(mid - 1);
    			st.push(left);
    		}
    		//当mid+1>=右区间则证明右区间已经排好序
    		if (right > mid + 1)
    		{
    			st.push(right);
    			st.push(mid + 1);
    		}
    	}
    }
    

    5.3 前后指针法

    思路:
    1、选出一个key,一般是最左边或是最右边的。
    2、起始时,prev指针指向序列开头,cur指针指向prev+1。
    3、若cur指向的内容小于key,则prev先向后移动一位,然后交换prev和cur指针指向的内容,然后cur指针++;若cur指向的内容大于key,则cur指针直接++。如此进行下去,直到cur到达end位置,此时将key和++prev指针指向的内容交换即可。

    经过一次单趟排序,最终也能使得key左边的数据全部都小于key,key右边的数据全部都大于key。

    然后也还是将key的左序列和右序列再次进行这种单趟排序,如此反复操作下去,直到左右序列只有一个数据,或是左右序列不存在时,便停止操作

    //快速排序法  前后指针版本
    void QuickSort2(int* arr, int begin, int end)
    {
    	if (begin >= end)
    		return;
    	int cur = begin, prev = begin - 1;
    	int keyi = end;
    	while (cur != keyi)
    	{
    		if (arr[cur] < arr[keyi] && ++prev != cur)
    		{
    			swap(&arr[cur], &arr[prev]);
    		}
    		++cur;
    	}
    	swap(&arr[++prev],&arr[keyi]);
    	keyi = prev;
    	//[begin,keyi -1]keyi[keyi+1,end]
    	QuickSort2(arr, begin, keyi - 1);
    	QuickSort2(arr, keyi + 1, end);
    
    }
    
    展开全文
  • 插入排序 插入排序的基本思想:每次将一个待排序序列按其关键字大小插入到前面已经排好序的子序列中,知道全部记录插入完成。主要有直接插入排序、折半插入排序和希尔排序。 直接插入排序(Straight Insertion Sort...
  • 六种内部排序算法比较:直接插入排序、希尔排序、冒泡排序、快速排序、选择排序、堆排序。包含实验报告和源代码设计。
  • C语言代码 直接插入排序算法fun1,冒泡法排序排列算法fun2,直接选择法排序算法fun3。
  • 易语言源码分组插入排序.rar 易语言源码分组插入排序.rar 易语言源码分组插入排序.rar 易语言源码分组插入排序.rar 易语言源码分组插入排序.rar 易语言源码分组插入排序.rar
  • 易语言源码二分插入排序.rar 易语言源码二分插入排序.rar 易语言源码二分插入排序.rar 易语言源码二分插入排序.rar 易语言源码二分插入排序.rar 易语言源码二分插入排序.rar
  • c程序,选择排序和插入排序。VC++工程。 c程序,选择排序和插入排序。VC++工程。
  • 【数据结构初阶】第一篇——八大经典排序算法之插入排序总结(图解+动图演示+代码实现+八大排序比较)

    前言

    本章将介绍常见八大排序中的 插入排序

    可能你会好奇,为什么只介绍插入排序呢?

    因为我学完了所有排序以后,也看了市面上很多写排序的文章,都是一篇文章全部把所有排序都写完了的!

    我觉得一篇文章把所有排序全部写完的话,会存在2个问题:

    1、一篇文章写完所有排序,会导致某个知识点不全面,换个话来说,就是越往后写,容易产生疲劳;
     
    2、读者的直观感受可能不是那么好,毕竟更多的是要让大家能看懂!其次自己也能看懂!

    所以,先分章节,慢慢来,把多个知识点深度剖析!

    Let’s get it!


    在这里插入图片描述



    1. 排序是什么

    🍑 排序的概念

    排序: 所谓排序,就是使一串记录,按照其中的某个或某些关键字的大小,递增或递减的排列起来的操作。

     

    稳定性: 假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序保持不变,即在原序列中,r[i]=r[j],且r[i]r[j]之前,而在排序后的序列中,r[i]仍在r[j]之前,则称这种排序算法是稳定的;否则称为不稳定的。

     

    内部排序: 数据元素全部放在内存中的排序。

     

    外部排序: 数据元素太多不能同时放在内存中,根据排序过程的要求不能在内外存之间移动数据的排序。

    🍑 排序的运用

    这里给大家举几个生活中,常见排序的栗子👇:

    购物平台里面按某个商品的维度排序

    image-20211212213019712

    全国高校排名

    其实在我们平时日常生活中还有很多都会用到排序的地方;

    由此可见,排序与我们的生活息息相关😄

    2. 插入排序分类

    插入排序可以分为:直接插入排序希尔排序

    image-20211212213649416

    3. 直接插入排序

    🍑 基本思想

    🎃直接插入排序是一种简单的插入排序法;

    插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴,但它的原理应该是最容易理解的了,因为只要打过扑克牌的人都应该能够秒懂。

     

    实际中我们玩扑克牌时,就用了插入排序的思想,不信你看👇

    image-20211212213858969

    ❗❓那么怎么去理解它呢?很简单

    直接插入排序是指:在待排序的元素中,假设前面n-1(其中n>=2)个数已经是排好顺序的,现将第n个数插到前面已经排好的序列中,然后找到合适自己的位置,使得插入第n个数的这个序列也是排好顺序的

     

    按照此法对所有元素进行插入,直到整个序列排为有序的过程,称为插入排序 。

     

    但我们并不能确定待排元素中究竟哪一部分是有序的,所以我们一开始只能认为第一个元素是有序的依次将其后面的元素插入到这个有序序列中来直到整个序列有序为止

    img

    🍑 动图演示

    🍅我们先来看个动态图演示:

    img

    1、从图中观察的现象是如果后一个数不比前一个数小,那就不需要插入,不插入的动作就是break出循环

     

    2、如果前面的数都比pos(拿出的数)值大,那么就将前n个数都往后挪动,直到比pos值小或者相等就停止,可以用循环控制,这里防止越界需要再加判断

    📃 代码实现

    void InsertSort(int* a, int n)
    {
    	int i = 0;
    
    	//注意控制好终止条件,这里的end的位置是在倒数第二个位置,所以要-1
    	for (i = 0; i < n - 1; i++)
    	{
    		int end = i;//记录有序序列的最后一个元素的下标
    
    		int tmp = a[end + 1];//待插入的元素
    		while (end >= 0)
    		{
    			if (tmp < a[end])//还需继续比较
    			{
    				a[end + 1] = a[end];
    				end--;
    			}
    			else//找到应插入的位置
    			{
    				break;
    			}
    		}
    		a[end + 1] = tmp;
    		//代码执行到此位置有两种情况:
    		//1.待插入元素找到应插入位置(break跳出循环到此)。
    		//2.待插入元素比当前有序序列中的所有元素都小(while循环结束后到此)。
    	}
    }
    

    🍑 概括总结

    复杂度分析:

    元素集合越接近有序,直接插入排序算法的时间效率越高,反之越低

     

    时间复杂度: O ( n 2 ) O(n^2) O(n2)

     

    空间复杂度: O ( 1 ) O(1) O(1)

     

    稳定性的分析:直接插入排序在遇到相同的数时,可以就放在这个数的后面,就可以保持稳定性了,所以说这个排序是稳定的。

    特性总结:

    插入排序是一种最简单直观的排序算法;

     

    它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。

     

    也就是说:把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中,直到所有的记录插入完为止,得到一个新的有序序列 。

    4. 希尔排序

    🍑 基本思想

    希尔排序,也称缩小增量法,是插入排序的一种更高效的改进版本;

     

    但希尔排序是非稳定排序算法

    ❗❓那么它的思路是什么呢?

    每次从一个有序序列开始,将待排元素与有序序列中的元素从后往前逐个比较,

     

    若有序序列中的元素大于待排元素,则将较大的元素往后覆盖;

     

    否则,将待排元素插入其前面,并结束此轮比较。

    🍑 动图演示

    img

    🤔实现原理

    1、先选定一个小于N的整数gap作为第一增量,然后将所有距离为gap的元素分在同一组,并对每一组的元素进行直接插入排序。然后再取一个比第一增量小的整数作为第二增量,重复上述操作…

     

    2、当增量的大小减到1时,就相当于整个序列被分到一组,进行一次直接插入排序,排序完成。

     

    为什么要让gap由大到小呢?

     

    答:gap越大,数据挪动得越快;gap越小,数据挪动得越慢。前期让gap较大,可以让数据更快得移动到自己对应的位置附近,减少挪动次数。

     

    注:一般情况下,取序列的一半作为增量,然后依次减半,直到增量为1(也可自己设置)。

    🍑 举例说明

    现在我们用希尔排序对该序列进行排序。

    img

    我们用序列长度的一半作为第一次排序时gap的值,此时相隔距离为5的元素被分为一组(共分了5组,每组有2个元素),然后分别对每一组进行直接插入排序。

    img

    gap的值折半,此时相隔距离为2的元素被分为一组(共分了2组,每组有5个元素),然后再分别对每一组进行直接插入排序。

    img

    gap的值再次减半,此时gap减为1,即整个序列被分为一组,进行一次直接插入排序。

    img

    上述示例中,前两趟就是希尔排序的预排序,最后一趟就是希尔排序的直接插入排序。

    📃 代码实现

    //希尔排序
    void ShellSort(int* a, int n)
    {
    	int gap = n;
    	while (gap > 1) //别加等号,不然就是死循环
    	{
            //控制gap值的变化,让数组接近有序,gap == 1就可以直接插入排序
    		gap = gap / 2;//gap折半
    		int i = 0;
    		//进行一趟排序
    		for (i = 0; i < n - gap; i++)
    		{
    			int end = i;
    			int tmp = a[end + gap];
    			while (end >= 0)
    			{
                    //当前的end的值比tmp大就要往end+gap位置挪
    				//所以要提前保存end+gap的值
    				if (tmp < a[end])
    				{
    					a[end + gap] = a[end];
    					end -= gap;
    				}
    				else
    				{
    					break;
    				}
    			}
    			a[end + gap] = tmp;
    		}
    	}
    }
    

    🍑 概括总结

    复杂度分析:

    时间复杂度: O ( N l o g N ) O(NlogN) O(NlogN)
     
    空间复杂度: O ( 1 ) O(1) O(1)
     
    平均时间复杂度: O ( N 1.3 ) O(N^{1.3}) O(N1.3)
     
    稳定性的分析:可以这样想,相同的数被分到了不同的组,就不能保证原有的顺序了,所以说这个排序是不稳定的

    特性总结:

    希尔排序是对直接插入排序的优化。

     

    gap > 1时都是预排序,目的是让数组更接近于有序。当gap == 1时,数组已经接近有序的了,这样就 会很快。这样整体而言,可以达到优化的效果。我们实现后可以进行性能测试的对比。

     

    希尔排序的时间复杂度不好计算,因为gap的取值方法很多,导致很难去计算,因此在好些树中给出的 希尔排序的时间复杂度都不固定:

     

    《数据结构(C语言版)》 中,是这样说的:

    image-20211214101932338

    《数据结构-用面相对象方法与C++描述》 中,是这样说的:

    image-20211214102013752

    因为我们的gap是按照Knuth提出的方式取值的,而且Knuth进行了大量的试验统计,我们暂时就按照: O ( n 1.25 ) O(n^{1.25}) O(n1.25) O ( 1.6 ∗ n 1.25 ) O(1.6*n^{1.25}) O(1.6n1.25) 来计算

     

    稳定性:不稳定

    5. 总结

    以上就是关于 插入排序 的全部内容,下一篇就进入到我们的 选择排序

    🌟你知道的越多,你不知道越多,我们下期见!

    展开全文
  • C++ 插入排序——直接插入排序 详解

    千次阅读 2022-03-12 20:12:53
    插入排序也是最简单的一类排序方法,我今天介绍的也是插入排序里最直观且浅显易懂的直接插入排序。对这个很简单的排序,记得当时也是花了近两个晚上才搞懂它的原理的,接下来就来介绍一下我的思路: 我曾经也在网上...

    插入排序也是最简单的一类排序方法,我今天介绍的也是插入排序里最直观且浅显易懂的直接插入排序。对这个很简单的排序,记得当时也是花了近两个晚上才搞懂它的原理的,接下来就来介绍一下我的思路:

    我曾经也在网上搜索了很多别人写的博客也百度看了别人的想法,但怎么说呢,大概是一百个人就会有一百种想法,也可能是我没有看到正中我心意的那一篇博客,导致看了很多别人写的代码以及图片示例都没有解决我心里的疑问和不解。现在我就来写一下我对这个排序的理解,希望曾经跟我一样有这样疑问的朋友,能在我的博客里找到答案。

    直接上例子,通过例子来讲解我的思路:

    首先来定义一个整型一维数组a[6] = {2, 6, 5, 3, 4, 1},

    2   6   5   3   4   1

    我们令数组下标 i 从0开始,假定第一个数即a[0] = 2 是有序的,然后从第二个数i = 1 时从后往前开始枚举, 枚举的过程就是找一个合适的位置把当前枚举的数存放进去即插进去。这时候要定义另一个整型变量 j 来辅助判断, 每一次循环 j = i

    i = 1 时: temp = 6   i<= 0 有序

    用整型变量 temp 来临时存放每一次需要排序的元素, 每一次判断的条件就是在一定条件下temp 是否小于前一个元素(默认从小到大排序),易知这一次排序6  > 2, 所以不需要进行交换,接着我们来进行下一趟排序;

    i = 2: temp = 5        i  <= 1 有序

     易发现此时当前项即temp  = 5 比 a[j - 1] 项小, 所以此时令 a[j] = a[j - 1], 即让原来的 j - 1项往后移一位,然后 j-- 让 j 继续枚举前面的数,原来的 i= 2 的原始值已经存放在了temp 里, 即

     J 继续向前枚举的时候,我们发现,此时的temp 并不满足小于a[j-1] ,所以将 temp 插入存放在 a[j]里, 这一次的排序已经排完,即

    i = 3:  temp = 3    i <= 2 有序

     此时temp 存放的 数值 3 小于 a[j-1] , 所以将a[j-1]赋值给a[j] ,然后 j 继续向前枚举。

     此时 temp 存放的数值3 仍旧小于a[j-1]项, 所以继续将a[j-1] 赋值给a[j], 即将a[j-1]向后移一项,然后j 继续向前枚举:

     此时temp 存放的数值3 比a[j-1]大, 所以此时就将temp 赋值给a[j]来完成该次排序,即:

     i = 4: temp = 4     i <= 3 有序

     此时当前项 temp 存放的 数值4 比前一项a[j-1]小,所以令a[j-1]的值赋值给a[j] 来使a[j-1] 的值后移一位,令j 继续向前枚举,即

     此时 temp 存放的数值4 仍旧比a[j-1] 要小,继续令a[j-1]的值赋值给a[j] 来使a[j-1] 的值后移一位,令j 继续向前枚举,即

     到此,temp 存放的数值 4 比a[j-1] 大,不再需要继续向前枚举,直接令a[j] = temp 来完成当前项的排序,即

     i = 5: temp = 1    i <= 4 有序

     此时 temp 存放的数值1 小于a[j-1]项,所以令a[j-1]的值赋值给a[j] 来使a[j-1] 的值后移一位,令j 继续向前枚举,即

     此时 temp 存放的数值1 依然小于a[j-1]项,所以令a[j-1]的值赋值给a[j] 来使a[j-1] 的值后移一位,令j 继续向前枚举,即

     此时 temp 存放的数值1 依然小于a[j-1]项,所以令a[j-1]的值赋值给a[j] 来使a[j-1] 的值后移一位,令j 继续向前枚举,即

     此时 temp 存放的数值1 依然小于a[j-1]项,所以令a[j-1]的值赋值给a[j] 来使a[j-1] 的值后移一位,令j 继续向前枚举,即

     此时 temp 存放的数值1 依然小于a[j-1]项,所以令a[j-1]的值赋值给a[j] 来使a[j-1] 的值后移一位,令j 继续向前枚举,即

     至此,j 已经到达了数组最前,且temp 已经无法满足小于 a[j-1]了,所以此时跳出while循环,顺势将temp 的数值赋值给a[j],至此,所有的数都已经完成排列,最后i <= 5有序, 即

     最后,上代码:

    #include<iostream>
    using namespace std;
    int main() {
    	int a[6] = { 2, 6, 5, 3, 4, 1};
    	int temp, i, j;
    	int n = 6;
    	for (i = 1; i < 6; i++) {  // 数组的下标是从0开始的
    		// 这里从第二个数开始枚举  即假定第一个数是有序的
    		temp = a[i]; j = i;     // 这里temp 临时储存每一次需要排序的数
    		while (j >= 1 && temp < a[j - 1]) {
    			a[j] = a[j - 1];
    			j--;
    		}
    		a[j] = temp;
    	}
    	for (i = 0; i < 6; i++) {
    		cout << a[i] << " ";
    	}
    	cout << endl;
    	return 0;
    }

    如有不对之处,欢迎批评指正!

    展开全文
  • C++实现插入排序

    2017-11-02 22:26:04
    插入排序插入排序插入排序插入排序插入排序插入排序插入排序
  • 数据结构---直接插入排序/快速排序/选择排序/冒泡排序(详细实现算法和性能比较)
  • 插入类:直接插入排序、折半插入排序、希尔排序 交换类:冒泡排序、快速排序 选择类:简单选择排序、堆排序 归并类:二路归并排序 基数类:多关键字排序 九种算法的时间复杂度、空间复杂度和稳定性小结如下: 本文...
  • 选择排序、冒泡排序、插入排序、希尔排序 归并排序、快速排序、堆排序 非比较的排序算法: 计数排序、基数排序、桶排序(一般不了解,是因为这些算法的应用很有限的。) 选择排序 就是一个一个的选出来,先选出最小...
  • 排序——插入排序 插入排序的基本思想是每次将一个待排序的记录,按其关键字大小插入到前面已经排好序的子文件中的适当位置,直到全部记录插入完成为止。常见的插入排序插入排序(Insertion Sort),希尔排序...
  • 插入排序过程详解

    千次阅读 2021-09-18 16:06:13
    插入排序过程详解 1,引入 2,外层选元素,内层找位置 看完此部分后再读一遍这个标题。 插入 3,实现 3,1,C++ 3,2,Python 4,想法 5,参考
  • 七种排序算法(包括直接插入排序,折半插入排序,希尔排序,冒泡排序,快速排序,简单选择排序,归并排序) 还有两道题 1./*设计并实现一个有效的对n个整数重排的算法,使得所有负数位于非负数之前,给出算法的性能...
  • 插入排序算法

    千次阅读 2021-05-10 22:33:58
      插入排序(Insertion sort)一般也被称为直接插入排序。对于少量元素的排序,它是一个有效的算法 。插入排序是一种最简单的排序方法,它的基本思想是将一个记录插入到已经排好序的有序表中,从而得到一个新的、...
  • (1)掌握线性表的存储方式,并在此基础上实现典型的排序算法 (2)理解并掌握内部排序中几种常用算法的性能和适用场合 (3)理解并比较各种排序算法的时间复杂度和空间复杂度
  • 插入排序:(Insertion Sort) 插入排序的基本思想是:每次将一个待排序的记录,按其关键字大小插入到前面已经排好序的子表中的适当位置,直到全部记录插入完成为止。 共有5种插入排序方法: (1) 直接插入排序; (2) 折半...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 773,796
精华内容 309,518
关键字:

插入排序