【零基础学Python】常用的Python 算法示例代码

admin

【零基础学Python】常用的Python 算法示例代码

, b$ x  H/ D& p+ t

Python 常见的算法可以分为多个类别，包括排序算法、搜索算法、图算法、动态规划、递归算法等。

一、排序算法
1.冒泡排序（Bubble Sort）：
原理：冒泡排序通过重复遍历待排序的列表，比较相邻的元素并交换它们的顺序。如果第一个元素比第二个大，就交换它们。这个过程会重复进行，直到没有交换发生，表示列表已经排序完成。
! U, t4 R3 j8 v. k" O+ l8 e% a
时间复杂度：最坏和平均情况下是O(n²)，最好情况下是O(n)。
' c5 z, C: U& B) @( `, e" R
$ W- O. `  r! a* z+ ]0 m% r实现：

# coding: utf-8
# `7 _- J$ U+ {% B* b) s4 M  |3 Ddef bubble_sort(arr):
) v+ y8 y' P; f3 G/ n; B    n = len(arr)
    for nu in range(n):
2 W. M  y0 m5 e, K. E        swapped = False
        for nu2 in range(0,n-nu-1):
            if arr[nu2] > arr[nu2+1]:
                arr[nu2],arr[nu2+1] = arr[nu2+1],arr[nu2]  #"""交换"""
" L/ ?5 [* H, p" o# J                swapped = True
! U: O3 [4 _+ Y7 i4 x        if not swapped:
            break   ##如果没有交换，提前结束
) m9 {  x1 C* X0 i0 a  ~. G+ |: Z. a    return arr

/ {- ]/ x' v- g1 P

$ b: g% s8 V' G$ v示例：
print(bubble_sort([23,65,28,12,29,10,70]))结果：
[10, 12, 23, 28, 29, 65, 70]
2 v  x9 L+ a0 }6 b) H( R
" P. {: O( u6 y4 C/ z1 d- U
3 B  Y2 n/ c; {8 F

$ I/ P/ J5 ], @1 ^7 k* [

2.选择排序（Selection Sort）：
原理：选择排序每次从未排序的部分中选择最小（或最大）元素，将其放到已排序部分的末尾。重复这个过程，直到所有元素都被排序。
5 F/ A8 n- `& b2 E9 q; B4 c' q* f
. y8 t1 C/ v0 @& u/ v时间复杂度：O(n²)。

实现：
4 |! T& T$ b9 F#coding: utf-8
/ m! u0 H+ P* o) t. {: ?+ f, Cdef select_sort(arr):
    number1 = len(arr)
    for nem1 in range(number1):
        min_idx = nem1
        for number2 in range(nem1+1,number1):
            if arr[number2] <arr[min_idx]:
                min_idx = number2
                arr[nem1],arr[min_idx] = arr[min_idx],arr[nem1]  ##交换
return arr


; }1 r, D& W* K- S$ {! r; ?. z# 示例
print(select_sort([23,19,90,11,29,22]))
4 F& g% d$ w  p2 `5 v( c) ^5 b结果：[11, 22, 19, 29, 23, 90]
1 S5 h2 H( j: H
' B- R- C; `# A" ?5 u
3.快速排序（Quick Sort）：
7 H: x1 d. h, ?原理：快速排序通过选择一个“基准”元素，将数组分为两部分：小于基准的元素和大于基准的元素。然后递归地对这两部分进行排序。

时间复杂度：平均情况是O(n log n)，最坏情况是O(n²)（当选择的基准不理想时）。
6 m* Z0 s  b' v/ j
实现：
8 B1 Z: i9 a% D) g# t

+ o$ m% P; B+ J. n  @; _+ `4 Hdef quick_sort(arr):
    if len(arr) <= 1:
1 I1 i$ c' Y6 p        return arr
) f  C; F" \7 U# {8 s    pivot = arr[len(arr) // 2]  ##选择基数
) f3 Z9 c- b" C    left = [a for a in arr if a < pivot]
9 M1 |  S. J! _2 ^: C/ P- M    middle = [a for a in arr if a == pivot]
2 F1 @4 x5 J: O- c* m& j& g    right = [a for a in arr if a > pivot]
6 C1 U* t: q' i0 i" |; u    return quick_sort(left) + middle + quick_sort(right)
4 E- f' ~6 h: Y$ M


# 示例
print(quick_sort([2,5,7,11,1,3,1]))
5 S0 n" `4 Y7 O! B8 O
结果：
[1, 1, 2, 3, 6, 8, 10]

4.插入排序（Insertion Sort）：
2 @. `& V2 h/ v原理：插入排序将数组分为已排序和未排序两部分。每次从未排序部分取出一个元素，插入到已排序部分的合适位置。

2 c) x! o* r/ R7 K5 i, t; L9 |时间复杂度：平均和最坏情况是O(n²)，最好情况是O(n)。
6 P1 M/ E. U* x. X& T. T
实现：
1 e) @- m3 W  v" M
def insertin_sort(arr):
+ A: z4 Y& f- W; J8 x    n = len(arr)
; d1 w9 M# \4 l2 W* F! }. ?    for a in range(1,n):
         key = arr[a]
         b = a -1
         while b>=0 and key < arr[b]:
            arr[b+1] = arr[b]    ##移动元素
b -= 1
( K3 M* u/ S5 r, [; ?. {            arr[b +1] = key    ####插入值
return arr
% m% A; F  ~7 Q

# 示例
print(insertin_sort([11,9,14,4,7]))
+ Y/ j# }. y3 x) ?! Nprint(insertin_sort([12, 11, 13, 5, 6]))


结果：
; K; H7 }% e% z9 I
[4, 7, 9, 11, 14]
[5, 6, 11, 12, 13]

+ g: C7 k$ ^' y# ^7 j2 Z% l
0 l+ _% a5 l( p0 \  V8 a5. 归并排序（Merge Sort）
. y5 e0 A4 y/ D/ x2 A原理：归并排序采用分治法，将数组分成两个子数组，分别对这两个子数组进行排序，然后将已排序的子数组合并成一个最终的排序数组。

6 p/ K$ X& J. X/ ~% O时间复杂度：O(n log n)。
3 [/ F7 R4 ^! Q) C$ [5 \% o
实现：

& w# d& B: I, W0 K+ Q1 o4 |  [#归并排序
def merge_sort(arr):
  w; a; `! ^+ X  N3 g3 \/ N( C    #如果数组长度小于等于1，则直接返回
( S! t$ ^$ v- N8 ^2 }if len(arr)<=1:
      return arr
# ^3 f+ S" B) x' ^. x' q
    ##找中间索引
mid = len(arr)//2

$ I/ R; g8 X1 U# E& m) ]    # 递归地对左右子数组进行排序
6 Z4 y4 @4 a3 p$ q7 `3 t6 Bleft = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
+ V& j( a; @. w- g) x1 s
1 e+ j& c# U4 o6 s8 y/ R    #合并已排序的子数组
return merage(left,right)
7 S9 L  q: l. D" M3 i8 B6 ]
def merage(left,right):
' ^7 a4 v, M* @" h3 F* W. l    sorted_array = []
    a = b = 0
0 r! S4 l* o4 O% [2 i1 d8 e    ##合并两个已排序的子数组
while a < len(left) and b < len(right):
2 ]4 ]+ _! x( }: b! Q, v        if left[a]< right[b]:
) i0 g; F9 ?- Q  @          sorted_array.append(left[a])
9 r6 `& v. z2 L; G          a += 1
/ {( ^) q5 I9 F% x1 w. q, f1 N        else:
          sorted_array.append(right[b])
          b += 1

    while a <len(left):
) j* w- a8 w8 ]% B$ }4 i. E$ w        sorted_array.append(left[a])
        a += 1
    while b<len(right):
        sorted_array.append(right[b])
        b += 1

- e1 S" a/ {) a# \7 z6 L
' b4 b; v9 Y4 t) U0 v' e    return sorted_array
+ l* L& J3 u3 F; i5 r: X$ v
if __name__ == "__main__":
" A1 x+ [* r1 g1 x) C. m  arr = [37,26,42,2,8,81,9]
  sorted_arr = merge_sort(arr)

% Q. d: ^2 q; L9 k  print("排序后的数组:",sorted_arr)
+ e5 E) ^+ x; B# t

