希尔排序
希尔排序是插入排序的一种改进,用大O表示法,其算法时间复杂度为O(nlogn)
其基本思想是:
先将整个待排元素序列分割成若干个子序列(由相隔某个“增量”的元素组成的)分别进行直接插入排序,然后依次缩减增量再进行排序,待整个序列中的元素基本有序(增量足够小)时,再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下(接近最好情况),效率是很高的,接近O(n),因此希尔排序在时间效率上比插入排序有较大提高。
希尔排序java实现:
/**
* shell sort is an improved insertion sort
*/
public class ArrayShell {
private long[] a;
private int nElement;
public ArrayShell(int max) {
this.a = new long[max];
this.nElement = 0;
}
public void shellSort(){
int outer,inner;
//calculate the initial value of sort interval
int h=1;
while(h<=nElement/3){
h=h*3+1;
}
while(h>0){
for(outer=h;outer<nElement;outer++){
long temp = a[outer];//挖走outer,放到temp里
inner = outer;//初始化inner为outer索引
while(inner>h-1 && a[inner-h]>temp){//增量h的左边那个大,
a[inner] = a[inner-h];//把左边大的填到挖走的地方
inner -= h;//把inner指向左边被挖走的大的地方
}
a[inner] = temp;//把temp填到左边被挖走的大的地方
}
h=(h-1)/3;//减小增量h
}
}
public void insert(long v){
a[nElement++]=v;
}
public void display(){
for(int i=0;i<nElement;i++){
System.out.print(a[i]+"\t");
}
System.out.print("\n");
}
}
直接插入排序基本思想:
每次将一个待排序的记录,按其关键字大小插入到前面已经排好序的子序列中的适当位置,直到全部记录插入完成为止。
直接插入排序java实现:
public class ArrayIns {
private long[] a;
private int nElement;
public ArrayIns(int max) {
a= new long[max];
nElement = 0;
}
public void insertionSort(){
int out,in;
for(out=1;out<nElement;out++){
if(a[out-1]>a[out]){
long temp = a[out];
for(in = out-1;in>=0 && temp<a[in];in--){
a[in+1]=a[in];
}
a[in+1]=temp;
}
}
}
public void insert(long v){
a[nElement++]=v;
}
public void display(){
for(int i=0;i<a.length;i++){
System.out.print(a[i]+"\t");
}
System.out.print("\n");
}
}
分享到:
相关推荐
一个数据结构作业,对刚刚学习希尔排序知识的同学有用,用C++做的
插入排序之希尔排序
希尔排序 希尔排序希尔排序希尔排序希尔排序希尔排序希尔排序希尔排序
(1) 完成5种常用内部排序算法的演示,5种排序算法为:快速排序,直接插入排序,选择排序,堆排序,希尔排序; (2) 待排序元素为整数,排序序列存储在数据文件中,要求排序元素不少于30个; (3) 演示程序开始,...
此希尔排序算法采用增量减半的方法来进行数据的排序,内有部分注释
合并排序,插入排序,希尔排序,快速排序,冒泡排序,桶排序的C语言实现,原创。
希尔排序法,最经典的排序法,但不是容易懂。包括希尔插入排序,希尔交换排序
希尔排序
排序算法: 1、插入排序 2、希尔排序 3、冒泡排序 4、快速排序 5、简单选择排序 6、堆排序
希尔排序的源代码; 平台:CentOS release 5.4 (Final) 编译器:GCC 4.3.2
用C++,模板写的 7中排序. 快速排序, 归并排序,插入排序,选择排序,起泡排序,堆排序,希尔排序
排序算法很多,下面有基数排序,堆排序,希尔排序,直接插入排序的代码和思路
数据结构 综合排序 冒泡排序 直接插入排序 快速排序 希尔排序,完整的代码,有每种排序时间的比较
希尔排序,比较高效的排序算法之一。这是一个例子,一个关于希尔排序的例子。
快速排序,希尔排序快速排序,希尔排序 快速排序,希尔排序
7大排序算法(快速排序,冒泡排序,选择排序,归并排序,插入排序,希尔排序,堆排序)实现源码
希尔排序,堆排序,快速排序,简单选择排序,插入排序,冒泡排序
希尔排序(程序).txt希尔排序(程序).txt希尔排序(程序).txt