def ShellSort(ary):
length = len(ary)
gap = round(length)
step = length//2
while step:
for i in range(step,length,step):
tmp = ary[i]
for j in range(i,0,-step):
if ary[j-step] > tmp:
ary[j] = ary[j-step]
else:
break
ary[j] = tmp
if step == 1:
break
step = step//2
ary = [1,23,4,53,55,34,3,99,14]
ShellSort(ary)
print(ary)
inputOrder: [5,4,1]
#include <stdio.h>
struct _Node{
int value;
struct _Node *left;
struct _Node *right;
int height;
};
typedef struct _Node Node;
int max( int a, int b )
{
return(a>b?a:b);
}
int Height( Node* tree )
{
if( NULL == tree ) {
return -1;
}
return tree->height;
}
int InitTree( Node* tree, int value )
{
if( tree == NULL ) {
return -1;
}
tree->value = value;
tree->left = NULL;
tree->right = NULL;
tree->height = 0;
return 0;
}
Node* SingleRotateWithLeft( Node* k1 )
{
Node* k2;
k2 = k1->left;
k1->left = k2->right;
k2->right = k1;
k1->height = max(Height(k1->left), Height(k1->right)) + 1;
k2->height = max( Height(k2->left), Height(k1) ) + 1;
return k2;
}
Node* InsertTree(Node *tree, Node *new_node )
{
if( new_node->value > tree->value ) {
if( tree->right == NULL ) {
tree->right = new_node;
} else {
InsertTree( tree->right, new_node );
}
} else {
if( tree->left == NULL ) {
tree->left = new_node;
} else {
InsertTree( tree->left, new_node );
if( Height(tree->left) - Height(tree->right) == 2 ) {
if( new_node->value < tree->left->value ) {
tree = SingleRotateWithLeft(tree);
}
}
}
}
tree->height = max(Height(tree->left),Height(tree->right)) + 1;
return tree;
}
void OrderTraverse( Node* tree )
{
if( tree != NULL ) {
printf("value:%d height:%d\t\n", tree->value,tree->height);
OrderTraverse( tree->left );
OrderTraverse( tree->right );
}
}
int main()
{
Node *tree = NULL;
tree = (Node*)malloc(sizeof(Node));
InitTree(tree, 5);
int i = 0;
int array[10] = {4,1};
for( i = 0; i < 2; i++ ) {
Node *node = NULL;
node = (Node*)malloc(sizeof(Node));
if( NULL == node ) {
continue;
}
InitTree(node,array[i]);
tree = InsertTree(tree,node);
}
printf("preOrderTraverse:\n");
OrderTraverse(tree);
printf("succeed!\n");
return 0;
}
#include <stdio.h>
struct _Node{
int value;
struct _Node *left;
struct _Node *right;
};
typedef struct _Node Node;
int InitTree( Node* tree, int value )
{
if( tree == NULL ) {
return -1;
}
tree->value = value;
tree->left = NULL;
tree->right = NULL;
}
int InsertTree(Node *tree, Node *new_node )
{
if( new_node->value > tree->value ) {
if( tree->right == NULL ) {
tree->right = new_node;
} else {
InsertTree( tree->right, new_node );
}
} else {
if( tree->left == NULL ) {
tree->left = new_node;
} else {
InsertTree( tree->left, new_node );
}
}
}
void OrderTraverse( Node* tree )
{
if( tree != NULL ) {
printf("%d ", tree->value);
OrderTraverse( tree->left );
OrderTraverse( tree->right );
}
}
int main()
{
Node *tree = NULL;
tree = (Node*)malloc(sizeof(Node));
InitTree(tree, 4);
int i = 0;
int array[10] = {4,1,6,9,7,8,3,2,5};
for( i = 0; i < 9; i++ ) {
Node *node = NULL;
node = (Node*)malloc(sizeof(Node));
if( NULL == node ) {
continue;
}
InitTree(node,array[i]);
InsertTree(tree,node);
}
OrderTraverse(tree);
printf("succeed!\n");
return 0;
}
// TODO: Replace examples and use TDD development by writing your own tests. The code provided here is just a how-to example.