希爾排序屬于插入類排序,是將整個無序列分割成若干小的子序列分別進行插入排序。
假如現有一數組: [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 閱讀(1162)
評論(0) 編輯 收藏