结果：
! X0 s7 d3 F" D% T& Y$ k1 K排序后的数组: [2, 8, 9, 26, 37, 42, 81]

+ R& {% b7 I. v
: p" V- `7 j) Y; I二、搜索算法
1. 线性搜索（Linear Search）
+ N2 ]% ?- Z: c$ S  j# Q) @线性搜索是一种简单的搜索算法，它通过逐个检查每个元素来查找目标值。
% P2 x! @) b& t5 k, A- d# {
+ i6 M8 h; z0 Z% I: t
4 f7 ?& w- A+ i! Odef line_search(arr,target):
0 O( B+ U! k) y4 p2 W+ {& Q    for index,value in enumerate(arr):
        if value == target:
            return index   ###换回目标值的索引
return -1    ###如果未找到值，则返回-1
#示例
2 w, d/ S* Y  g/ Darr = [2,5,1,6,9]
target = 9
result = line_search(arr,target)
print(f"目标值 {target}的索引是：{result}")
% d: L' N) t" X. w
/ p/ P5 P, j2 A, b$ Y
结果：

目标值 9的索引是：4
$ d7 {* A1 ?% J+ i+ L
- E8 |/ G& ]8 V6 |. [$ _" F* Y2. 二分搜索（Binary Search）
2 ~: h) v' b  }' a二分搜索是一种高效的搜索算法，适用于已排序的数组。它通过将搜索范围减半来快速定位目标值。
! I. L; f& E# x- Y
2 V" Q# u3 V+ q4 \3 Qdef binary_search(arr,target):
    left,right=0,len(arr)-1
, J2 e4 t" v( D/ M& U    while left <= right:
        mid = left + (right-left)//2
        if arr[mid]==target:
; k) m. w) ^: d  K8 R2 r            return mid   ###返回目标值的索引
        elif arr[mid]<target:
            left = mid +1
        else:
            right = mid -1
