数据结构(c语言)--排序算法之插入排序（直接插入排序、希尔排序）_c语言直接插入排序用链式存储

数据结构(c语言)–排序算法之插入排序（直接插入排序、希尔排序）

一：插入排序

插入排序的基本思想：是每次将一个待排序的记录按其关键字的大小插入前面已经排好序的子序列当中。
插入排序种类包括：直接插入排序、折半插入排序、希尔排序。

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

1、直接插入排序

(1):算法思想

假设待排序表L[1 …n]在一次的排序过程中的一时刻如下：

此时，要将L[i]插入到有序序列中的步骤：

• 在有序序列 L[1…i-1]中查到 L[i] 要插入的位置k
• 将有序序列L[k+1…i-1]中的所有元素往后移动一个单位
• L[k]=L[i]元素复制

(2):算法实现

#include "stdio.h"
typedef int Element;
void InsertSort01(Element a[],int n){   //带哨兵的
    int i,j;
    for ( i = 2; i <n ; i++) { //初始时，a[1]可以视为一个已经排好序的元素
        if(a[i]<a[i-1]) {         //如果改元素小于其前驱，就将其插入到有序表中
            a[0] = a[i];
            for (j = i - 1; a[0] < a[j]; --j) {
                a[j + 1] = a[j];
            }
            a[j + 1] = a[0];
        }
    }
}
void InsertSort02(Element a[],int n){     //不带哨兵
    int i,j;
    int temp;
    for (i = 1; i < n; ++i) {
        if(a[i]<a[i-1]){
            temp=a[i];
            for ( j = i-1; a[j]>temp ; --j) {
                a[j+1]=a[j];
            }
            a[j+1]=temp;
        }
    }
    printf("不用哨兵时零时变量temp=%d",temp);
}
int main(){
    Element a[9]={0,49,38,65,97,76,13,27,49};    //初始化一个数组,a[0]为哨兵
    Element b[8]={49,38,65,97,76,13,27,49};
    InsertSort01(a,9);
    for (int i = 0; i < 9; ++i) {
        printf("%d ,",a[i]);
    }
    printf("\n");
    InsertSort02(b,8);
    printf("\n");
    for (int i = 0; i < 8; ++i) {
        printf("%d ,",b[i]);
    }
    return 0;
}
/**
   输出结果：
   49 ,13 ,27 ,38 ,49 ,49 ,65 ,76 ,97 ,
   不用哨兵时零时变量temp=49
   13 ,27 ,38 ,49 ,49 ,65 ,76 ,97 ,
 */
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

(3):性能分析

空间复杂度：O(1)–把已经排好序的元素向后挪位，为元素提供新的插入空间；并没有借助其它的辅助空间。
时间复杂度：向有序子表中插入元素的操作进行了n-1趟，每趟操作都分为比较关键字和移动元素，其中比较和移动的次数取决于待排序表的初始状态。

• 最好情况：O(n)表元素已经有序，此时插入每个元素只需要比较一次而不需要移动
• 最坏情况：O(n*n)表中的元素和想要排序的顺序刚好相反
• 平均情况：O(n*n)

稳定性：直接插入排序是稳定的插入排序算法。
适用性：直接插入排序适用于顺序存储或者链式存储(要从前往后查找指定元素的位置)。

(4):图示过程

红色标注的可以理解为所用的“哨兵”或者temp零时变量。

2、折半插入排序

(1):算法思想

思想：在直接插入排序的思想上，将比较(折半查找实现)和移动操作分离,减少了比较元素的次数

(2):算法实现

