/**/

# 希尔排序

## Knuth公式

h=h * 3 + 1
where -
h is interval with initial value 1

## 希尔排序伪代码

procedure shellSort()
A : array of items

/* calculate interval*/
while interval < A.length /3 do:
interval = interval * 3 + 1
end while

while interval > 0 do:

for outer = interval; outer < A.length; outer ++ do:

/* select value to be inserted */
valueToInsert = A[outer]
inner = outer;

/*shift element towards right*/
while inner > interval -1 && A[inner - interval] >= valueToInsert do:
A[inner] = A[inner - interval]
inner = inner - interval
end while

/* insert the number at hole position */
A[inner] = valueToInsert

end for

/* calculate interval*/
interval = (interval -1) /3;

end while

end procedure

## C实现希尔排序

#include <stdio.h>
#include <stdbool.h>

#define MAX 7

int intArray[MAX] = {4,6,3,2,1,9,7};

void printline(int count) {
int i;

for(i = 0;i < count-1;i++) {
printf("=");
}

printf("=\n");
}

void display() {
int i;
printf("[");

// navigate through all items
for(i = 0;i < MAX;i++) {
printf("%d ",intArray[i]);
}

printf("]\n");
}

void shellSort() {
int inner, outer;
int valueToInsert;
int interval = 1;
int elements = MAX;
int i = 0;

while(interval <= elements/3) {
interval = interval*3 +1;
}

while(interval > 0) {
printf("iteration %d#:",i);
display();

for(outer = interval; outer < elements; outer++) {
valueToInsert = intArray[outer];
inner = outer;

while(inner > interval -1 && intArray[inner - interval]
>= valueToInsert) {
intArray[inner] = intArray[inner - interval];
inner -=interval;
printf(" item moved :%d\n",intArray[inner]);
}

intArray[inner] = valueToInsert;
printf(" item inserted :%d, at position :%d\n",valueToInsert,inner);
}

interval = (interval -1) /3;
i++;
}
}

int main() {
printf("Input Array: ");
display();
printline(50);
shellSort();
printf("Output Array: ");
display();
printline(50);
return 1;
}
Input Array: [4 6 3 2 1 9 7 ]
==================================================
iteration 0#:[4 6 3 2 1 9 7 ]
item moved :4
item inserted :1, at position :0
item inserted :9, at position :5
item inserted :7, at position :6
iteration 1#:[1 6 3 2 4 9 7 ]
item inserted :6, at position :1
item moved :6
item inserted :3, at position :1
item moved :6
item moved :3
item inserted :2, at position :1
item moved :6
item inserted :4, at position :3
item inserted :9, at position :5
item moved :9
item inserted :7, at position :5
Output Array: [1 2 3 4 6 7 9 ]
==================================================

## 猜你喜欢

Java性能调优实战 -〔刘超〕

DevOps实战笔记 -〔石雪峰〕

Spark性能调优实战 -〔吴磊〕

React Native 新架构实战课 -〔蒋宏伟〕