# }+ D3 e) _: F3 Q    return -1    ##如果未找到，返回-1
8 v2 t6 y6 N7 F& W
##示例
( u3 _  G) o" Q& yarr = [11,12,13,14,15,16,17,18,19]
3 }1 K# y, i% p+ Itarget = 15
* i5 e/ N; \0 i' b0 b5 Fresult = binary_search(arr,target)
print(f"目标值 {target}的索引是：{result}")
, Z& t1 t! L' m% m
  b* O: ^8 }, L7 F结果：
. V8 s/ ^  s: d  c7 D, J& p目标值 15的索引是：4
! J  \1 s) Z, X! ]9 Z
% ^* d. t! h- T7 H+ K3. 深度优先搜索（Depth-First Search, DFS）
( H$ p' D) h' l5 W深度优先搜索通常用于树或图的遍历。它会尽可能深地搜索树的分支。
" W6 [9 k% T* N0 ^
9 ~; R6 R; D% h9 O! kdef dfs(graph, node, visited=None):
$ X3 W1 n2 H- ]    if visited is None:
3 O6 X, e/ R  Q2 }6 f        visited = set()
    visited.add(node)
    print(node)
. f  F* t, Z, h% z. m" p; m1 D    for neighbor in graph[node]:
  w7 N& |  }' W* {  X; T8 E6 x        if neighbor not in visited:
/ V: y5 ]! h1 N. Y1 I            dfs(graph, neighbor, visited)

4 G+ ~& i: A# {) U3 m; L# 示例
0 s: N" T* G! f( f8 m+ agraph = {
    'A': ['B', 'C'],
1 S* T# h4 B5 A8 |; J' i    'B': ['D', 'E'],
* y$ o/ g5 k5 l, G7 ]    'C': ['F'],
    'D': [],
    'E': ['F'],
! s5 c6 D8 D# _  u- P" I8 w    'F': []
}
* K# w: ~/ T8 I+ C0 I# Ydfs(graph, 'A')
4. 广度优先搜索（Breadth-First Search, BFS）
广度优先搜索也是用于树或图的遍历，它逐层访问节点。

: o( }* E& g: q" H7 @$ ~: Rfrom collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
   
