文档章节

排序篇 - 希尔排序的实现

狮子的魂
 狮子的魂
发布于 2012/10/20 23:05
字数 468
阅读 97
收藏 2

希尔排序是首批冲破二次效率的排序算法。主要利用了插入排序的以下特性:

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

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

具体算法,谷歌一下吧。这里给出C和Java的实现。(代码已经用过很久了,可以直接拿来用,已泛型化)

注:增量序列来自公式:9 * pow(4, j) - 9 * pow(2, j) + 1 和 pow(4, j) - 3 * pow(2, j) + 1

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;
			}
		}
	}


有问题我们一起讨论。

© 著作权归作者所有

共有 人打赏支持
狮子的魂

狮子的魂

粉丝 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

没有更多内容

加载失败,请刷新页面

加载更多

使用Airflow来调度Data Lake Analytics的任务

今天我们来介绍一下使用Airflow来调度 Data Lake Analytics(后面简称DLA)的任务执行。DLA作为一个数据湖的解决方案, 客户有每天周期性的调度一些任务从DLA查询数据回流到业务系统的需求。因...

迷你芊宝宝
26分钟前
3
0
简单的file获取文本内容且, 修改文本内容(java8)

题主, 因入职新公司, 表设计混乱, 不得不手动写一个小脚本,获取所有字段后,重新写入至新表中; 思路 顺序如下 原sql 具体, 获取行 , 根据行开头的" ,"截取内容, 重新输入到txt, 中就可以了; 代...

尾生
34分钟前
3
0
嵌入式编程(一):51单片机如何将函数 定义到指定程序地址

在单片机编程使用中,会涉及到将某些函数定义到指定的code区。此时需要对工程文件进行配置修改才可完成。本期针对单片机平台做出说明介绍 1、测试目标 将函数testaddr定义到0x6000地址 2、测...

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
好程序员教程之配置H5的滚动条样式示例代码

配置H5的滚动条样式示例代码有不少的小伙伴在网上寻找,本篇文章好程序员小编和大家分享一下配置H5的滚动条样式示例代码,希望对HTML5开发感兴趣的小伙伴有所帮助,下面我们一块来看一下吧:...

好程序员IT
43分钟前
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部