希尔排序属于插入类排序,是将整个无序列分割成若干小的子序列分别进行插入排序。
假如现有一数组: [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] = {6, 5, 3, 1, 8, 7, 2, 4};
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 = {6, 5, 3, 1, 8, 7, 2, 4};
Sort.shellsort(array);
for(int obj : array){
System.out.print(obj);
}
}
}
posted on 2013-02-05 16:00
fancydeepin 阅读(1140)
评论(0) 编辑 收藏