, X+ M/ H1 a% T- L    while queue:
9 D# X: T$ _) j8 n5 z        node = queue.popleft()
* F  [/ @4 H+ ?! _' c2 y% N$ A# h& r2 `$ B        if node not in visited:
7 T5 Y& u+ g3 N( k            visited.add(node)
8 L% G  S% u: Z4 P9 Y- M            print(node)
            queue.extend(neighbor for neighbor in graph[node] if neighbor not in visited)
/ w+ _$ i: ^  X% j5 O: j4 z
' j( T9 b( E$ B# 示例
graph = {
    'A': ['B', 'C'],
3 N4 [& _: ^' c$ f    'B': ['D', 'E'],
9 |7 G9 C! }2 r. S    'C': ['F'],
0 ]6 M! q5 l. J2 g5 p    'D': [],
0 E) [$ \3 l. Z" J3 V, C: J3 ~# B, f    'E': ['F'],
    'F': []
$ Q1 B, a5 C( |9 l  U% K2 `0 O}
. B( f, A( C3 O9 `% Q! z+ s$ k" ybfs(graph, 'A')
三、动态规划
斐波那契数列（Fibonacci Sequence）：
def fibonacci(n):
    if n <= 1:
        return n
    fib = [0, 1]
    for i in range(2, n + 1):
4 l/ l2 A( J0 ^# w( P5 N) z        fib.append(fib[i - 1] + fib[i - 2])
, A; a6 F. y, z    return fib[n]
( O  e! v! D& ]  i
2 \* ]8 m7 x8 `  S$ ~# 示例
8 N3 R. |3 Y0 _/ T7 zprint(fibonacci(10))  # 输出: 55
" B# ]! c6 L; w* [: T+ k四、 图算法
深度优先搜索（DFS）：

def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
7 ~4 m( n; q4 O8 O    for neighbor in graph[start]:
2 u: v  y+ r+ Q4 u2 k        if neighbor not in visited:
            dfs(graph, neighbor, visited)
4 X, h# H2 V- }8 R; {% U' N7 \6 ^0 x    return visited
9 q3 L3 F& J; r3 X
# 示例
graph = {
8 y: J/ ]" A8 ]/ W9 M7 f    'A': ['B', 'C'],
7 Z$ g* j$ R: L    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
* m: {; f/ B' A7 \1 Q4 Z    'D': ['B'],
& b, c8 E# b5 `. E    'E': ['B', 'F'],
) e9 V( ]+ {! f) a6 Q  V& s. S    'F': ['C', 'E']
: A5 N. v+ h) F3 X+ w& S7 \+ b}
, f, i2 z2 f/ g8 T0 k0 i% }print(dfs(graph, 'A'))  # 输出: {'A', 'B', 'D', 'E', 'C', 'F'}
五、递归算法
8 p0 F/ @8 e1 k1 O2 m. v7 ^+ B4 x2 v" M计算阶乘（Factorial）
/ f* A8 [% X( V; M! F2 k9 ~def factorial(n):
9 Y2 j; T/ E, p3 D! K0 h6 D    if n == 0:
4 J9 t  r  Q2 ~+ ]7 V! _; m& W        return 1
    else:
        return n * factorial(n - 1)
* ]- ?4 I6 n3 m: l- z) I
# 示例
& E; _3 ]+ a0 ]% j7 ]. zprint(factorial(5))  # 输出: 120
六、 回溯算法
解决八皇后问题：
def solve_n_queens(n):
$ u6 }; a! ?2 T( h    def is_safe(board, row, col):
        # 检查当前列是否安全
0 T2 @2 {% n, b1 a- Q        for i in range(row):
7 @" B; `' Q2 ~5 t8 \            if board == col or \
               board - i == col - row or \
+ C. f5 p1 F6 G0 ^! e/ ?; K               board + i == col + row:
                return False
, g( u) w/ Q. \4 c( L/ g0 k        return True

5 \% M7 l& i: r" h3 S! G    def solve(board, row):
        if row == n:
            result.append(board[:])
3 h- ]; D4 [' H  O1 A8 ]            return
        for col in range(n):
            if is_safe(board, row, col):
                board[row] = col
1 Z4 e. v3 l/ m1 ^4 h/ _$ }                solve(board, row + 1)
                # 在回溯时不需要重置，因为我们直接覆盖
( L) v" p* g: c9 z* F) z8 Q
    result = []
    board = [-1] * n  # 初始化棋盘
    solve(board, 0)
    return result
! _$ c" m/ r# {1 d4 D
def print_solutions(solutions):
$ _0 `1 Y( d6 a  X7 R    for board in solutions:
  ]+ n$ F9 s4 k9 ?1 J        for row in board:
% t; x5 q. \0 u( g+ ^  Z            line = ['.'] * len(board)
            line[row] = 'Q'
4 u1 e* j$ G/ n9 e            print(' '.join(line))
) C# f8 B9 h% R5 L        print()
: }7 u6 e7 l" x+ r+ ~' K3 g
if __name__ == "__main__":
    n = 8  # 八皇后
    solutions = solve_n_queens(n)
    print(f"找到 {len(solutions)} 种解决方案:")
    print_solutions(solutions)
! U& i( {! X* {* i- c3 o+ A: sAI写代码
- |$ K. J' x3 w- }



0 _+ v5 o3 V- @6 r- P5 W( m
7 J: z; U; [2 R3 q' s
' M9 b5 o0 u$ w1 l% F) y

admin

常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括：
9 ]5 L$ U' W+ _, w) W
/ D' {! _/ N6 E% t! e: _图片

# N: U! C) r2 |" A
( u7 E- j3 _' \+ a& P* n图片
关于时间复杂度
3 J: R. V5 l  K
* I  O& _8 H; G" D& ^图片


平方阶 (O(n2)) 排序 各类简单排序：直接插入、直接选择和冒泡排序。
线性对数阶 (O(nlog2n)) 排序 快速排序、堆排序和归并排序；
O(n1+§)) 排序，§ 是介于 0 和 1 之间的常数。希尔排序
- q( D: P* w. D0 E线性阶 (O(n)) 排序 基数排序，此外还有桶、箱排序。

+ @, C& \: j8 c6 @* k9 ?  [
3 K' I( {: N+ ?' x; `- `/ a, X图片
$ A7 G% I3 Y. l7 d& z; s' _8 N关于稳定性

图片
$ S2 q% w1 x0 o/ J
  G$ e. a, t! {5 [
+ z5 G- h3 R$ M9 ?" c& B0 ~- _( O排序后 2 个相等键值的顺序和排序之前它们的顺序相同
: l  K* R, O% z0 X8 s6 z+ t; i稳定的排序算法：冒泡排序、插入排序、归并排序和基数排序。
不是稳定的排序算法：选择排序、快速排序、希尔排序、堆排序。
* _6 S/ Q8 V% N6 ]- V. x' r" t
: n9 d& b$ M, t3 [2 T, G) i
% `1 m( m& W, C! Y* J图片
6 e4 ]1 F* x2 c6 ?/ v5 u* h1 O; g名词解释
+ x1 z+ H* K! t
. E: k9 q* I6 F' ?" i图片

; d2 t* Z3 N: n0 Z: A+ z
n：数据规模
& v  f  N5 F: a8 j. P# r( P# Ck：“桶”的个数
In-place：占用常数内存，不占用额外内存
Out-place：占用额外内存


% i& k, ^8 d6 G$ o图片
1、冒泡排序

* y  k. ~; l, m! H$ J  O7 L% }图片
- K9 q3 i' H- }$ m6 w" `' H& Y
7 b) R& I7 y/ l: M: h
! A3 B' Z! K( ]( A; L/ X- Z冒泡排序（Bubble Sort）也是一种简单直观的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
% B8 P5 r7 G; }/ Y
作为最简单的排序算法之一，冒泡排序给我的感觉就像 Abandon 在单词书里出现的感觉一样，每次都在第一页第一位，所以最熟悉。冒泡排序还有一种优化算法，就是立一个 flag，当在一趟序列遍历中元素没有发生交换，则证明该序列已经有序。但这种改进对于提升性能来说并没有什么太大作用。

