liyuxia713

蹣跚前行者

留言簿(3)

隨筆分類

收藏夾

隨筆檔案

閱讀排行榜

評論排行榜

常用鏈接

統計

隨筆 - 50
文章 - 0
評論 - 32
引用 - 0

Algorithms

lzmagic (rss)
正在更新數據結構中的一些經典算法
第四維空間
數據結構算法
極限定律
算法

C++

鷹之夢園
C++ Primer 學習筆記

基本排序算法及分析（三）：shell排序

shell排序是對直接插入方法的改進方法.

1

/*-------------------------------------------------------------------------------------
2

Shell_sort.h
3

shell排序是對直接插入方法的改進，它并不是對相鄰元素進行比較，而是對一定間隔的元素比較.
4

選擇增量序列的幾種方法：(為方便，本例采用第一種增量序列)
5

1. h[1]=size， h[k] = h[k-1]/2.
6

最壞運行時間為O(N^2).
7

最壞情形：數組長度為2^n,數組的偶數位置上同是一個數，奇數位置上也同是一個數，
8

且比偶數位置的小。此時到最后一次遍歷前shell排序實際上什么也沒做。
9

最后一次遍歷相當于直接插入方法。
10

2. Hibbard增量序列： h = 1,3,7,

,2^k-1

11

這個的區別于上的主要的特點是相鄰增量沒有公因子
12

最壞運行時間為O(n^{1.5});
13

3. Sedgewick增量序列：{1，5，19，41，109，

}
14

-------------------------------------------------------------------------------------*/
15

16

#ifndef SHELL_SORT_H
17

#define SHELL_SORT_H
18

19

#include "typedef.h"
20

21

void Shell_sort(T* a, int n)
22

{
23

24

for(int gap = n; gap > 0; gap = gap/2)
25

{
26

for(int i = 0; i != n; ++i)
27

{
28

T temp = a[i];
29

int j = i - gap;
30

for( ; j >= 0 && a[j] > temp; j = j-gap)
31

a[j+gap] = a[j];
32

a[j+gap] = temp;
33

}
34

}
35

}
36

37

#endif

posted on 2009-04-22 16:50 幸運草閱讀(907) 評論(0) 編輯收藏引用所屬分類: Algorithms

只有注冊用戶登錄后才能發表評論。


相關文章: 基本排序方法及分析（九）：Randomized-Quicksort快速排序的隨機化版本 Order Statistics 順序統計（找出第i小元素）基本排序方法及分析（八）：CoungtingSort 計數排序基本排序方法及分析（七）：HeapSort 堆排序同時求最大最小值基本排序算法及分析（六）：桶式排序基本排序算法及分析（五）：歸并排序基本排序算法及分析（四）：快速排序基本排序算法及分析（三）：shell排序基本排序算法及分析（二）：冒泡排序

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品