天道酬勤系列之Python 希尔排序

1047521767

Python 希尔排序
& [! m8 `2 e( k6 p希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。
希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录"基本有序"时，再对全体记录进行依次直接插入排序。
                        
$ i$ ^& Y( g- @8 e2 J
$ p) x6 O' |; u" g) u  a, F      def shellSort(arr):
. a" i' s/ h; l9 p3 |1 \) v
    n = len(arr)
    gap = int(n/2)

    while gap > 0:

' f6 D' D" s% c+ [3 ]' S5 [) W        for i in range(gap,n):
$ q* _$ b) B* L
9 L2 J: S/ e6 G4 ?* ]5 r            temp = arr
- r6 K9 S1 ^4 }, h: u, Y  R9 k            j = i
            while  j >= gap and arr[j-gap] >temp:
                arr[j] = arr[j-gap]
                j -= gap
            arr[j] = temp
" r8 \- {& F  p# I) Q        gap = int(gap/2)
  K; w$ x; ?2 Q9 y; `
arr = [ 12, 34, 54, 2, 3]
5 r5 e) G/ p9 [9 U
  N- A+ {( O1 K& u% On = len(arr)
print ("排序前:")
0 |# C/ G' |6 d5 }  |) a/ ifor i in range(n):
    print(arr),

shellSort(arr)

2 ^/ ]; P5 q1 u% |: Q5 yprint ("\n排序后:")
5 c) c+ x7 G4 K. ]for i in range(n):
9 e' }/ a8 m0 H; M    print(arr),
/ s  x# |0 Q+ a* b/ _2 i0 w5 p) y
! _3 S2 ]- t5 k执行以上代码输出结果为：
1 A4 g( p( v. I% J4 z             排序前:12
34
  B+ P0 D! B' y/ n) L54
2
4 U* T. D& q8 e: U( {4 Z6 y: j0 g3

排序后:
) r, X, U+ p5 l4 w. \. @+ F2 p2
3
+ [2 O# H2 I+ G3 z7 n0 d, W12
6 b2 E) S. a3 p7 l& Y" v34
54
) f6 C& |. p( R# E2 K6 W. z
/ X# @, a+ M" C, T, L: L9 y- Y: n( x+ }
$ }) o" l8 {4 R8 f
- y* N7 O# U9 p9 ?
: s9 D8 w% f# D+ Y