数据结构-希尔排序

每次对5个间隔的元素进行插入排序，然后间隔依次递减，直到间隔为1

互质：相邻的两个元素没有公因子

这个例子只有间隔1起来作用

#include<iostream>
using namespace std;
typedef int ElmentType;
void shell_Sort(ElmentType A[], int N) {/*希尔排序-用Sedgewick增量*/int Si, D, P, i;ElmentType Tmp;/*这里只列出一小部分增量 */int Sedgewick[] = { 929,505,209,109,41,19,5,1,0 };for (Si = 0; Sedgewick[Si] >= N; Si++);/*初始化的增量Sedgewick[Si]不能超过待排序列长度*/for(D=Sedgewick[Si];D>0;D=Sedgewick[++Si])for (P = D; P < N; P++) {//插入排序Tmp = A[P];for (i = P; i >= D && A[i - D] > Tmp; i -= D)A[i] = A[i - D];A[i] = Tmp;}}
int main()
{ElmentType A[10] = { 1,2,0,9,3,5,4,7,6,9 };shell_Sort(A, 10);for (int i = 0; i < 10; i++)cout << A[i] << " ";cout << endl;return 0;
}