排序——插入类排序

约定不等于承诺〃 2021-11-11 04:24 243阅读 0赞

> **插入类排序，一般是在一个有序的序列中，插入一个新的元素，要点在于如何找到这个插入的位置。**
> 
> **插入类排序包括：直接插入排序，折半插入排序，希尔排序**

## 直接插入排序 ##

> **算法思想：每趟将一个待排序的关键字按照其值的大小插入到已经排好的部分有序序列的适当位置上，直到所有关键字都被插入到有序序列中为止。**
> 
> **时间复杂度分析：**
> 
>  **空间复杂度：O(1)**
> 
>  *  **最坏情况下，****基本操作选取最内层循环中arr\[j+1\] = arr\[j\]，基本操作的执行次数为n\*(n-1)/2，时间复杂度为O(n^2)；**
>  *    **最好情况下，整个序列已经有序，双层循环变成了单层循环，时间复杂度为O(n)；**
>  *  **平均时间复杂度为O(n^2)；**

**代码：**

void StrightInsert_sort(int arr[],int n)        //直接插入排序
    {
        int i,j,temp;
        for(i=0; i<n; i++)
        {
            temp = arr[i];
            j = i-1;
            while(j>=0&&temp<arr[j])                //找到插入位置，并使插入位置后的元素后移一位
            {
                arr[j+1] = arr[j];
                --j;
            }
            arr[j+1] = temp;
        }
    }

## 折半插入排序 ##

> **算法思想：和直接插入排序相似，不同的是查找插入位置的方法不同，折半插入是使用二分查找的方法来查找。**
> 
> **时间复杂度分析：**
> 
> **使用场所：关键字数较多时**
> 
>  *  **折半插入排序在关键字移动次数方面和直接插入排序一致，所以其时间复杂度和直接插入排序一样**
>  *  **最好：O(nlog2n)**
>  *  **最坏：O(n^2)**
>  *  **平均：O(n^2)**

**代码：**

/*比较arr[i]与arr[mid]的大小，若arr[i]>a[mid]，说明a[i]的位置应该在mid~right之间，将区间[left,right]缩短为[mid+1,right]，
    令指针left = mid+1；若arr[i]<=arr[mid]，说明arr[i]的位置应该在left~mid之间，将区间压缩为[left,mid-1]，令指针right=mid-1。
    每次折半之后，arr[i]的位置应该在[left,right]之间。
    如此循环，left与right渐渐靠近，直到left>right跳出循环，arr[i]的位置找到，left即为arr[i]应该放置的位置。
    找到arr[i]的位置之后进行插入，先将arr[left]~arr[i-1]这些元素向后平移一个元素的位置，然后将arr[i]放到left位置*/
    void BinaryInsert_sort(int arr[],int n)         //折半插入排序
    {
        int i,j,temp,left,right,mid;
        for(i=1; i<n; i++)                          //折半插入要求前面是已经有序，所以从第二位数开始，依次插入
        {
            temp = arr[i];                          //将待插入数据赋值给temp
            left = 0;
            right = i-1;
            while(left<=right)                      //每一次循环都从第一个依次比较，当退出循环时,arr[i]的位置找到，left即是应该放置的位置
            {
                mid = (left+right)/2;
                if(arr[mid]<temp)                   //说明插入的数据在mid右边，改变此时left的值
                    left = mid+1;
                else                                //插入数据在mid左边，改变此时right的值
                    right = mid-1;
            }
            for(j=i-1; j>=left; j--)                //将left之后的元素后移一位
            {
                arr[j+1] = arr[j];
            }
            arr[left] = temp;                       //放入插入元素
        }
    }

## 希尔排序 ##

> **算法思想：选取增量，将待排序序列以某种规则（增量的选取）分成几个子序列，分别对这几个子序列进行直接插入排序。**
> 
> **时间复杂度分析：**
> 
> **希尔排序是不稳定的**
> 
>  *  **希尔排序的时间复杂度和增量选取有关，常见规则：每次将增量/2并向下取整，此时时间复杂度为O(n^2)**；**或增量序列为2^(t-k+1)  -1，t为排序趟数，时间复杂度为O(n^3/2)**
>  *  **增量序列的最后一个值一定取1**
>  *  **增量序列中的值应尽量没有除1之外的公因子**

