## 排序篇 - 希尔排序的实现 原

狮子的魂

1.对于已经排好序的数据，插入排序表现为O(N)。

2.插入排序能不能更快的找到每个元素的位置。（引入了增量序列）。

C的实现：

``````/*
* shell sort functions implements file.
*
* @author chenxin
* @see http://www.webssky.com
*/
#include <stdlib.h>
//#include <stdio.h>
#include "jsort.h"

/*
* shell sort algorithm.
*
* @param *arr the pointer of the array to sort.
* @param len the length of the array.
*/
void shell_sort( void *a, size_t len, size_t size, compare_fn_t comp ) {
int gaps[] = {
1, 5,
19, 41,
109, 209, 505, 929,
2161, 8929,
16001, 36289, 64769,
146305, 260609, 587521,					//1000th
1045505, 2354689, 4188161, 9427969,
16764929, 37730305, 67084289,
150958081, 268386305, 603906049,
1073643521, 2147483647};

register int k = 0;
while ( gaps[k] < len ) k++ ;

register int i, j, gap;

unsichar_t *__ichar_p = ( unsichar_t * ) a ;

register unsichar_t *tmp = ( unsichar_t * ) malloc( size );
register unsichar_t *prev;

while ( k-- > 0 ) {
gap = gaps[k];
for ( i = gap; i < len; i++ ) {
copy_value_to( __ichar_p + i * size, tmp, size );
//printf("gap=%d, tmp=%d\n", gap, *(int*)tmp);
for ( j = i;
j >= gap && comp( tmp, \
( prev = __ichar_p + ( j - gap ) * size ) ) < 0; j -= gap ) {
copy_value_to( prev, __ichar_p + j * size, size );
}
if ( j < i )
copy_value_to( tmp, __ichar_p + j * size, size );
}
}

//free the heap memory
free( tmp );
}``````

jsort.h头文件代码在“排序篇 - 插入排序的实现”中可以找到。

Java的实现：

``````public static final int[] GAPS = new int[] {
1, 5,
19, 41,
109, 209, 505, 929,
2161, 8929,
16001, 36289, 64769,
146305, 260609, 587521,					//1000th
1045505, 2354689, 4188161, 9427969,
16764929, 37730305, 67084289,
150958081, 268386305, 603906049,
1073643521, 2147483647};

/**
* shell sort algorithm. <br />
*
* @param arr an array of Comparable items.
*/
public static <T extends Comparable<? super T>> void shellSort( T[] arr ) {
int j, k = 0, gap;
for ( ; GAPS[k] < arr.length; k++ ) ;

while ( k-- > 0 ) {
gap = GAPS[k];
for ( int i = gap; i < arr.length; i++ ) {
T tmp = arr[ i ];
for ( j = i;
j >= gap && tmp.compareTo( arr[ j - gap ] ) < 0; j -= gap ) {
arr[ j ] = arr[ j - gap ];
}
if ( j < i ) arr[ j ] = tmp;
}
}
}``````

### 狮子的魂

CEO

2017/05/18
0
0

2017/05/18
0
0

2017/05/18
0
0

2017/05/18
0
0

2017/05/18
0
0

26分钟前
3
0

34分钟前
3
0

Music121
37分钟前
1
0
Java Android几个重要的基础知识

Java 1.数据类型 bit(位):0或1计算机存储处理信息的最基本的单位 byte（字节）：8个bit（上面表格数字的单位是byte） 2. m与n数值交换 //m=2,n=3; m=m^n; //m=2^3 n =m^n; //n =2^3^3=2 m=m...

Coding缘
40分钟前
4
0

43分钟前
2
0