Python实现经典排序算法-超详细

目前已经有很多非常成熟的排序算法,虽然使用python时,有sort这样的方法可以实现排序。但在实际工作中,还是难免需要手写一些排序过程。跳槽在面试时,手撕一个排序算法,也是经常需要做的事情。

本文总结了以下排序算法的Python实现:(持续更新)

  1. 冒泡排序
  2. 选择排序
  3. 插入排序
  4. 快速排序

冒泡排序

冒泡排序(Bubble Sort)是一种交换排序,基本思想是:两两比较相邻记录的关键字,如果反序则交换,直到没有反序的记录为止。

在最好的情况下,也就是数列本身是排好序的,需要进行 n – 1 次比较;在最坏的情况下,也就是数列本身是逆序的,需要进行 n(n-1)/2 次比较。因此冒泡排序总的时间复杂度是 O(n^2)。

步骤:

  • 从第一组两个相邻元素开始比较,依次往后交换
  • 每经过一次排序较大的元素就会被放到后面,直到最大的元素被放到最后,那么下一次排序的时候也就不用用它(最后一个数)和它相邻的前面的数进行比较了,最后的元素就成了“稳定元素”
  • 重复以上步骤,每一次排序完成,最后的“稳定元素”都会增加一个,直到没有可以交换的元素,那么排序就完成了
冒泡排序

上面动图中

  • 橙色表示被排序好的数字
  • 绿色表示迭代过程中的数字
  • 蓝色表示等待排序的数字

以下是冒泡排序的Python实现

# 冒泡排序
def bubbleSort(nums):
if len(nums) <= 1:
return nums

for i in range(len(nums) - 1):
for j in range(len(nums) - i - 1):
if nums[j] > nums[j + 1]:
nums[j], nums[j + 1] = nums[j + 1], nums[j]
return nums

listnum = [5, 3, 8, 7, 9, 2, 18, 6, 8, 10, 55, 12, 58, 47]
bubbleSort(listnum)

选择排序

选择排序(Selection sort) 的基本思想是每一趟在 n – i + 1 (i = 1,2,***,n – 1)个记录中选取关键字最小(或最大)的记录作为有序序列的第 i 个记录,直到所有元素排序完成。选择排序是不稳定的排序算法。

选择排序的时间复杂度为 O(n^2),但性能上略优于冒泡排序。

步骤:

  • 把要排序的序列分为有序序列和无序序列
  • 遍历序列,每一次从无序序列找到最小元素,定义为minIndex=i,放到无序序列最前面,
  • 直到无序区间内没有元素,也就是所有元素都排好序
选择排序

上面动图中:

  • 橙色表示被排序好的数字
  • 绿色表示迭代过程中的数字
  • 蓝色表示等待排序的数字
  • 红色表示一轮迭代中的minIndex,最小值的索引。

以下是选择排序的Python实现

# 选择排序
def selectionSort(nums):
if len(nums) <= 1:
return nums

for i in range(0, len(nums)):
# 最小值位置索引
minIndex = i
for j in range(i + 1, len(nums)):
if nums[j] < nums[minIndex]:
minIndex = j
nums[i], nums[minIndex] = nums[minIndex], nums[i]
return nums

listnum = [5, 3, 8, 7, 9, 2, 18, 6, 8, 10, 55, 12, 58, 47]
selectionSort(listnum)

数据采集工作,爬取公司评级文件与法律文书,并对爬取的PDF文件进行OCR识别处理

插入排序

每次选择一个元素,并且将这个元素和整个数组中的所有元素进行比较,然后插入到合适的位置,插入排序的时间复杂度 O(n^2)

步骤:

  • 从第一个元素开始,认为第一个元素已经被排序
  • 取出下一个元素,在已排好序的序列中从后往前扫描
  • 如果该元素(已排好序)大于新元素,将该元素移到下一位置
  • 重复步骤3,直到找到已排好序的元素小于或者等于新元素的位置
  • 将新元素插入到该位置后
  • 重复步骤2-5
