Python实现快速排序和插入排序算法及自定义排序的示例

杨利霞

Python实现快速排序和插入排序算法及自定义排序的示例
5 \* Y* ^! K8 T" J/ {这篇文章主要介绍了Python实现快速排序和插入排序算法及自定义排序的示例,自定义排序用到了Python的sort和sorted函数,需要的朋友可以参考下
一、快速排序

快速排序（Quicksort）是对冒泡排序的一种改进。由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

快速排序，递归实现
) ]4 W" o3 n' v# s/ `& g1 ?2 L; s
( \1 `' ~) K! {; J! L1 d! A# O+ Y  w    def quick_sort(num_list):
, \7 h" |, Z- ^# I2 x, Q  """
  快速排序
  """
! R" T- m/ T9 \' B" c  if num_list == []:
' y. x% p" A2 d3 ?    return num_list
9 q% c  U% Y; g9 t( E+ s6 V  smallList = []
  bigList = []
7 ^. y5 n1 ~& r" K( b  middleElement = num_list[0]
$ V: H/ ^8 r- ?* c  for i in num_list[1:]:
! G* y# |+ Z' Q4 ?5 e4 Q9 n    if i <= middleElement:
8 j6 o5 T( y* q      smallList.append(i)
, Q/ t8 q% [8 d3 S) F" K- H* l    else:
      bigList.append(i)
, x6 @2 L0 o& ~. w7 l' ]( J; U  Y  return quick_sort(smallList)+[middleElement]+quick_sort(bigList)
9 [; S0 h8 p# q7 r$ I# K+ j# j: v" R

# q4 I! J. R0 d3 P1 a/ P插入排序（Insertion Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

插入排序
" D8 |1 \( Z3 K( f. c' \- @# P

  E/ a0 I- {$ F0 Q* d; R0 `def insert_sort(num_list):
  """
  插入排序
  """
  for i in range(len(num_list)-1):
! z5 F/ S: r; e1 b+ o6 p8 ?" a    for j in range(i+1, len(num_list)):
8 O. \6 `0 P2 U' B# s$ R      if num_list>num_list[j]:
$ m( Z6 V- ]0 g: q( R# L# C        num_list,num_list[j] = num_list[j],num_list
6 i9 e, X2 H2 P9 }  return num_list
2 J8 A* k  B/ |( K
( M: y& K: _& Q5 m  Q- b: ?
三、自定义排序
' I5 J! q$ e0 Z利用 sort() 或 sorted() 的 key 即可实现。
def sort_key(obj):
  sorted_list = [4, 2, 5, 9, 7, 8, 1, 3, 6, 0]
; M  {$ |5 G4 `5 t  return sorted_list.index(obj)

6 c( {: A% L9 n
if __name__ == '__main__':
  print sorted(range(10), key=sort_key)

! R4 j% O' R$ h. X3 r) g( {: u' {# 输出结果如下
# z8 ^  Z- M% p' i$ s; f[4, 2, 5, 9, 7, 8, 1, 3, 6, 0]
. F1 N$ L% ^& A0 @$ }3 _
0 s7 i) S- ~" U! [
6 T, U8 C  s% {6 E! t非常感谢你的阅读
大学的时候选择了自学python，工作了发现吃了计算机基础不好的亏，学历不行这是
: U0 C8 [5 G/ o5 D! d$ ?没办法的事，只能后天弥补，于是在编码之外开启了自己的逆袭之路，不断的学习python核心知识，深入的研习计算机基础知识，整理好了，如果你也不甘平庸，那就与我一起在编码之外，不断成长吧！
9 Y  O( X5 y5 z+ i! i: P1 ?+ u5 o其实这里不仅有技术，更有那些技术之外的东西，比如，如何做一个精致的程序员，而不是“屌丝”，程序员本身就是高贵的一种存在啊，难道不是吗？[点击加入]想做你自己想成为高尚人，加油！
  l* X9 Q4 n# A" \————————————————
版权声明：本文为CSDN博主「程序员牡蛎」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
8 m1 ?' ^9 b1 _. b: ^原文链接：https://blog.csdn.net/chengxun03/article/details/105460563
$ H# n5 K* V) N9 Q5 x
; k1 @2 v  V" O; |( g  z

0 j- }+ n5 T+ R+ j$ m