#include "stdio.h"
typedef int Element;
void InsertSort01(Element a[],int n){   //带哨兵的
    int i,j;
    int low,high,mid;
    for ( i = 2; i <n ; i++) { //初始时，a[1]可以视为一个已经排好序的元素
        a[0] = a[i];            //将a[i]暂存到a[0]中
        low=1,high=i-1;
        while (low<=high){
            mid=(high+low)/2;   //取中间点
            //***注意：当a[mid]=a[0]时，继续执行low=mid+1;以保证算法的稳定性，最后将a[0]插入到a[high+1]处
            if(a[mid]>a[0])
                high=mid-1;     //查左半区间
            else
                low=mid+1;      //查右半区间
        }
        for ( j = i-1; j >=high+1 ; --j) {
            a[j+1]=a[j];        //移动元素，空出插入位置
        }
        a[high+1]=a[0];         //插入操作
    }
}
void InsertSort02(Element a[],int n){     //不带哨兵
    int i,j;
    int temp;
    int low,high,mid;
    for ( i = 2; i <n ; i++) { //初始时，a[1]可以视为一个已经排好序的元素
        temp = a[i];            //将a[i]暂存到temp中
        low=1,high=i-1;
        while (low<=high){
            mid=(high+low)/2;   //取中间点
            //***注意：当a[mid]=temp时，继续执行low=mid+1;以保证算法的稳定性，最后将temp插入到a[high+1]处
            if(a[mid]>temp)
                high=mid-1;     //查左半区间
            else
                low=mid+1;      //查右半区间
        }
        for ( j = i-1; j >=high+1 ; --j) {
            a[j+1]=a[j];        //移动元素，空出插入位置
        }
        a[high+1]=temp;         //插入操作
    }
    printf("不用哨兵时零时变量temp=%d",temp);
}
int main(){
    Element a[9]={0,49,38,65,97,76,13,27,49};    //初始化一个数组,a[0]为哨兵
    Element b[8]={49,38,65,97,76,13,27,49};
    InsertSort01(a,9);

    for (int i = 0; i < 9; ++i) {
        printf("%d ,",a[i]);
    }
    printf("\n");
    InsertSort02(b,8);
    printf("\n");
    for (int i = 0; i < 8; ++i) {
        printf("%d ,",b[i]);
    }
    return 0;
}
/**
 * 输出结果：
   49 ,13 ,27 ,38 ,49 ,49 ,65 ,76 ,97 ,
   不用哨兵时零时变量temp=49
   49 ,27 ,38 ,49 ,49 ,65 ,76 ,97 ,
 */
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

(3):性能分析

空间复杂度：O(1)
时间复杂度：O(n*n)
适用性：对于数据量不大的排序表会有很好的性能
稳定性：稳定的

3、希尔排序

(1):算法思想

  基本思想：先将待排序表分割成若干形如L[i,i+d,i+2d,i+3d…,i+kd]这样"特殊的子表"，即把相隔某个”增量“的记录组成一个子表，对各个子表进行直接插入排序，当整个表的元素已呈”基本有序“时，再对全体记录进行一次直接插入排序。

  希尔排序的过程：先取一个小于n的步长d1，把表中的全部记录分成d1组(d建议每次减半，直到1)，所有距离为的d1的的倍数的记录放在同一组，在各组内进行直接插入排序，然后取第二个步长d2重复；直到步长为1，即所有记录已经放在了同一组中(局部有序)，在进行一次直接插入排序。

(2):算法实现

#include "stdio.h"
typedef int Element;
void Print(int a[],int n){
    for (int i = 0; i < n; ++i) {
        printf("%d\t",a[i]);
    }
    printf("\n");
}
void shellSort(Element a[],int n){
    int i,j;
    int temp;
    //当j<=0时，插入位置已到，a[0]只是暂存单元
    for (int dk = n/2; dk >0 ; dk=dk/2) {  //步长变化
        for ( i = dk+1; i <n ; ++i) {
            if(a[i]<a[i-dk]){
                temp=a[i];          //用a[0]暂存
                for ( j = i-dk; j >0&& temp<a[j] ; j=j-dk)
                    a[j+dk]=a[j];   //记录后移
                a[j+dk]=temp;       //插入
            }
        }
        Print(a,n);
    }
}

int main(){
    Element a[9]={3,49,38,65,97,76,13,27,49};    //初始化一个数组,a[0]为哨兵
    shellSort(a,9);
    for (int i = 0; i < 9; ++i) {
        printf("%d ,",a[i]);
    }
    return 0;
}
/**
 * 输出结果：
3       49      13      27      49      76      38      65      97
3       27      13      49      38      65      49      76      97
3       13      27      38      49      49      65      76      97
3 ,13 ,27 ,38 ,49 ,49 ,65 ,76 ,97 ,
 */
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

(3):性能分析

空间复杂度：O(1)–仅使用了常数个辅助单元
时间复杂度：O（pow（n,1.3)）;最坏：O（n*n）
稳定性：不稳定