shell排序

1、知识导入

                            

2 、排序算法：

     shell 排序  基数排序  桶排序

2.1 希尔排序

  插入排序：

   希尔排序的思路：

（1.）插入排序的优化

 （2）步长：一开始设置为元素的个数/2

  (3)步长次序排序：每次排序完，步长减1，每次排序都是以步长为间隔单位给所有元素分组，组内作插入排序。

 

 3、代码实现1（插入排序）

#include <iostream>
using  namespace std;
/*******************
 * Project:希尔排序（即插入排序的优化）
 * 时间：2019-10-3
 * Author:zjl
 * ****************************************************/
//插入排序
void insertSort(int *a ,int len)
{//找待插入的元素
 //定义变量保存待插入元素
    int temp;
    int j;
    //知道循环次数用for ，不知道循环次数用while
    for(int i=1;i<len;i++)
    {
        temp=a[i];//保存待插入元素
        j=i-1;
        //待插入元素之前数据后移
        while (j>=0&&a[j]>temp) {
           //数据后移操作
            a[j+1]=a[j];
            j--;
        }
        //待插入元素赋值给a【j】
        a[j+1]=temp;
    }

}
//打印
void  print(int *a,int  len)
{
    //遍历输出
    for(int i=0;i<len;i++)
    {
        printf("%d",a[i]);
    }
    cout<<endl;
}
int  main()
{  //插入排序测试
    int  a[10]={9,66,54,33,-5,78,123,0,8,7};
    printf("before sort");
    print(a,10);
    insertSort(a,10);
    printf("After sort");
    print(a,10);
    return  0;
}

4.代码实现2（希尔排序）

#include <iostream>
using  namespace std;
/*******************
 * Project:希尔排序（即插入排序的优化）
 * 时间：2019-10-3
 * Author:zjl
 * ****************************************************/
//插入排序
void insertSort(int *a ,int len)
{//找待插入的元素
 //定义变量保存待插入元素
    int temp;
    int j;
    //知道循环次数用for ，不知道循环次数用while
    for(int i=1;i<len;i++)
    {
        temp=a[i];//保存待插入元素
        j=i-1;
        //待插入元素之前数据后移
        while (j>=0&&a[j]>temp) {
           //数据后移操作
            a[j+1]=a[j];
            j--;
        }
        //待插入元素赋值给a【j】
        a[j+1]=temp;
    }

}
//打印
void  print(int *a,int  len)
{
    //遍历输出
    for(int i=0;i<len;i++)
    {
        printf("%d",a[i]);
    }
    cout<<endl;
}
//shell 排序
void  shell_Sort(int *a,int len)
{
    //计算步长
    int  step=len/2;
    int temp;
    int j;
    //2.按照步长来做插入排序，每次步长减去1
    while(step>=1)
    {//分组插入排序
    for(int i=step;i<len;i++) //分组排序都是从
    {
        temp=a[i];//保存待插入数据
        j=i-step;
        while(j>=0&&a[j]>temp)
        {
            a[j+step]=a[j];
            j=j-step;
        }
        //将待插入的数据存放刀a[j+1]中去
        a[j+step]=temp;

    }
         step=step/2;
    }
}



int  main()
{  //插入排序测试
    int  a[10]={9,66,54,33,-5,78,123,0,8,7};
    printf("before sort");
    print(a,10);
    insertSort(a,10);
    printf("After sort");
    print(a,10);
 //进行希尔排序
    shell_Sort(a,10);
    print(a,10);
    return  0;
}