**代码：**

void Shell_sort(int arr[],int n)         //希尔排序（缩小增量排序）
    {
        int i,j,temp,step;
        for(step=n/2; step>0; step/=2)       //定义每次比较的增量，增量每次循环/2
        {
            for(i=step; i<n; i++)           
            {
                temp = arr[i];              //保存每次遍历的元素
                for(j=i-step;(j>=0&&arr[j]>temp);j-=step)   //将遍历元素（下标i）与前i-=step元素比较
                    arr[j+step] = arr[j];
                arr[j+step] = temp;                         //此时j+step即为当前增量子序列最小元素的位置，插入即可
            }
        }
    }

**完整代码：**

#include <stdio.h>
    #include <stdlib.h>
    void StrightInsert_sort(int arr[],int n)        //直接插入排序
    {
        int i,j,temp;
        for(i=0; i<n; i++)
        {
            temp = arr[i];
            j = i-1;
            while(j>=0&&temp<arr[j])                //找到插入位置，并使插入位置后的元素后移一位
            {
                arr[j+1] = arr[j];
                --j;
            }
            arr[j+1] = temp;
        }
    }
    /*比较arr[i]与arr[mid]的大小，若arr[i]>a[mid]，说明a[i]的位置应该在mid~right之间，将区间[left,right]缩短为[mid+1,right]，
    令指针left = mid+1；若arr[i]<=arr[mid]，说明arr[i]的位置应该在left~mid之间，将区间压缩为[left,mid-1]，令指针right=mid-1。
    每次折半之后，arr[i]的位置应该在[left,right]之间。
    如此循环，left与right渐渐靠近，直到left>right跳出循环，arr[i]的位置找到，left即为arr[i]应该放置的位置。
    找到arr[i]的位置之后进行插入，先将arr[left]~arr[i-1]这些元素向后平移一个元素的位置，然后将arr[i]放到left位置*/
    void BinaryInsert_sort(int arr[],int n)         //折半插入排序
    {
        int i,j,temp,left,right,mid;
        for(i=1; i<n; i++)                          //折半插入要求前面是已经有序，所以从第二位数开始，依次插入
        {
            temp = arr[i];                          //将待插入数据赋值给temp
            left = 0;
            right = i-1;
            while(left<=right)                      //每一次循环都从第一个依次比较，当退出循环时,arr[i]的位置找到，left即是应该放置的位置
            {
                mid = (left+right)/2;
                if(arr[mid]<temp)                   //说明插入的数据在mid右边，改变此时left的值
                    left = mid+1;
                else                                //插入数据在mid左边，改变此时right的值
                    right = mid-1;
            }
            for(j=i-1; j>=left; j--)                //将left之后的元素后移一位
            {
                arr[j+1] = arr[j];
            }
            arr[left] = temp;                       //放入插入元素
        }
    }
    void Shell_sort(int arr[],int n)         //希尔排序（缩小增量排序）
    {
        int i,j,temp,step;
        for(step=n/2; step>0; step/=2)       //定义每次比较的增量，增量每次循环/2
        {
            for(i=step; i<n; i++)           
            {
                temp = arr[i];              //保存每次遍历的元素
                for(j=i-step;(j>=0&&arr[j]>temp);j-=step)   //将遍历元素（下标i）与前i-=step元素比较
                    arr[j+step] = arr[j];
                arr[j+step] = temp;                         //此时j+step即为当前增量子序列最小元素的位置，插入即可
            }
        }
    }
    int main()
    {
        int i;
        int arr[] = {56,12,78,34,10,90,23,67,56,43};
    //    StrightInsert_sort(arr,10);
    //    BinaryInsert_sort(arr,10);
        Shell_sort(arr,10);
        for(i=0; i<10; i++)
        {
            printf("%d\t",arr[i]);
        }
    }

![20190804120102755.png][]

[20190804120102755.png]: /images/20211109/c936983be3d349ea9bedb10dab2d5d77.png