[数据结构与算法]数据结构考研学习-第8章排序

这一篇介绍三种插入排序分别是：
直接插入排序，折半插入排序，希尔排序

1. 直接插入排序

直接插入排序是另外两种的基础也是核心思想：
每次将关键字大小插入到有序区域中（调整是从后向前），直到全部插入有序区域完成

不带哨兵

void inserSort(int A[],int n){,n个数据，递增排序
    int i ,j ,temp;
    for(i =1;i<n;i++){//数据放在0，n-1
        if(A[i]<A[i-1]){//前，第二个小于第一个，后
            temp = A[i];

            //比较中间量或者是关键字因为初始1个的时候我们认为就是有序的所以第二个就是关键字

            for(j = i-1;j>=0 && A[j]>temp;--j ){
                //从后往前检查有序队列中的数据和关键字

            A[j+1] = A[j];//大于关键字的后移
            }

        A[j+1] = temp;//将关键字复制到插入位置
        }
    }
}

测试数据
int d[]={49,38,65,7,76,13,27,49};
int n = 8;
inserSort2(d,n);
for(int i=0;i<n;i++){
cout<<d[i]<<", ";
}
cout<<endl;

哨兵机制

void inserSort2(int A[],int n){
    int i,j;
    for(int i=2;i<=n;i++){
        if(A[i] < A[i-1]){//无序,待调整
            A[0] = A[i];//哨兵
            for(j = i-1;A[0] <A[j]; --j){
                A[j+1] = A[j];//大于哨兵的元素依次后移
            }
        cout<<"J= "<<j<<endl;
        A[j+1] = A[0];//复制到该位置，上--，这里需要++
        }
    }

}

测试数据
int d[]={0,49,38,65,97,76,13,27,49};
int n = 8;
inserSort2(d,n);
for(int i=1;i<=n;i++){
cout<<d[i]<<", ";
}
cout<<endl;

2.折半插入排序

void insertSort(int A[],int n){
    int i,j ,mid,low ,high;
    for(i =2;i<= n; i++){
        A[0] = A[i];
        low  = 1;
        high = i-1;
        while( low <= high){//递增排序
            mid = (low+high)/2;
            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];//插入
    }

}

测试数据
int d[]={0,20,30,40,50,60,70,80,55,60,90,10};
int n = 11;
for(int i=1;i<=n;i++){
cout<<d[i]<<", “;
}
cout<<“折半插入排序结果：”<<endl;
insertSort(d,n);
for(int i=1;i<=n;i++){
cout<<d[i]<<”, ";
}

3.希尔排序

void sheelSort2(int A[], int n){
//希尔排序
    int d,i,j;
    for(d= n/2;d>=1;d=d/2){
    //步长变化，第一次是数据长度一半
        for(i =d+1;i <= n; ++i){
        //步长内排序直到为1，就是最终
            if(A[i] < A[i-d]){  
            //直接插入
                A[0] = A[i];
                for(j =i-d; j>0&& A[0] <A[j]; j-=d){
                //同一步调内的调整
                    A[j+d] = A[j];
                }
            A[j+d] = A[0];//插入
            }
        }
    }
}

测试数据
int d2[] = {0,49,38,65,97,76,13,27,49};
int n2 = 8;
for(int i=1;i<=n2;i++){
cout<<d2[i]<<", “;
}
sheelSort2(d2,n2);
cout<<“希尔排序结果：”<<endl;
for(int i=1;i<=n2;i++){
cout<<d2[i]<<”, ";
}
cout<<endl;

5.概述

1. 直接插入排序（折半插入排序）
   一般研究直接插入比较多，

• -基本有序 ，最好 ，时间复杂度O（1）

• -逆序 ，最坏 ，0(n^2)

• -平均 ，0(n^2)

• -只需要常数个辅助变量 ，空间 杂度 O（1）

• -稳定

2. 希尔排序
   时间复杂度未知，但不稳定

2021 ，冲冲冲！！！