（1）算法步骤
: ?2 ~; ?: d# F, _比较相邻的元素。如果第一个比第二个大，就交换他们两个。
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
（2）动图演示
1 x6 ~0 D8 ?7 E  F! g8 k6 s4 Z图片
/ }( F4 T" _7 y5 A: a1 a6 J! V（3）Python 代码
; Q: w1 M! ^% ^  Z+ Kdef bubbleSort(arr):
' Z$ g4 M- U; a0 T6 M  D4 p    for i in range(1, len(arr)):
        for j in range(0, len(arr)-i):
            if arr[j] > arr[j+1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr
6 ^5 t$ Z/ Y6 D! L
5 R& R& N$ i$ ~: j+ i, N. v  b
0 A2 E8 B" i) r9 |# G图片
2、选择排序
( T5 q* z2 T9 n% i/ x7 Q
图片
% @- F- H8 R) ?# Q' X1 {5 D- ~" n选择排序是一种简单直观的排序算法，无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。
7 y* {, Z% E  c/ |  N
1 a7 ^: D. e* I（1）算法步骤
首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
重复第二步，直到所有元素均排序完毕。
- m1 D1 R3 N' `) D/ e（2）动图演示
图片
; L3 `1 f! s8 H, o; G1 `+ E/ O（3）Python 代码
- ]- u0 t% Y+ `  Q) a, W; u# mdef selectionSort(arr):
5 s) y9 W; T* X5 Q    for i in range(len(arr) - 1):
; T0 ?( d( J4 [* r+ g0 K        # 记录最小数的索引
        minIndex = i
  _. T8 x* P$ H) I) c        for j in range(i + 1, len(arr)):
' i0 ^, B3 p5 f+ a9 w, F            if arr[j] < arr[minIndex]:
+ `$ I7 H' G2 d' u7 t4 E) E                minIndex = j
        # i 不是最小数时，将 i 和最小数进行交换
        if i != minIndex:
            arr[i], arr[minIndex] = arr[minIndex], arr[i]
) ]" K0 J5 A. g8 x  ^: @    return arr

$ b( U$ R8 j. P
4 s7 i) \+ [& S* v! S图片
9 }0 n5 j# M4 c# M0 w5 [3、插入排序

图片
7 p! v) M& n2 B0 J& n" Z. {插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴，但它的原理应该是最容易理解的了，因为只要打过扑克牌的人都应该能够秒懂。插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

  n; `6 ^7 {2 Y: `2 f" y1 E. Z插入排序和冒泡排序一样，也有一种优化算法，叫做拆半插入。
4 N% s1 B; D2 G) F$ \) U
（1）算法步骤
$ K1 I7 A. C, B3 Q% g) H! p) i& ]将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
5 }5 M& ?& P5 o
" n- s9 m2 X+ c' y# ]1 K从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）

