插入排序和希尔排序的比较_插入排序 希尔排序 用时对比

希尔排序中用了一个插入排序，总是理解不好，在这里比较一下，主要是关于取未排序序列中的下一个元素的问题

void InsertionSort(int A[], int N)
{
	int P, i;
	for (P = 1; P < N; P++)
	{
		int tmp = A[P];
		for (i = P; i > 0 && A[i - 1] > tmp; i--)
			A[i] = A[i - 1];
		A[i] = tmp;
	}
}

插入排序：手里拿着第一张牌，每次抽后面一张牌tmp进行比较，排序

void ShellSort(int A[], int N)
{
int D, P, i;
for(D=N/2;D>0;D/=2)
for (P = D; P < N; P++)
{
int tmp = A[P];
for (i = P; i >= D&&A[i - D] > tmp; i -= D)
A[i] = A[i - D];
A[i] = tmp;
}
}
希尔排序：比如我们第一次步长为5，进入第二个for以后，拿到的第一张牌tmp，之后对第一张牌排序（或者理解为对tmp及其之前的牌排序，其实是一样的，就是插入排序），第一次跳出for (P = D; P < N; P++)时已经把tmp查进去了，之后P++注意，这里变成里第二个以D为步长的序列，P++一次会变成下一个以D为步长的序列，所以，对于第一个步长为5的序列来说，它的第二张牌要到P达到第二个步长时才出现（与上面的插入排序不同，插入排序的P++就是下一张牌，希尔排序里的下一张牌要到下一个步长才能去到）。

所以，对于希尔排序来说，步长定了之后里面的循环是第一个以D为步长的序列增加一张牌、第2个以D为步长的序列增加一张牌、第3个以D为步长的序列增加一张牌。。。第D个以D为步长的序列增加一张牌、第一个以D为步长的序列增加第二张牌、第2个以D为步长的序列增加第二张牌。。。

之前就是这里没看明白，纠结了半天。语言表达有限，要是没懂可以留言，，我也是刚学，水平有限