数学建模社区-数学中国
标题:
天道酬勤系列之Python 希尔排序
[打印本页]
作者:
1047521767
时间:
2021-10-28 16:05
标题:
天道酬勤系列之Python 希尔排序
Python 希尔排序
- i7 t3 Z, w7 v, n# a- s6 X. a
希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。
$ A( B2 V1 G: n( ]
希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录"基本有序"时，再对全体记录进行依次直接插入排序。
$ {, k( h2 \0 ^& H9 h, @
% T0 q( \2 R* e; H' h
5 ^, s" ^& v% h1 T2 T: B
def shellSort(arr):
9 @ a' r$ [8 W: k9 I. m% I8 ^
; L- _, O9 n5 ?3 b) s
n = len(arr)
. x: X7 x( J" o( @ x7 {# e
gap = int(n/2)
0 q% u! i9 \/ O C* O6 k% k L
8 Y& ~* B2 ~, x2 p! T9 p' r, V
while gap > 0:
. ?1 U! P" H! R. I! C% i( |& s
0 P$ ^4 o7 d+ p
for i in range(gap,n):
1 G3 e9 }! y$ f5 |4 I
) L- y4 \% K8 @
temp = arr
; O$ b* Q ]( i& ~6 D
j = i
" z# }5 f! y2 u Y/ `! n- P
while j >= gap and arr[j-gap] >temp:
% q d2 M ^; j* n4 S# v) f
arr[j] = arr[j-gap]
+ r9 k- i I+ \: M1 C+ e
j -= gap
7 z: G7 t% |7 J3 a# r4 E$ K
arr[j] = temp
3 ?3 r, C/ p1 C& B, K* l
gap = int(gap/2)
6 [+ l" P" y2 s! _5 [9 u* v F# g
" }2 C) s( \ k9 S7 w" O& A
arr = [ 12, 34, 54, 2, 3]
6 u6 W- r2 |5 J, B
' Q1 L. l, |1 v; c
n = len(arr)
' \# z# ~& w. d8 \7 ^* L
print ("排序前:")
/ x, i, i9 g# |6 G4 [
for i in range(n):
. B" I( g6 A) l6 J1 W# s, o9 s# H" H
print(arr
),
' I8 c5 ?8 U7 ]; g
. l$ V; E6 C8 S) _
shellSort(arr)
: i$ s; h) E4 G9 V, l- w
$ [6 B" `* t/ O' t
print ("\n排序后:")
1 R$ k8 N4 ?+ u4 X/ v* a% _9 x
for i in range(n):
" \1 J' v6 A1 k/ g6 T% X0 u3 f
print(arr
),
# I7 p+ B f; k* v! R
, `- ?3 r4 D: }, j
执行以上代码输出结果为：
) G& l/ R3 m% M, s' o0 c
排序前:12
5 K( F( T! E0 X5 E4 v
34
3 S; ?# v+ P o$ M( Q# B+ y$ D0 M
54
4 k6 X0 g0 g; y5 N
2
0 a# \+ d7 Z5 q7 t! n
3
$ [4 s- _2 E& E' f6 L& n/ A( t
, h# Q0 ?% F9 T
排序后:
4 U7 l4 F7 z$ P1 F
2
3 A6 C; y0 J- l& ~2 z' @
3
: U+ i1 X; i! R$ q( e. g2 V; i0 s
12
$ R, M% q" f0 L- U! t
34
3 X f6 l& H7 J9 d) s" X: i6 g5 ?4 ~
54
3 Z( a4 L: K6 \
- S% H9 K* I+ Z5 V9 ?9 ^4 v
7 \1 l5 p, @6 Z( \: g! R: }0 M
* n1 ]' p) z4 s6 C ]
- `9 ~$ Z4 k3 B4 S6 P# y5 V0 u
& Z7 O+ n+ O' z" G, o
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5
% T0 q( \2 R* e; H' h