（2）动图演示
图片
1 `  o' o9 j- j! `. R（3）Python 代码
9 b8 X. b; t9 M% q8 g9 S" L2 cdef insertionSort(arr):
# L6 A* ]# i9 b- g9 V  S) P( \    for i in range(len(arr)):
: c7 S, j! O4 [. Z7 U        preIndex = i-1
        current = arr[i]
        while preIndex >= 0 and arr[preIndex] > current:
3 O. m" ^) c6 Q* x+ y# G# M  S. g1 t            arr[preIndex+1] = arr[preIndex]
! p8 c7 e/ W' p6 ]6 v            preIndex-=1
        arr[preIndex+1] = current
5 D3 @' a/ h7 a% J" F# m  \    return arr
4 J7 ~2 [; Z9 V* h& p

" R, k6 L0 n+ }, I* R4 p, b图片
4、希尔排序
3 |; ^: \, T7 `! |+ G& a
图片
2 |2 T% |2 h/ J$ t  C$ Z希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。
) W& Z. A2 _) J
希尔排序是基于插入排序的以下两点性质而提出改进方法的：
3 }: \3 i+ c. X; \- E8 U
插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；
但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位；
* r  T( D8 j0 N. n8 t希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。
$ L) V0 L! m$ }+ s  [" O4 v8 [/ l
4 u' q3 Q9 U) C' i- ^5 F) u（1）算法步骤
选择一个增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；
) B/ U) S9 Q! z# d9 n& L+ |7 V按增量序列个数 k，对序列进行 k 趟排序；
- t8 X+ w/ p! k& `0 U& n" b每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
* F  C, u5 T! R) N（2）Python 代码
def shellSort(arr):
" m$ M/ i8 ^# K8 @- M5 q! b/ }    import math
/ w9 c. g8 w3 y. |2 u* ?% G% e$ s6 O    gap=1
    while(gap < len(arr)/3):
        gap = gap*3+1
( i4 Q% R5 H3 N7 ?. H0 v5 m    while gap > 0:
        for i in range(gap,len(arr)):
            temp = arr[i]
4 Q0 n5 u4 w- F4 v! |            j = i-gap
: ?: ?8 d  z; V. w' v9 |1 H            while j >=0 and arr[j] > temp:
0 q, a3 ]/ @: u! a5 T& i" P; ~* E                arr[j+gap]=arr[j]
                j-=gap
% o8 H% e& E1 U& @0 _0 }. x% G9 {            arr[j+gap] = temp
/ {9 U+ ~( W/ _9 n        gap = math.floor(gap/3)
, Y3 O3 p" [$ O7 J* T    return arr
- Q0 s0 d; r4 I6 b2 q+ W: O

图片
7 K! u# U* `' X% j  o5、归并排序

0 s' y7 I7 N/ b( _( U" H' x图片
! |7 ?9 [; j! B: g, E归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
! A- B# z  Z0 O. d1 {
3 m# t& J/ T- H; H. o) H作为一种典型的分而治之思想的算法应用，归并排序的实现由两种方法：

; }3 ]8 l2 z* @) q1 L2 C( W3 `5 \/ w自上而下的递归（所有递归的方法都可以用迭代重写，所以就有了第 2 种方法）；
" Y1 W# E+ K5 d% s- e7 [自下而上的迭代；
* G5 x- J5 x( Z9 G和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是 O(nlogn) 的时间复杂度。代价是需要额外的内存空间。

7 }" c+ y( z! y& O' d（1）算法步骤
7 |4 e. O+ h" P2 q: Z7 B申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
7 R! w6 A0 P8 t, Y" ]( x
" L+ p# T: _$ f' _9 ^- ^' K设定两个指针，最初位置分别为两个已经排序序列的起始位置；

比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
% |1 b2 @4 {# v& r
' G0 {4 l4 k1 _; c- w3 w重复步骤 3 直到某一指针达到序列尾；
2 k% _4 D+ n% v* A* E7 ~1 J
* ]; k0 V: y4 D; G, Y$ S将另一序列剩下的所有元素直接复制到合并序列尾。

: ?& U0 T0 p# u5 T6 @0 U2 M（2）动图演示
图片
（3）Python 代码
def mergeSort(arr):
    import math
    if(len(arr)<2):
        return arr
8 G" W- s9 P& A- ]( _    middle = math.floor(len(arr)/2)
    left, right = arr[0:middle], arr[middle:]
    return merge(mergeSort(left), mergeSort(right))
5 l1 E9 I3 \. r5 L2 L
def merge(left,right):
$ E* Q+ G- h5 o    result = []
  g& ?# c: U9 d    while left and right:
        if left[0] <= right[0]:
& P6 w3 S* w) m% _. z, L            result.append(left.pop(0));
        else:
. P5 u# k2 V0 ]            result.append(right.pop(0));
$ h& O, U! x1 Z  e' c" K* H( g; O2 y1 W    while left:
6 p  A7 R  _0 R# t/ s  Z: Y+ h        result.append(left.pop(0));
$ ?! g+ {. F' q! [3 w    while right:
        result.append(right.pop(0));
    return result

8 X8 r7 i+ U: M& u, Q
/ m$ W5 f  s& M% t, G图片
" g( J& T  s! l+ ^8 o) h7 Z6、快速排序

( i0 @5 v  x# g' D图片
快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 n 个项目要 Ο(nlogn) 次比较。在最坏状况下则需要 Ο(n2) 次比较，但这种状况并不常见。事实上，快速排序通常明显比其他 Ο(nlogn) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。

' x2 ?9 ^* W  k快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。

  |: |8 x9 v& [/ o, i7 T' r; E快速排序又是一种分而治之思想在排序算法上的典型应用。本质上来看，快速排序应该算是在冒泡排序基础上的递归分治法。
7 _1 r6 n' F& n' j
2 O8 g* K/ T  n6 G8 R, ]+ O快速排序的名字起的是简单粗暴，因为一听到这个名字你就知道它存在的意义，就是快，而且效率高！它是处理大数据最快的排序算法之一了。虽然 Worst Case 的时间复杂度达到了 O(n²)，但是人家就是优秀，在大多数情况下都比平均时间复杂度为 O(n logn) 的排序算法表现要更好，可是这是为什么呢，我也不知道。好在我的强迫症又犯了，查了 N 多资料终于在《算法艺术与信息学竞赛》上找到了满意的答案：

1 {$ w. A0 N( I' L2 H, C$ K& J快速排序的最坏运行情况是 O(n²)，比如说顺序数列的快排。但它的平摊期望时间是 O(nlogn)，且 O(nlogn) 记号中隐含的常数因子很小，比复杂度稳定等于 O(nlogn) 的归并排序要小很多。所以，对绝大多数顺序性较弱的随机数列而言，快速排序总是优于归并排序。
8 B# R1 a: _  E5 e* h0 o
0 G: z* E* g0 E' |& }（1）算法步骤
① 从数列中挑出一个元素，称为 “基准”（pivot）;

② 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
+ z. j# W1 i& h
③ 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；

' i9 Y2 |) L8 c$ ]3 c递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递归下去，但是这个算法总会退出，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。
' z! H% @/ ^8 Y
（2）动图演示
9 I* g7 p1 c. F) E* q' H$ L$ d图片
6 i; ]8 ^5 y- b4 J5 M7 g（3）Python 代码
2 u3 B6 U2 f/ S- v: ]% e+ Mdef quickSort(arr, left=None, right=None):
    left = 0 if not isinstance(left,(int, float)) else left
    right = len(arr)-1 if not isinstance(right,(int, float)) else right
& D( L" E: V; K0 F' w0 o    if left < right:
        partitionIndex = partition(arr, left, right)
8 k; w% [% M" L) ~        quickSort(arr, left, partitionIndex-1)
  _4 x$ d8 s# {        quickSort(arr, partitionIndex+1, right)
    return arr
4 ?' i4 s! ~2 \5 s: C( V  V6 V: }, J
def partition(arr, left, right):
    pivot = left
; L' F  x) ^+ g5 Z! {6 l2 t    index = pivot+1
. Y# b$ v4 p4 P6 N    i = index
    while  i <= right:
& X- a7 I5 N2 m* t        if arr[i] < arr[pivot]:
" T8 `$ U, h; w( M( L            swap(arr, i, index)
, D$ @  I7 ]- E4 B/ T            index+=1
+ a, s! [$ \! U        i+=1
    swap(arr,pivot,index-1)
, h5 e- @' R5 I5 E0 r    return index-1
8 }! g: o7 q+ U& j8 ^0 ?1 _1 X
def swap(arr, i, j):
    arr[i], arr[j] = arr[j], arr[i]
& t/ e! A: _5 B
1 c1 ~( w3 P4 a5 b
图片
7、堆排序
8 ~/ E+ n- y- f4 f# t7 _! J
图片
堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法：
9 \6 b1 ~4 L. t' `8 J
3 y, F6 J4 k/ x* b- U: g大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；
; W6 D/ }* z3 R+ u, W7 C7 q2 ^( G小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；
堆排序的平均时间复杂度为 Ο(nlogn)。

3 Y" E  k( m4 R" a（1）算法步骤
创建一个堆 H[0……n-1]；
% z, H8 c2 |; @1 j% F1 }% p8 V把堆首（最大值）和堆尾互换；
# u# T& ~$ z9 a; }+ E把堆的尺寸缩小 1，并调用 shift_down(0)，目的是把新的数组顶端数据调整到相应位置；
重复步骤 2，直到堆的尺寸为 1。
' N% s+ ^$ V% F; Y3 i（2）动图演示
图片
（3）Python 代码
$ e* c: M# \9 _0 fdef buildMaxHeap(arr):
    import math
    for i in range(math.floor(len(arr)/2),-1,-1):
0 n) H- \4 }! A8 g        heapify(arr,i)
$ H0 `. b- d* ~4 o
def heapify(arr, i):
; `/ A. y1 h2 R  E+ }" @; ]    left = 2*i+1
    right = 2*i+2
    largest = i
