文档章节

排序篇 - 插入排序的实现

狮子的魂
 狮子的魂
发布于 2012/10/20 22:55
字数 462
阅读 90
收藏 1

插入排序是最基本的排序算法,在所有的O(n^2)的排序算法中,它的效率是很不错的。至于说更高级的排序实现,请接着关注后面排序算法。这里是贴出代码,不讲解算法的过程,谷歌一下,太多了。

(代码用了很久了,可以直接拿来用,已泛型化)

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头文件代码:



/*
 * jsort functions header file.
 * 
 * @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; 
		}
	}


有什么问题,我们一起讨论。

© 著作权归作者所有

共有 人打赏支持
狮子的魂

狮子的魂

粉丝 205
博文 11
码字总数 11922
作品 7
深圳
CEO
私信 提问
算法系列【希尔排序】篇

常见的内部排序算法有:插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括: 关于时间复杂度: 1. 平方阶 (O(n2)) 排序各类简单排序:直接插入...

湖南小影
2017/05/18
0
0
算法系列【希尔排序】篇

常见的内部排序算法有:插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括: 关于时间复杂度: 1. 平方阶 (O(n2)) 排序各类简单排序:直接插入...

湖南小影
2017/05/18
0
0
算法系列【希尔排序】篇

常见的内部排序算法有:插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括: 关于时间复杂度: 1. 平方阶 (O(n2)) 排序各类简单排序:直接插入...

湖南小影
2017/05/18
0
0
算法系列【希尔排序】篇

常见的内部排序算法有:插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括: 关于时间复杂度: 1. 平方阶 (O(n2)) 排序各类简单排序:直接插入...

湖南小影
2017/05/18
0
0
算法系列【希尔排序】篇

常见的内部排序算法有:插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括: 关于时间复杂度: 1. 平方阶 (O(n2)) 排序各类简单排序:直接插入...

湖南小影
2017/05/18
0
0

没有更多内容

加载失败,请刷新页面

加载更多

合理设置线程池大小

要想合理的配置线程池的大小,首先得分析任务的特性,可以从以下几个角度分析: 任务的性质:CPU密集型任务、IO密集型任务、混合型任务。 任务的优先级:高、中、低。 任务的执行时间:长、中...

飓风2000
12分钟前
0
0
git checkout命令详解

在实际应用中,git checkout是最为常见命令之一。 此命令参数众多,功能多样,但有些功能可能整个职业生涯都不会用到,所以本文只介绍最为实用的部分。 如果想要了git checkout命令所有功能,...

天王盖地虎626
12分钟前
0
0
jquery中处理ajax跨域的三大方式

之前mui项目开发过程遇到过跨域问题,搜集了下关于相关跨域的解决方案: 一、处理跨域的方式: 1.代理 2.XHR2 HTML5中提供的XMLHTTPREQUEST Level2(及XHR2)已经实现了跨域访问。但ie10以下...

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

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部