? 排序系列之（4）希爾排序及C語言實(shí)現(xiàn) 收藏
希爾排序(Shell Sort)也稱為遞減增量排序算法，是插入排序的一種高速而安定的改良版。因希爾(Donald L. Shell)于1959年提出而得名。各種實(shí)現(xiàn)在如何進(jìn)行遞減上有所不同。

希爾排序是基于插入排序的以下兩點(diǎn)性質(zhì)而提出改進(jìn)方法的：
插入排序在對(duì)幾乎已經(jīng)排好序的數(shù)據(jù)操作時(shí)， 效率高， 即可以達(dá)到線性排序的效率
但插入排序一般來說是低效的， 因?yàn)椴迦肱判蛎看沃荒軐?shù)據(jù)移動(dòng)一位

以下是其C語言實(shí)現(xiàn)
view plaincopy to clipboardprint?
#include "shellSort.h"??
#include "common.h"??
void shellSort(int a[],int len)??
{??
??? int step;??
??? int i,j;??
??? int temp;??
??? for(step=len/2; step>0;step/=2) //用來控制步長(zhǎng),最后遞減到1??
??? {??
??????? // i從第step開始排列，應(yīng)為插入排序的第一個(gè)元素??
??????? // 可以先不動(dòng)，從第二個(gè)開始排序??
??????? for(i=step;i<len;i++)??
??????? {??
??????????? temp = a[i];??
??????????? for(j=i-step;(j>=0 && temp < a[j]);j-=step)??
??????????? {??
??????????????? a[j+step] = a[j];??
??????????? }??
??????????? a[j+step] = temp; //將第一個(gè)位置填上??
??????? }??
??????? showArray(a,len);?????
??? }??
}??
void shellSortTest()??
{??
??? int a[] = {5, 18, 151, 138, 160, 63, 174, 169, 79, 200};??
??? int len = sizeof(a)/sizeof(int);??
??? printf("Init.../n");??
??? showArray(a,len);??
??? printf("Begin sorting.../n");??
??? shellSort(a,len);??
??? printf("After sorting.../n");??
??? showArray(a,len);??
}?
#include "shellSort.h"
#include "common.h"
void shellSort(int a[],int len)
{
?int step;
?int i,j;
?int temp;
?for(step=len/2; step>0;step/=2) //用來控制步長(zhǎng),最后遞減到1
?{
??// i從第step開始排列，應(yīng)為插入排序的第一個(gè)元素
??// 可以先不動(dòng)，從第二個(gè)開始排序
??for(i=step;i<len;i++)
??{
???temp = a[i];
???for(j=i-step;(j>=0 && temp < a[j]);j-=step)
???{
????a[j+step] = a[j];
???}
???a[j+step] = temp; //將第一個(gè)位置填上
??}
??showArray(a,len);?
?}
}
void shellSortTest()
{
?int a[] = {5, 18, 151, 138, 160, 63, 174, 169, 79, 200};
?int len = sizeof(a)/sizeof(int);
?printf("Init.../n");
?showArray(a,len);
?printf("Begin sorting.../n");
?shellSort(a,len);
?printf("After sorting.../n");
?showArray(a,len);
}

?

本文來自CSDN博客，轉(zhuǎn)載請(qǐng)標(biāo)明出處：http://blog.csdn.net/taizhoufox/archive/2010/10/22/5959437.aspx

總結(jié)

以上是生活随笔為你收集整理的希尔排序及C语言实现的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。