+ z+ h, n: U, r2 ^- l0 r5 i    if left < arrLen and arr[left] > arr[largest]:
        largest = left
    if right < arrLen and arr[right] > arr[largest]:
9 R: a$ b8 V8 G; u0 A        largest = right

/ ^1 T9 r; ?* b    if largest != i:
% U. A3 o/ @3 y1 C  Z6 M        swap(arr, i, largest)
, m3 S0 X2 t" {3 c* z        heapify(arr, largest)

! H0 X: \9 d$ jdef swap(arr, i, j):
    arr[i], arr[j] = arr[j], arr[i]

def heapSort(arr):
    global arrLen
    arrLen = len(arr)
* K# P; W( h+ w# ~    buildMaxHeap(arr)
    for i in range(len(arr)-1,0,-1):
: t" u  u3 }1 J& p        swap(arr,0,i)
, {* i0 e  h0 `" d4 [7 j: P! M: s        arrLen -=1
3 B1 P9 }; y: a        heapify(arr, 0)
+ d7 F8 k) {6 Z; l    return arr

- a9 C7 P" D- T1 I/ P* `
1 B7 ~7 e, y  p: f1 ]0 i图片
8、计数排序

图片
  O3 K; ]" _# g9 N- m9 c1 p计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

（1）动图演示
图片
（2）Python 代码
def countingSort(arr, maxValue):
    bucketLen = maxValue+1
