随笔-126  评论-247  文章-5  trackbacks-0

  
希尔排序属于插入类排序,是将整个无序列分割成若干小的子序列分别进行插入排序。

假如现有一数组: [49, 38, 65, 44, 81, 97, 76, 13, 27, 52, 30]

则可以以步长为5开始对数组进行排序。为了更加直观的表现这一过程,下面将该数组元素分成3行,并对每一列进行排序(直接插入排序)



C++ 实现代码片段

  
//希尔排序
//按自然顺序
void shellsort(Element array[], int len){
    
int i, index, key;
    
for(int step = len / 2; step > 0; step /= 2){  //每趟步长折半
        for(index = step; index < len; index++){
            key 
= array[index];
            
for(i = index - step; i >= 0 && array[i] > key; i -= step){
                array[i 
+ step] = array[i];
            }
            array[i 
+ step] = key;
        }
    }
}
  


Java 实现代码片段

       
//希尔排序,按自然顺序
public static void shellsort(int[] array){
    
int i, index, key;
    
for(int step = array.length / 2; step > 0; step /= 2){  //每趟步长折半
        
//直接插入排序
        for(index = step; index < array.length; index++){
            key 
= array[index];
            
for(i = index - step; i >= 0 && array[i] > key; i -= step){
                array[i 
+ step] = array[i];
            }
            array[i 
+ step] = key;
        }
    }
}
     


C++ 实现完整代码

   
/**
 * <!--
 * File   : insertsort.h
 * Author : fancy
 * Email  : fancydeepin@yeah.net
 * Date   : 2013-02-05
 * --!>
 
*/
#include 
<stdio.h>
#include 
<stdlib.h>
#define length(array) sizeof(array) / sizeof(array[0])
#define Element int
#define format "%d"

//希尔排序
//按自然顺序
void shellsort(Element array[], int len){
    
int i, index, key;
    
for(int step = len / 2; step > 0; step /= 2){  //每趟步长折半
        for(index = step; index < len; index++){
            key 
= array[index];
            
for(i = index - step; i >= 0 && array[i] > key; i -= step){
                array[i 
+ step] = array[i];
            }
            array[i 
+ step] = key;
        }
    }
}

//遍历数组
void visit(Element array[], int len){
    
for(int i = 0; i < len; i++){
        printf(format, array[i]);
    }
}
   

 

   
/**
 * <!--
 * File   : InsertSort.cpp
 * Author : fancy
 * Email  : fancydeepin@yeah.net
 * Date   : 2013-02-05
 * --!>
 
*/
#include 
"insertsort.h"

int main() {

    Element array[
8= {65318724};
    
int len = length(array);
    printf(
"\n排序前: ");
    visit(array, len);
    printf(
"\n希尔排序: ");
    shellsort(array, len);
    visit(array, len);
    
/**
     * 控制台输出结果:
     *
     * 排序前: 65318724
     * 希尔排序: 12345678
     
*/
    
return 0;

}
   




Java 实现完整代码

   
package net.yeah.fancydeepin.sort.insert;
/**
 * <!--
 * Author : fancy
 * Email  : fancydeepin@yeah.net
 * Date   : 2013-02-05
 * --!>
 
*/
public class Sort {

    
private Sort(){}
       
    
//希尔排序,按自然顺序
    public static void shellsort(int[] array){
        
int i, index, key;
        
for(int step = array.length / 2; step > 0; step /= 2){  //每趟步长折半
            
//直接插入排序
            for(index = step; index < array.length; index++){
                key 
= array[index];
                
for(i = index - step; i >= 0 && array[i] > key; i -= step){
                    array[i 
+ step] = array[i];
                }
                array[i 
+ step] = key;
            }
        }
    }
       
}
   

 

   
package test;
/**
 * <!--
 * Author : fancy
 * Email  : fancydeepin@yeah.net
 * Date   : 2013-02-05
 * --!>
 
*/
import net.yeah.fancydeepin.sort.insert.Sort;

public class Test {

    
public static void main(String[] args) {
        
        
int[] array = {65318724};
        Sort.shellsort(array);
        
for(int obj : array){
            System.out.print(obj);
        }
    }
}
   


 



  
posted on 2013-02-05 16:00 fancydeepin 阅读(1125) 评论(0)  编辑  收藏

只有注册用户登录后才能发表评论。


网站导航: