一、shell排序

1.shell排序原理

       shell排序，和Linux的shell程序没有关系；shell排序得名的原因是该排序方法是DL. Shell于1959年基于直接插入排序算法改进提出的，所以命名为shell排序。

      shell排序是基于直接插入排序改进的。

      直接插入排序的思想是：构建一个有序的序列，把新的数字插入到有序序列当中。直接插入排序到问题在于：每次插入都会移动大量空间，造成时间复杂度过大。直接插入排序到时间复杂度为O(n^2)。

      shell排序基于直接插入排序改进：把整个序列分割为多个部分进行插入排序，然后再进行子序列合起来，再进行插入插入排序；这样，减少移动空间次数。直接插入排序的平均时间复杂度为O(n^1.3)；最坏的时间复杂度为O(n^2)。

2.代码分析

 int increment=L->last+1;

先将increment的位置放置最后一位

increment=increment/3+1;

此处为选取增量，但如何去选择现在并没有明确的较好的方式去确定

        for(i=increment;i<=L->last;i++)
        {
            if(L->data[i]<L->data[i-increment])
            {   
                //将data[i]的位置空出来,将值暂存在temp中
                int temp=L->data[i];
                for(j=i-increment;j>=0&&L->data[j]>temp;j-=increment)
                {
                    L->data[j+increment]=L->data[j];
                }
                L->data[j+increment]=temp;
            }
        }

进行循环比较，其比较原理是将较小的数放在前面 ，较大的数放在后面，其比较间隔为increment.

其比较方式在下图中做一个简单的解释：

 表中一共有9个元素，则increment为4，那么在比较时间隔四个。

则为 1与5比较；2与6比较；3与7比较；4与8比较；5与9比较；并将较小的值放到前面。第一次循环结果为：

当第二次循环时，increment = 4/3 + 1 =2,

则为：1与3比较；2与4比较；3与5比较；4与6比较；5与7比较；6与8比较；7与9比较，其结果为：

当第三次循环是，increment = 1；则为每一位和他的下一位做比较；

其结果为：

由于采用的是do....while语句，所以即便我们采用的退出条件为 increment >1 但当其＝1时，仍要进行一次循环。

另外以上示列并没有完全展现出代码的功能，其中一段代码为：

                for(j=i-increment;j>=0&&L->data[j]>temp;j-=increment)
                {
                    L->data[j+increment]=L->data[j];
                }

 其作用是进行二次比较，例如：

在这组数组当中，当Increment为4的时候，1和5比较后，1号位为 5 ；5号位为6；但当5号为和9号位比较时，5号位变为4，9号位变为5，当后置位交换到前置位时还应和前前置位比较，意为5号位还需要和1号为比较，此时1号位变为4，5号位变为5.以上便是这一段代码的作用。

其完功能代码完整代码为：

#include "sqlist.h"

void shellsort(sqlist_t *L)
{
    int i,j;
    int increment=L->last+1;
    do
    {
        //每轮比较间隔,也叫增量序列
        increment=increment/3+1;
        for(i=increment;i<=L->last;i++)
        {
            if(L->data[i]<L->data[i-increment])
            {   
                //将data[i]的位置空出来,将值暂存在temp中
                int temp=L->data[i];
                for(j=i-increment;j>=0&&L->data[j]>temp;j-=increment)
                {
                    L->data[j+increment]=L->data[j];
                }
                L->data[j+increment]=temp;
            }
        }
    }while(increment>1);
    return ;
}

其获取随机书代码为：

int sqlist_insert(sqlist_t *L, data_t x, int pos)
{
    if(L==NULL)
    {
        printf("list no exist!\n");
        return -1;
    }
    if(is_full(L) || pos < 0 || pos > (L->last+1))
    {
        printf("sqlist can not insert\n");
        return -1;
    }
    for(int i=L->last;i>=pos;i--)
    {
        L->data[i+1]=L->data[i];
    }
    L->data[pos]=x;
    L->last+=1;
    return 0;
}

其头文件为：

#ifndef _SQLIST_H
#define _SQLIST_H

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define MAXSIZE 100
typedef int data_t;
typedef struct
{
    data_t data[MAXSIZE];
    int last;
}sqlist_t;

int sqlist_insert(sqlist_t *L, data_t x, int pos);

#endid

其主函数为：

#include "sqlist.h"

int main(int argc, char *argv[])
{ 
    srand(time(NULL));
	sqlist_t *L = NULL;
	sqlist_init(&L);
	if(is_full(L) == 1)
		printf("full!\n");
	else
		printf("no full!\n");
    int i=0,ra=0;
	while(i < 10){
		sqlist_insert(L,(ra=rand()%20) , i);
		i++;
	}
	sqlist_show(L);
    shellsort(L);
    sqlist_show(L);
    retuen 0 ;
}

以下为代码运行结果：

no full!
L->data[0]: 9
L->data[1]: 7
L->data[2]: 1
L->data[3]: 14
L->data[4]: 1
L->data[5]: 3
L->data[6]: 2
L->data[7]: 1
L->data[8]: 9
L->data[9]: 14
----------------
L->data[0]: 1
L->data[1]: 1
L->data[2]: 1
L->data[3]: 2
L->data[4]: 3
L->data[5]: 7
L->data[6]: 9
L->data[7]: 9
L->data[8]: 14
L->data[9]: 14
----------------
 

总结

shell排序是将慢速排序提向高速排序的先锋，在整个代码中唯一一个不太容易理解的点在于increment/+1这一个增量当中，但作为一个新手这貌似也不在我的考量范围之内。

以上分享借鉴了《大话数据结构》