当前位置: 首页 > 编程笔记 >

python 常见的排序算法实现汇总

庄高谊
2023-03-14
本文向大家介绍python 常见的排序算法实现汇总,包括了python 常见的排序算法实现汇总的使用技巧和注意事项,需要的朋友参考一下

排序分为两类,比较类排序和非比较类排序,比较类排序通过比较来决定元素间的相对次序,其时间复杂度不能突破O(nlogn);非比较类排序可以突破基于比较排序的时间下界,缺点就是一般只能用于整型相关的数据类型,需要辅助的额外空间。

要求能够手写时间复杂度位O(nlogn)的排序算法:快速排序、归并排序、堆排序

1.冒泡排序

思想:相邻的两个数字进行比较,大的向下沉,最后一个元素是最大的。列表右边先有序。

时间复杂度$O(n^2)$,原地排序,稳定的

def bubble_sort(li:list):
  for i in range(len(li)-1):
    for j in range(i + 1, len(li)):
      if li[i] > li[j]:
        li[i], li[j] = li[j], li[i]

2.选择排序

思想:首先找到最小元素,放到排序序列的起始位置,然后再从剩余元素中继续寻找最小元素,放到已排序序列的末尾,以此类推,直到所有元素均排序完毕。列表左边先有序。

时间复杂度$O(n^2)$,原地排序,不稳定

def select_sort(nums: list):
  for i in range(len(nums) - 1):
    min_index = i
    for j in range(i + 1, len(nums)):
      if nums[j] < nums[i]:
        min_index = j
    nums[i], nums[min_index] = nums[min_index], nums[i] 

3.插入排序

思想:构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。列表左边先有序。

时间复杂度$O(n^2)$,原地排序,稳定

def insert_sort(nums: list):
  for i in range(len(nums)):
    current = nums[i]
    pre_index = i - 1
    while pre_index >= 0 and nums[pre_index] > current:
      nums[pre_index + 1] = nums[pre_index]
      pre_index -= 1
    nums[pre_index + 1] = current

4.希尔排序

思想:插入排序的改进版,又称缩小增量排序,将待排序的列表按下标的一定增量分组,每组分别进行直接插入排序,增量逐渐减小,直到为1,排序完成

时间复杂度$O(n^{1.5})$,原地排序,不稳定

def shell_sort(nums: list):
  gap = len(nums) >> 1
  while gap > 0:
    for i in range(gap, len(nums)):
      current = nums[i]
      pre_index = i - gap
      while pre_index >= 0 and nums[pre_index] > current:
        nums[pre_index + gap] = nums[pre_index]
        pre_index -= gap
      nums[pre_index + gap] = current
    gap >>= 1

5.快速排序

思想:递归,列表中取出第一个元素,作为标准,把比第一个元素小的都放在左侧,把比第一个元素大的都放在右侧,递归完成时就是排序结束的时候

时间复杂度$O(nlogn)$,空间复杂度$O(logn)$,不稳定

def quick_sort(li:list):
  if li == []:
    return []
  first = li[0]
  # 推导式实现
  left = quick_sort([l for l in li[1:] if l < first])
  right = quick_sort([r for r in li[1:] if r >= first])
  return left + [first] + right

6.归并排序

思想:分治算法,拆分成子序列,使用归并排序,将排序好的子序列合并成一个最终的排序序列。关键在于怎么合并:设定两个指针,最初位置分别为两个已经排序序列的起始位置,比较两个指针所指向的元素,选择相对小的元素放到合并空间,并将该指针移到下一位置,直到某一指针超出序列尾,将另一序列所剩下的所有元素直接复制到合并序列尾。

时间复杂度$O(nlogn)$,空间复杂度O(n),不稳定

二路归并

def merge_sort(nums: list):
  if len(nums) <= 1:
    return nums
  mid = len(nums) >> 1
  left = merge_sort(nums[:mid]) # 拆分子问题
  right = merge_sort(nums[mid:])

  def merge(left, right): # 如何归并
    res = []
    l, r = 0, 0
    while l < len(left) and r < len(right):
      if left[l] <= right[r]:
        res.append(left[l])
        l += 1
      else:
        res.append(right[r])
        r += 1
    res += left[l:]
    res += right[r:]
    return res

  return merge(left, right)

7.堆排序

思想:根节点最大,大顶堆,对应升序,根节点最小,小顶堆。

  • 构建大根堆,完全二叉树结构,初始无序
  • 最大堆调整,进行堆排序。将堆顶元素与最后一个元素交换,此时后面有序

时间复杂度$O(nlogn)$,原地排序,稳定

