希尔排序（C/java）

算法思想：希尔排序是一种插入排序法。先将待排序序列分割成若干个“稀疏”的子序列，分别进行直接插入排序。

1.首先选定元素之间的距离为step1，将序列中所有间隔为step1的元素分为一组，然后进行组内直接插入排序。（step1取n/2）

2.然后再取距离为step2，将所有间隔为step2的元素分为1组，进行组内直接插入排序,（step1/2=step2）。

3.一直取到step的值为1，此时挣个序列只有一个子序列，对该序列完成直接插入排序，从而完成整个排序过程。

因此希尔排序又称缩小增量排序。

举例：

                                           46   55    13    42   94   17   05   70                   

核心代码段：

void shellsort(int a[],int n)
{
    int step = 0;//距离
    int i,j;
    for(step=n/2;step>0;step=step/2)//每次距离除以二直到距离到1为止
    {
    	//每一趟循环采用直接插入排序 
        for(i=step;i=step&&temp

 算法分析：

1.增量的取法：最初shell提出step=n/2，再取step=step/2,直到step=1为止。该思路的缺点是奇数位置的元素只有在最后一步才能与偶数位置的元素进行比较，使得希尔排序效率降低。后来Knuth提出了step=(step/3)+1。不过step的取值没有最优性。

2.算法性能：当step=1时，希尔排序相当于一次直接插入排序，但此时元素序列已经基本有序，相对于“直接的”直接插入排序而言移动次数会大大减少。一般认为希尔排序的时间复杂度为O(n^1.5),优于直接插入排序。

希尔排序对于中等规模(n<=1000)的序列有较高的效率。

3.算法的稳定性：希尔排序是一种不稳定排序算法。

举例：{7(1),10,1,7(2)}，排序后{1,7(2),7(1),10}，所以希尔排序不稳定。

#include
void printArray(int a[],int n)
{
	for(int i=0;i0;step=step/2)//每次之后距离除以二直到距离到1为止
    {
    	//每一趟循环采用直接插入排序 
        for(i=step;i=step&&temp

运行结果：

 java可执行代码：

package one;
import java.util.Scanner;
public class shellSort {
    public static void main(String[]args){
        Scanner input=new Scanner(System.in);
        int[]a=new int[10];
        System.out.println("please enter 10 numbers");
        for(int i=0;i0;step=step/2)
        {
            
            for(i=step;i=step&&temp

运行结果：