久久一区国产,欧美日韩日日骚,亚洲欧洲美洲综合色网

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

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

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

Shell_sort.h
3

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

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

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

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

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

且比偶數(shù)位置的小。此時到最后一次遍歷前shell排序?qū)嶋H上什么也沒做。
9

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

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

,2^k-1

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

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

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

}
14

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

#ifndef SHELL_SORT_H
17

#define SHELL_SORT_H
18

#include "typedef.h"
20

void Shell_sort(T* a, int n)
22

{
23

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

#endif

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

只有注冊用戶登錄后才能發(fā)表評論。
【推薦】100%開源！大型工業(yè)跨平臺軟件C++源碼提供，建模，組態(tài)！

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

網(wǎng)站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

liyuxia713

導航

留言簿(3)

隨筆分類

收藏夾

隨筆檔案

閱讀排行榜

評論排行榜

常用鏈接

統(tǒng)計

Algorithms

C++

最新評論

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