## 排序篇 - 插入排序的实现 原

狮子的魂

（代码用了很久了，可以直接拿来用，已泛型化）

C的实现：

``````/*
* insertion sort algorithm implements.
*
* @author chenxin
* @see http://www.webssky.com
*/
#include <stdlib.h>
#include "jsort.h"

void copy_value_to( void *a, void *b, size_t size ) {
unsichar_t *__a = ( unsichar_t * ) a;
unsichar_t *__b = ( unsichar_t * ) b;

do {
*__b++ = *__a++;
} while ( --size > 0 );
}

/*
* insertion sort.
* @param *a the pointer of the array to sort.
* @param size the bytes of one item in the array.
* @param start the start index.
* @param end the end index.
*/
void insertion_sub_sort( void *a, size_t size, \
compare_fn_t comp, size_t start, size_t end ) {

register int i, j;

unsichar_t *__ichar_p = ( unsichar_t * ) a;

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

for ( i = start + 1; i <= end; i++ ) {
copy_value_to( __ichar_p + i * size, tmp, size );
for ( j = i;
j > start && comp( tmp, \
(prev = __ichar_p + ( j - 1 ) * size) ) < 0; j-- ) {
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 );
}

/*
* insertion sort.
* @param *a the pointer of the array to sort.
* @param len the length of the array.
*/
void insertion_sort( void *a, size_t len, size_t size, compare_fn_t comp ) {
insertion_sub_sort( a, size, comp, 0, len - 1 );
}``````

jsort.h头文件代码：

``````/*
*
* @author chenxin
* @see http://www.webssky.com
*/
#ifndef __JSORT_H
#define __JSORT_H

typedef unsigned char unsichar_t;
typedef int ( * compare_fn_t )( void *, void * );

extern void copy_value_to( void *, void *, size_t size );

extern void swap_value( void *, void *, size_t size );

extern void insertion_sort( void *, size_t len, size_t size, compare_fn_t );

extern void insertion_sub_sort( void *, size_t size, compare_fn_t, size_t start, size_t end );

extern void shell_sort( void *, size_t len, size_t size, compare_fn_t );

extern void merge_sort( void *, size_t len, size_t size, compare_fn_t );

extern void quicksort( void *, size_t len, size_t size, compare_fn_t );

extern void bucket_sort( size_t *a, size_t len, size_t m );

#endif /*end of jsort*/``````

Java的实现：

``````/**
* insert sort method. <br />
*
* @param arr an array of a comparable items.
*/
public static <T extends Comparable<? super T>> void insertionSort( T[] arr ) {
int j;
for ( int i = 1; i < arr.length; i++ ) {
T tmp = arr[i];
for ( j = i; j > 0 && tmp.compareTo(arr[j-1]) < 0; j--) {
arr[j] = arr[j-1];
}
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

12分钟前
0
0
git checkout命令详解

12分钟前
0
0
jquery中处理ajax跨域的三大方式

ZhangLG
13分钟前
0
0
HTTP访问控制（CORS）

HTTP访问控制（CORS）

gdxz110
15分钟前
0
0
11g DG中的参数

11g DG中的SEC_CASE_SENSITIVE_LOGON参数 在一次配置dg完成后，备库会时不时的无法自动应用日志，后台日志报错如下： 期间排除了修改sys密码问题、网络问题、参数_system_trig_enabled问题（...

19分钟前
0
0