[其他资源] 天道酬勤系列之Python 希尔排序

[复制链接]

字体大小: 正常放大

1047521767

1178 主题	15 听众	1万积分

TA的每日心情

	开心 2023-7-31 10:17

签到天数: 198 天

[LV.7]常住居民III

自我介绍: 数学中国浅夏

电梯直达

1^#

发表于 2021-10-28 16:05 |只看该作者 |倒序浏览

|招呼Ta 关注Ta

Python 希尔排序
希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。
希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录"基本有序"时，再对全体记录进行依次直接插入排序。


   def shellSort(arr):

n = len(arr)
gap = int(n/2)

while gap > 0:

      for i in range(gap,n):

         temp = arr 7 W( `* P8 B5 G9 p
         j = i ' l' o! e5 Z+ ~# w4 [  n
         while  j >= gap and arr[j-gap] >temp: . |, c& n* }/ h8 ]4 H7 s* h3 K( ?
            arr[j] = arr[j-gap] ) P$ q8 z( a$ |# ~! c( \* e
            j -= gap
& ]6 N+ ?! |) b3 o- D4 B          arr[j] = temp * V( h7 b7 D3 u* ?: q2 F
      gap = int(gap/2)6 ~! K7 t$ F. V* d3 `

8 B6 v' A: {; V# ~* q6 Rarr = [ 12, 34, 54, 2, 3] 7 i) Q5 o8 _0 t/ q0 R, C' b

; k+ v: [! ~1 zn = len(arr) 1 {1 A9 h7 l* r4 ?/ \4 h2 W
print ("排序前:") 7 k+ d: {+ j# i
for i in range(n): ; g" ~! ^0 }$ ~* i: X( X" o
print(arr), ( _6 ~' ~+ ~1 T8 m( k) G" s

. n7 g. i# w, R6 k/ h6 ZshellSort(arr) 6 [" b. G5 d. `0 x7 n! T
4 g; p. T: T! V& \
print ("\n排序后:") & B3 t) q( E1 T" z  b8 q1 Y
for i in range(n): % n  G; e* C& Q5 p2 [
print(arr),
" u, Q! P: V" C1 ?, [3 c+ g$ ?
0 Z5 J  c, F' u' T" \3 M7 Q& E* F执行以上代码输出结果为：
8 t4 s9 k; i2 _1 U% s          排序前:12
. {! Z# I* K% b34
$ E" |7 _& d$ \7 u1 u5 O3 K54
4 H5 w, R" z! U2
5 J* I9 Y1 W0 @- o7 D, L3
1 G5 G  }2 N; C4 e7 i, ~
# b, s, ^+ x3 K7 a7 s2 K排序后:" P0 n6 E; G6 T
2; @, ]6 D" ?3 v2 q4 S& ]2 k7 K
3; N9 [6 ~" z( N$ s
12
  S% Q. y% G! e8 `349 J6 H% A0 }* x" ?2 r5 B
54+ q6 b. e& G" y
, S' _/ H% t: b5 U: T; K
' H+ t) n4 v. L7 g

& f. @5 M' h5 h: ~2 Y
4 V9 W7 u  E+ ]: }. b" ~. u
7 r4 `- K. c% z% ?/ s