数学建模社区-数学中国
标题:
Python实现快速排序和插入排序算法及自定义排序的示例
[打印本页]
作者:
杨利霞
时间:
2020-4-12 11:41
标题:
Python实现快速排序和插入排序算法及自定义排序的示例
Python实现快速排序和插入排序算法及自定义排序的示例
0 j9 {! c$ T4 z
这篇文章主要介绍了Python实现快速排序和插入排序算法及自定义排序的示例,自定义排序用到了Python的sort和sorted函数,需要的朋友可以参考下
: E& I" Y3 V' Z: H9 S: Q
一、快速排序
; }9 w- p m$ t; ]
- w9 s) X, ?( D& C% @' V
快速排序（Quicksort）是对冒泡排序的一种改进。由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
" n; C7 d* i1 }
+ h: q8 [( S. `* ^# I5 U
快速排序，递归实现
S1 G+ I$ F2 r4 K0 @- m! s+ R
8 l) J% h5 B+ q3 r$ ~) s" v5 W
def quick_sort(num_list):
: ?: o* r& {$ t4 a
"""
; _ z5 ^4 Q; M. e5 X' `, o/ |
快速排序
( e# [' w _4 I
"""
. e( z( W+ ^( K. N7 Y/ m' O
if num_list == []:
" M9 Z5 K5 w' l- d: v+ }; u" v( J
return num_list
: ?3 N% T( ]$ P7 e0 F
smallList = []
0 T) b" ?% z* ?% ^$ v7 c3 j
bigList = []
- w: q2 q8 j$ g, L8 X- L7 _4 w* s0 \
middleElement = num_list[0]
7 G+ |+ h( b& C* G
for i in num_list[1:]:
% ?* P. h$ O5 a4 f
if i <= middleElement:
( c, [; A3 d# v% R8 a6 f+ M
smallList.append(i)
7 C& o" J. O y( S# C
else:
/ w" W- n' v5 z9 p P( a
bigList.append(i)
+ h) ?/ ~' `! w4 v# Y1 ?; S
return quick_sort(smallList)+[middleElement]+quick_sort(bigList)
7 N: y2 ^; l* p! y$ m* N: E; A
/ [* p% h/ G: j5 J
7 @+ w" a/ d2 b( H) T7 _1 {5 r
插入排序（Insertion Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
- j. t4 A- }1 Y/ S0 ^
4 J# a. B( |+ A4 o l
插入排序
8 d9 z' Q" r; ~6 L* f' f
# [' r) z( y9 Q% A3 u1 [/ m* S- ?
, z3 h& I1 u2 @5 S7 }
def insert_sort(num_list):
# W0 {% a2 l" f' B, i$ ^5 b8 u* ?! G
"""
/ W, u% t, G3 s0 a" \
插入排序
: H* N: T7 \& l: ]" [6 _8 {
"""
6 H+ |$ o' [ \1 \6 E- p- W
for i in range(len(num_list)-1):
7 {- D5 c- q: Z% ]3 B
for j in range(i+1, len(num_list)):
9 Z9 E# @4 n& s5 b4 x2 Z( P% P+ E
if num_list
>num_list[j]:
4 D0 b- T; a' ?+ m( ^3 a
num_list
,num_list[j] = num_list[j],num_list
* c! @* @, `, m
return num_list
% n# ^# |; A2 F2 w/ l6 k+ V
+ F7 }3 H- z8 G8 f) y
! T1 ]8 r4 w" I. v8 }
三、自定义排序
4 N e" h1 b& L0 D) T
利用 sort() 或 sorted() 的 key 即可实现。
7 u! o# l; O( ]) l6 v$ {3 G
def sort_key(obj):
- U+ D, s+ s* A0 `
sorted_list = [4, 2, 5, 9, 7, 8, 1, 3, 6, 0]
1 p) ?2 a# n# K/ P+ k! V
return sorted_list.index(obj)
) H; O6 n( T8 A" C$ I
! o% C" ]/ ^3 C: s
" h6 L4 L" P% N$ b1 x; Y5 J G1 W
if __name__ == '__main__':
6 n- g) ~# v" S
print sorted(range(10), key=sort_key)
/ v- [* b8 k% H) w6 r4 k
5 x$ x) G8 g' n: y) }* F6 k9 N3 H1 y
# 输出结果如下
/ Y! c" U3 }+ h- e
[4, 2, 5, 9, 7, 8, 1, 3, 6, 0]
8 [; t l. c+ j& {! R; x
* Y w W& x8 U! b$ O& z6 G9 B4 {
1 ~; s7 Z9 ]! c( n/ k( l
非常感谢你的阅读
( m6 h: j) o$ J1 `
大学的时候选择了自学python，工作了发现吃了计算机基础不好的亏，学历不行这是
0 U) {* z8 z( u( S/ f/ ]* k
没办法的事，只能后天弥补，于是在编码之外开启了自己的逆袭之路，不断的学习python核心知识，深入的研习计算机基础知识，整理好了，如果你也不甘平庸，那就与我一起在编码之外，不断成长吧！
|6 u( F$ T0 F: S
其实这里不仅有技术，更有那些技术之外的东西，比如，如何做一个精致的程序员，而不是“屌丝”，程序员本身就是高贵的一种存在啊，难道不是吗？[点击加入]想做你自己想成为高尚人，加油！
6 _6 b: Y/ }5 Q& e
————————————————
) {: s7 w; Y3 n2 Y, s% A
版权声明：本文为CSDN博主「程序员牡蛎」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
: F, F, P* {) N$ X4 x; t a
原文链接：https://blog.csdn.net/chengxun03/article/details/105460563
/ m2 C8 W& E; y2 r$ W j
4 R! {3 a3 {. P( T9 k: X% T" a5 v6 [. q
( e' u @2 D$ B
7 a9 a6 C$ U* @' B
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5