def heap_sort(nums: list):
  def heapify(parent_index, length, nums):
    temp = nums[parent_index] # 根节点的值
    chile_index = 2 * parent_index + 1 # 左节点,再加一为右节点
    while chile_index < length:
      if chile_index + 1 < length and nums[chile_index + 1] > nums[chile_index]:
        chile_index = chile_index + 1
      if temp > nums[chile_index]:
        break
      nums[parent_index] = nums[chile_index] # 使得根节点最大
      parent_index = chile_index
      chile_index = 2 * parent_index + 1
    nums[parent_index] = temp

  for i in range((len(nums) - 2) >> 1, -1, -1):
    heapify(i, len(nums), nums) # 1.建立大根堆
  for j in range(len(nums) - 1, 0, -1):
    nums[j], nums[0] = nums[0], nums[j]
    heapify(0, j, nums) # 2.堆排序,为升序
    
if __name__ == '__main__':
  nums = [89, 3, 3, 2, 5, 45, 33, 67] # [2, 3, 3, 5, 33, 45, 67, 89]
  heap_sort(nums)
  print(nums) 

以上就是python 常见的排序算法实现汇总的详细内容,更多关于python 排序算法的资料请关注小牛知识库其它相关文章!

 类似资料:
  • 本文向大家介绍python常见排序算法基础教程,包括了python常见排序算法基础教程的使用技巧和注意事项,需要的朋友参考一下 前言:前两天腾讯笔试受到1万点暴击,感觉浪费我两天时间去牛客网做题……这篇博客介绍几种简单/常见的排序算法,算是整理下。 时间复杂度 (1)时间频度一个算法执行所耗费的时间,从理论上是不能算出来的,必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试,只需

  • 本文向大家介绍Python实现的几个常用排序算法实例,包括了Python实现的几个常用排序算法实例的使用技巧和注意事项,需要的朋友参考一下 前段时间为准备百度面试恶补的东西,虽然最后还是被刷了,还是把那几天的“战利品”放点上来,算法一直是自己比较薄弱的地方,以后还要更加努力啊。 下面用Python实现了几个常用的排序,如快速排序,选择排序,以及二路并归排序等等。 运行结果如下:

  • 本文向大家介绍C/C++实现八大排序算法汇总,包括了C/C++实现八大排序算法汇总的使用技巧和注意事项,需要的朋友参考一下 概述排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。 我们这里说说八大排序就是内部排序。 当n较大,则应采用时间复杂度为O(nlog2n)的排序方法:快速排序、堆排序或归并排序。

  • 本文向大家介绍C++实现各种排序算法类汇总,包括了C++实现各种排序算法类汇总的使用技巧和注意事项,需要的朋友参考一下 C++可实现各种排序算法类,比如直接插入排序、折半插入排序、Shell排序、归并排序、简单选择排序、基数排序、对data数组中的元素进行希尔排序、冒泡排序、递归实现、堆排序、用数组实现的基数排序等。 具体代码如下:

  • 本文向大家介绍js实现常用排序算法,包括了js实现常用排序算法的使用技巧和注意事项,需要的朋友参考一下 本文为大家分享了js实现常用排序算法,具体内容如下 1.冒泡排序 2.选择排序  3.插入排序 4.希尔排序 5.归并排序 6.快速排序 总结:算法效率比较: 以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持呐喊教程。

  • 本文向大家介绍JS实现常见的查找、排序、去重算法示例,包括了JS实现常见的查找、排序、去重算法示例的使用技巧和注意事项,需要的朋友参考一下 本文实例讲述了JS实现常见的查找、排序、去重算法。分享给大家供大家参考,具体如下: 今天总结了下排序简单的算法 【自定义排序】 先寻找一个最小的数,然后依次那这个数和数组中其他数字比较,如果发现比这个数字小的数就把这两个数调换位置,然后再继续寻找下一个最小的数

  • 本文向大家介绍Python实现的堆排序算法示例,包括了Python实现的堆排序算法示例的使用技巧和注意事项,需要的朋友参考一下 本文实例讲述了Python实现的堆排序算法。分享给大家供大家参考,具体如下: 堆排序的思想: 堆是一种数据结构,可以将堆看作一棵完全二叉树,这棵二叉树满足,任何一个非叶节点的值都不大于(或不小于)其左右孩子节点的值。 将一个无序序列调整为一个堆,就可以找出这个序列的最大值

  • 本文向大家介绍Python实现的桶排序算法示例,包括了Python实现的桶排序算法示例的使用技巧和注意事项,需要的朋友参考一下 本文实例讲述了Python实现的桶排序算法。分享给大家供大家参考,具体如下: 桶排序也叫计数排序,简单来说,就是将数据集里面所有元素按顺序列举出来,然后统计元素出现的次数。最后按顺序输出数据集里面的元素。 但是桶排序非常浪费空间, 比如需要排序的范围在0~2000之间,