3 S: I) C/ p, n+ \7 n  e& u    bucket = [0]*bucketLen
, d- I& h! J8 K( @) [# d6 e3 j    sortedIndex =0
1 D# C) Q* a, D3 S, L  b, D: e    arrLen = len(arr)
    for i in range(arrLen):
        if not bucket[arr[i]]:
# d' }1 _  p% J% F            bucket[arr[i]]=0
, I$ {) D. o. T# d        bucket[arr[i]]+=1
4 [& M( p, e# |& q7 [8 `    for j in range(bucketLen):
; f9 Y0 ~$ m; {% [) K. x) ~        while bucket[j]>0:
            arr[sortedIndex] = j
            sortedIndex+=1
            bucket[j]-=1
    return arr
* }4 t/ D4 t; P4 A  ~) ~. q2 ?1 F8 ~
: E, h" l0 k7 J8 ^3 p& y  `4 h
图片
9、桶排序
' ]1 h4 H- U# T# h" J$ j, T
4 _7 P0 J4 a3 X1 s; Z图片
& Y* x7 Q. ^8 |% s( R5 J" k+ L桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效，我们需要做到这两点：

在额外空间充足的情况下，尽量增大桶的数量
使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中
' J+ v9 d  ]) M3 l; R同时，对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要。
) l8 _% a( k! o/ W- a
' ~0 ?! ?. x- P1 k/ O, P7 {什么时候最快
0 }9 F5 C' N# z9 L) Y& X当输入的数据可以均匀的分配到每一个桶中。

什么时候最慢
; m. |/ U0 }' u  u当输入的数据被分配到了同一个桶中。
0 u! Q# G1 r, I+ a2 p
$ ~/ H( h8 m2 Y* q: tPython 代码
def bucket_sort(s):
    """桶排序"""
    min_num = min(s)
    max_num = max(s)
  X( f, s, y: d" T3 i0 N    # 桶的大小
5 Y+ I& V1 M5 y9 l; X) o5 }    bucket_range = (max_num-min_num) / len(s)
, A! M% ?. o, g) V    # 桶数组
    count_list = [ [] for i in range(len(s) + 1)]
    # 向桶数组填数
3 x& |% D0 b4 s; I& a    for i in s:
        count_list[int((i-min_num)//bucket_range)].append(i)
    s.clear()
    # 回填，这里桶内部排序直接调用了sorted
& s0 x" E4 @- t2 b0 N- Q    for i in count_list:
        for j in sorted(i):
            s.append(j)

if __name__ == __main__ :
    a = [3.2,6,8,4,2,6,7,3]
    bucket_sort(a)
1 L. t( j& V# M/ X# A/ R    print(a) # [2, 3, 3.2, 4, 6, 6, 7, 8]
( n8 I/ m5 n# U5 T
( R6 k* ^  a/ S
图片
10、基数排序

图片
基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。
) W: a  ~! S0 _& y+ P, x9 s* P. d
基数排序 vs 计数排序 vs 桶排序
基数排序有两种方法：

1 K5 \, ^' X: g4 P' L* ~这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：

/ Z" m+ W# X; U基数排序：根据键值的每位数字来分配桶；
计数排序：每个桶只存储单一键值；
6 o  R1 `7 e' l! [; I4 w* j桶排序：每个桶存储一定范围的数值；
4 T; d) m+ f; ~- r动图演示
) W* u, t. T! M& O0 S( g- Z7 W图片
8 m% y. U; E2 QPython 代码
def RadixSort(list):
    i = 0                                    #初始为个位排序
    n = 1                                     #最小的位数置为1（包含0）
, i9 k, `, Y' B5 g" F/ U    max_num = max(list) #得到带排序数组中最大数
$ o7 B; l3 o2 W4 t    while max_num > 10**n: #得到最大数是几位数
$ d( A1 o  j0 i2 N  `        n += 1
* n3 j. E* Q' S8 r    while i < n:
( o0 t$ q( G2 A0 L& R7 t' b        bucket = {} #用字典构建桶
/ n& r. p  ^' @$ ^+ `' U, [        for x in range(10):
            bucket.setdefault(x, []) #将每个桶置空
        for x in list: #对每一位进行排序
            radix =int((x / (10**i)) % 10) #得到每位的基数
            bucket[radix].append(x) #将对应的数组元素加入到相 #应位基数的桶中
        j = 0
/ X8 \% `6 Z. l- F) ^' D        for k in range(10):
* L! a" C8 l) C$ N% t; p            if len(bucket[k]) != 0: #若桶不为空
, ~1 T5 O6 J- r3 n  g                for y in bucket[k]: #将该桶中每个元素
                    list[j] = y #放回到数组中
                    j += 1
        i += 1
$ t0 M+ P* Q" p# sreturn  list