【数据结构】内部排序之插入排序（直接插入排序，折半插入排序，希尔排序）直接插入排序折半插入希尔排序

78 阅读 0 评论 52 点赞

我是靠谱客的博主调皮铃铛，这篇文章主要介绍【数据结构】内部排序之插入排序（直接插入排序，折半插入排序，希尔排序）直接插入排序折半插入希尔排序，现在分享给大家，希望可以做个参考。

插入排序的核心便是一个有序表，不断将新的记录插入到有序表合适的位置，从而使得有序表记录数加一。

直接插入排序

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void InsertSort(int* L)
{
    int temp;//设置一个临时变量
    for (int i = 0; i < num - 1; i++)//前i个数已经有序
    {
        if (L[i + 1] < L[i])//若i+1个数小于第i个数,则开始找合适的位置插入。若大于等于，则第i+1个位置就是合适的位置
        {
            temp = L[i + 1];//将需要插入的数存储进临时变量
            int j;
            for (j = i; L[j] >= temp && j>=0; j--)L[j + 1] = L[j];//找到第一个小于待插入数的数，大于待插入数的数后移，插入在它后面
            L[j + 1] = temp;
        }
    }
}

时间复杂度：首先下标为1到n-1的数要和它们前面的数作比较，假如小于则要继续向前作比较找到合适的插入位置。则最理想的情况下，数列为正序，只需比较n-1次。最坏的情况则是倒序，每个数在和前面的数做比较后，还要和前面所有的数作比较后再后移，从1到n-1，分别需要比较2,3,...,n次，根据等差列求和得出需要比较 $\text{[math]}$ 次。则平均时间复杂度为O(n²)。

折半插入

为了减少比较的次数，则用折半的思想去寻找插入位置。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void BInsertSort(int* L)
{
    int temp;
    for (int i = 0; i < num - 1; i++)
    {
        if (L[i + 1] < L[i])
        {
            temp = L[i + 1];
            int low = 0, high = i;
            int mid;
            while (low<=high)
            {
                mid = (low + high) / 2;
                if (temp < L[mid])high = mid - 1;//若待插入值小于中间值，则插入位置在上半部分
                else low = mid + 1;//若待插入值大于等于中间值，则插入位置在下半部分
            }
            for (int j = i; j >= high + 1; j--)L[j + 1] = L[j];
            L[high + 1] = temp;
        }
    }
}

虽然减少了比较的次数，但是移动次数还是不变，时间复杂度任然为O(n²)。

希尔排序

希尔排序也称为缩小增量排序，它的不同在于当待排序列很长时，它通过先将序列变得基本有序，然后再进行插入排序，从而减少时间复杂度。如何将序列变得基本有序，希尔排序选择将待排序列分割成若干子序列再进行直接插入排序，若干子序列合起来就是基本有序。再对整个序列进行插入排序，从而提高效率。怎么将待排序列进行分割，希尔排序引入增量数组这个辅助数组，增量数组中的元素由大变小，最后一定为1，增量表示下标之差。比如，首先将记录数为10的待排序列分割成5个子序列，增量为5，则这5个子序列为{R1,R6},{R2,R7},{R3,R8},{R4,R9},{R5,R10}，分别进行插入排序后，增量缩小，对增量为3的子序列进行插入排序，有{R1,R4,R7,R10},{R2,R5,R8},{R3,R6,R9}。增量最后缩小为1，即对整个序列再进行插入排序。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void ShellInsert(int* L,int dlta)
{
    for(int i = dlta; i < num; i++)\第dlta+1个记录之前有dlta个有序的子序列，每个子序列都只有一个记录。之后的每个记录都会根据增量在自己的子序列内进行插入排序，写法和普通的插入排序一样
    {
        int temp;
        if(L[i] < L[i - dlta])
        {
            temp = L[i];
            int j;
            for(j = i - dlta; j >= 0 && L[j] > temp; j-=dlta)L[j + dlta] = L[j];
            L[j + dlta] = temp;
        }
    }
}

void ShellSort(int* L, int* dlta, int k)                
{
    for(int i = 0; i < k; i++)
    {
        ShellInsert(L, dlta[i]);\进行一趟增量为dlta[i]的插入排序
    }
}