数据结构与算法：插入排序

有关排序的一些概念

时间复杂度：一个算法执行所耗费的时间。
空间复杂度：运行完一个程序所需内存的大小。
原地排序：空间复杂度为 O(1)，不需要申请额外的空间。
内部排序：待排序的元素全部存放在内存中。
外部排序：待排序元素很多，需要从外存中读取元素。
稳定性：排序前后两个相同元素的相对位置不变。

插入排序

直接插入排序：将数组分为待排区和有序去，先用顺序查找，取出待排区第一个数字，从后向前比较找到在有序区的插入位置并将元素插入到该位置，一直重复操作直到清空待排区。

代码实现：

void InsertSort(int *arr,int N)
{
    for(int i=1;i<N;i++){
        int k=arr[i];
        int j;
        for(j=i;j>0;j--){
            if(arr[j-1]>k){
                arr[j]=arr[j-1];
            }else{
                break;
            }
        }
        arr[j]=k;
    }
}

改良：二路插入排序：改为循环数组，左右同时比较，左边小，左边前移，右边小，右边前移。

希尔排序

优化后的插入排序

取一个增量，将待排数组分为若干个；选择下标中位数为增量，a[i+nd]为一组，分为d组
第一组：1,1+d,1+2d……1+nd
第二组：2,2+d,2+2d……2+nd
第三组：3,3+d,3+2d……3+nd
依次类推将数组分组。

分完组后，对每一组进行插入排序。
缩小增量d=d/2，重复分组排序操作，直到d=1，由此可知直接插入排序为d=1的希尔排序。

代码实现：

void ShellSort(int arr[],int n)
{
    for(int d=n/2;d>=1;d/=2){
        for(int i=d;i<n;i++){
            int t=arr[i];
            int j;
            for(j=i;j>=d;j-=d){
                if(t<arr[j-d]){
                    arr[j]=arr[j-d];
                }else{
                    break;
                }
            }
            arr[j]=t;
        }
    }

    for(int i=0;i<n;i++){
        cout << arr[i] << ' ';
    }
}

• 本文作者： KongXinQing
• 本文链接： https://13114987559.github.io/2023/09/20/note/数据结构与算法-插入排序/
• 版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！