插入排序

上面动图中:

  • 橙色表示被排序好的数字
  • 绿色表示与迭代过程中比较的数字
  • 蓝色表示等待排序的数字
  • 红色表示迭代过程中的数字。

以下是选择排序的Python实现

# 插入排序
def insertSort(nums):
if len(nums) <= 1:
return nums

for i in range(1, len(nums)):
pos = 0
for j in range(i - 1, -1, -1):
if nums[i] > nums[j]:
pos = j + 1
break
temp = nums[i]
for x in range(i, pos - 1, -1):
nums[x] = nums[x - 1]
nums[pos] = temp
return nums

listnum = [5, 3, 8, 7, 9, 2, 18, 6, 8, 10, 55, 12, 58, 47]
insertSort(listnum)

快速排序

快速排序(Quicksort)是对冒泡排序的一种改进。基本思想是通过一趟排序将待排记录分割成独立的两部分,其中一部分的记录都比另一部分小,然后再分别对这两个部分进行快速排序,最终实现整个序列的排序。

快速排序例子

步骤解析:

  • 一开始选定数组的最后一个元素5作为基准值,也就是最终排序结果应该是以5为界限划分为左右两边

  • 从左边开始,寻找比5大的值,然后与5进行调换(因为如果比5小的值本来就应该排在5前面,比5大的值调换之后就去到了5的后面),一路过来找到了7,将7与5调换,结束此次遍历

  • 从右边开始,由于7已经是上一轮排好序的便不再动它,从10开始,一路向左遍历,寻找比5小的值,然后与5进行调换(因为如果比5大的值本来就应该排在5后面,比5小的值调换之后就去到了5的后前面),一路过来找到了4,将4与5调换,结束此次遍历

  • 从左边开始,由于3和4都是前两轮已经排好序的便不再动它,从2开始,一路向右遍历,寻找比5大的值,然后与5进行调换(道理同步骤2),一路过来找到了9,将9与5调换,结束此次遍历

  • 从右边开始,由于排在9后面的那几个数字都是上几轮排好序的便不再动它,从1开始,一路向右遍历,寻找比5小的值,然后与5进行调换(道理同步骤3),一下子就找到了1,将1与5调换,结束此次遍历

  • 这个时候,发现5的左右两边都是排好序了的,所以结束此轮排序,5的左右两边抽出来各自进行下一轮的排序,规则同上,直到无法再拆分下去,即完成了整体的快速排序

快速排序

上面动图中:

  • 橙色表示被排序好,小于基准的数字
  • 紫色表示被排序好,大于基准的数字
  • 黄色表示基准数字
  • 绿色表示与迭代过程中比较的数字
  • 蓝色表示等待排序的数字
  • 红色表示迭代过程中的数字。

以下是快速排序的Python实现,里面使用了递归调用的方法。

# 快速排序
def quicksort(nums):
if len(nums) <= 1:
return nums

# 左子数组
left = []
# 右子数组
right = []
# 基准数,数组最后一位
base = nums.pop()
# 对原数组进行划分
for x in nums:
if x < base:
left.append(x)
else:
right.append(x)
# 递归调用
return quicksort(right) + [base] + quicksort(left)

listnum = [5, 3, 8, 7, 9, 2, 18, 6, 8, 10, 55, 12, 58, 47]
quicksort(listnum)

参考资料

The End


已发布

分类

标签:

评论

《“Python实现经典排序算法-超详细”》 有 2 条评论

  1.  的头像
    匿名

    选择排序,这句代码是不是应该是在if条件里面,要不没啥意义
    nums[i], nums[minIndex] = nums[minIndex], nums[i]

    1. monk 的头像
      monk

      谢谢评论,无需放到if条件里面哦,因为做出if判断后,将j赋值给了minindex,所有后面交换值的时候,可以直接进行

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注