首页 后端开发 Python教程 总结有关python八大排序算法(下)

总结有关python八大排序算法(下)

Sep 16, 2017 am 10:14 AM
python 排序

这篇文章主要为大家详细介绍了python实现八大排序算法的第二篇,具有一定的参考价值,感兴趣的小伙伴们可以参考一下

本文接上一篇博客python实现的八大排序算法part1,将继续使用python实现八大排序算法中的剩余四个:快速排序、堆排序、归并排序、基数排序

5、快速排序

快速排序是通常被认为在同数量级(O(nlog2n))的排序方法中平均性能最好的。

算法思想:

已知一组无序数据a[1]、a[2]、……a[n],需将其按升序排列。首先任取数据a[x]作为基准。比较a[x]与其它数据并排序,使a[x]排在数据的第k位,并且使a[1]~a[k-1]中的每一个数据a[x],然后采用分治的策略分别对a[1]~a[k-1]和a[k+1]~a[n]两组数据进行快速排序。
优点:极快,数据移动少;
缺点:不稳定。

python代码实现:


def quick_sort(list):
  little = []
  pivotList = []
  large = []
  # 递归出口
  if len(list) <= 1:
    return list
  else:
    # 将第一个值做为基准
    pivot = list[0]
    for i in list:
      # 将比基准小的值放到less数列
      if i < pivot:
        little.append(i)
      # 将比基准大的值放到more数列
      elif i > pivot:
        large.append(i)
      # 将和基准相同的值保存在基准数列
      else:
        pivotList.append(i)
    # 对less数列和more数列继续进行快速排序
    little = quick_sort(little)
    large = quick_sort(large)
    return little + pivotList + large
登录后复制

下面这段代码出自《Python cookbook 第二版的三行实现python快速排序。


#!/usr/bin/env python
#coding:utf-8
&#39;&#39;&#39;
file:python-8sort.py
date:9/1/17 9:03 AM
author:lockey
email:lockey@123.com
desc:python实现八大排序算法
&#39;&#39;&#39;
lst = [65,568,9,23,4,34,65,8,6,9]
def quick_sort(list):
  if len(list) <= 1:
    return list
  else:
    pivot = list[0]
    return quick_sort([x for x in list[1:] if x < pivot]) + \
        [pivot] + \
        quick_sort([x for x in list[1:] if x >= pivot])
登录后复制

运行测试结果截图:

这里写图片描述

好吧,还有更精简的语法糖,一行完事:

quick_sort = lambda xs : ( (len(xs) <= 1 and [xs]) or [ quick_sort( [x for x in xs[1:] if x < xs[0]] ) + [xs[0]] + quick_sort( [x for x in xs[1:] if x >= xs[0]] ) ] )[0]

若初始序列按关键码有序或基本有序时,快排序反而蜕化为冒泡排序。为改进之,通常以“三者取中法”来选取基准记录,即将排序区间的两个端点与中点三个记录关键码居中的调整为支点记录。快速排序是一个不稳定的排序方法。

在改进算法中,我们将只对长度大于k的子序列递归调用快速排序,让原序列基本有序,然后再对整个基本有序序列用插入排序算法排序。实践证明,改进后的算法时间复杂度有所降低,且当k取值为 8 左右时,改进算法的性能最佳。

6、堆排序(Heap Sort)

堆排序是一种树形选择排序,是对直接选择排序的有效改进。

优点 : 效率高
缺点:不稳定

堆的定义下:具有n个元素的序列 (h1,h2,...,hn),当且仅当满足(hi>=h2i,hi>=2i+1)或(hi<=h2i,hi<=2i+1) (i=1,2,...,n/2)时称之为堆。在这里只讨论满足前者条件的堆。由堆的定义可以看出,堆顶元素(即第一个元素)必为最大项(大顶堆)。完全二 叉树可以很直观地表示堆的结构。堆顶为根,其它为左子树、右子树。

算法思想:

初始时把要排序的数的序列看作是一棵顺序存储的二叉树,调整它们的存储序,使之成为一个 堆,这时堆的根节点的数最大。然后将根节点与堆的最后一个节点交换。然后对前面(n-1)个数重新调整使之成为堆。依此类推,直到只有两个节点的堆,并对 它们作交换,最后得到有n个节点的有序序列。从算法描述来看,堆排序需要两个过程,一是建立堆,二是堆顶与堆的最后一个元素交换位置。所以堆排序有两个函数组成。一是建堆的渗透函数,二是反复调用渗透函数实现排序的函数。

python代码实现:


# -*- coding: UTF-8 -*-
&#39;&#39;&#39;
Created on 2017年9月2日
Running environment:win7.x86_64 eclipse python3
@author: Lockey
&#39;&#39;&#39;
lst = [65,568,9,23,4,34,65,8,6,9]
def adjust_heap(lists, i, size):# 调整堆
  lchild = 2 * i + 1;rchild = 2 * i + 2
  max = i
  if i < size / 2:
    if lchild < size and lists[lchild] > lists[max]:
      max = lchild
    if rchild < size and lists[rchild] > lists[max]:
      max = rchild
    if max != i:
      lists[max], lists[i] = lists[i], lists[max]
      adjust_heap(lists, max, size)
def build_heap(lists, size):# 创建堆
  halfsize = int(size/2)
  for i in range(0, halfsize)[::-1]:
    adjust_heap(lists, i, size)
def heap_sort(lists):# 堆排序
  size = len(lists)
  build_heap(lists, size)
  for i in range(0, size)[::-1]:
    lists[0], lists[i] = lists[i], lists[0]
    adjust_heap(lists, 0, i)
    print(lists)
登录后复制

结果示例:

这里写图片描述

7、归并排序

算法思想:

归并(Merge)排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。

归并过程为:比较a[i]和a[j]的大小,若a[i]≤a[j],则将第一个有序表中的元素a[i]复制到r[k]中,并令i和k分别加上1;否则将第二个有序表中的元素a[j]复制到r[k]中,并令j和k分别加上1,如此循环下去,直到其中一个有序表取完,然后再将另一个有序表中剩余的元素复制到r中从下标k到下标t的单元。归并排序的算法我们通常用递归实现,先把待排序区间[s,t]以中点二分,接着把左边子区间排序,再把右边子区间排序,最后把左区间和右区间用一次归并操作合并成有序的区间[s,t]。


# -*- coding: UTF-8 -*-
&#39;&#39;&#39;
Created on 2017年9月2日
Running environment:win7.x86_64 eclipse python3
@author: Lockey
&#39;&#39;&#39;
lst = [65,568,9,23,4,34,65,8,6,9]
def merge(left, right):
  i, j = 0, 0
  result = []
  while i < len(left) and j < len(right):
    if left[i] <= right[j]:
      result.append(left[i])
      i += 1
    else:
      result.append(right[j])
      j += 1
  result += left[i:]
  result += right[j:]
  print(result)
  return result
def merge_sort(lists):# 归并排序
  if len(lists) <= 1:
    return lists
  num = int(len(lists) / 2)
  left = merge_sort(lists[:num])
  right = merge_sort(lists[num:])
  return merge(left, right)
登录后复制

程序结果示例:

这里写图片描述

8、桶排序/基数排序(Radix Sort)

优点:快,效率最好能达到O(1)
缺点:

1.首先是空间复杂度比较高,需要的额外开销大。排序有两个数组的空间开销,一个存放待排序数组,一个就是所谓的桶,比如待排序值是从0到m-1,那就需要m个桶,这个桶数组就要至少m个空间。

2.其次待排序的元素都要在一定的范围内等等。

算法思想:

是将阵列分到有限数量的桶子里。每个桶子再个别排序(有可能再使用别的排序算法或是以递回方式继续使用桶排序进行排序)。桶排序是鸽巢排序的一种归纳结果。当要被排序的阵列内的数值是均匀分配的时候,桶排序使用线性时间(Θ(n))。但桶排序并不是 比较排序,他不受到 O(n log n) 下限的影响。
简单来说,就是把数据分组,放在一个个的桶中,然后对每个桶里面的在进行排序。
例如要对大小为[1..1000]范围内的n个整数A[1..n]排序

首先,可以把桶大小设为10,这样就有100个桶了,具体而言,设集合B[1]存储[1..10]的整数,集合B[2]存储 (10..20]的整数,……集合B[i]存储( (i-1)*10, i*10]的整数,i = 1,2,..100。总共有 100个桶。

然后,对A[1..n]从头到尾扫描一遍,把每个A[i]放入对应的桶B[j]中。 再对这100个桶中每个桶里的数字排序,这时可用冒泡,选择,乃至快排,一般来说任 何排序法都可以。

最后,依次输出每个桶里面的数字,且每个桶中的数字从小到大输出,这 样就得到所有数字排好序的一个序列了。

假设有n个数字,有m个桶,如果数字是平均分布的,则每个桶里面平均有n/m个数字。如果

对每个桶中的数字采用快速排序,那么整个算法的复杂度是

O(n + m * n/m*log(n/m)) = O(n + nlogn - nlogm)

从上式看出,当m接近n的时候,桶排序复杂度接近O(n)

当然,以上复杂度的计算是基于输入的n个数字是平均分布这个假设的。这个假设是很强的 ,实际应用中效果并没有这么好。如果所有的数字都落在同一个桶中,那就退化成一般的排序了。

python代码实现:


# -*- coding: UTF-8 -*-
&#39;&#39;&#39;
Created on 2017年9月2日
Running environment:win7.x86_64 eclipse python3
@author: Lockey
&#39;&#39;&#39;
import math
lst = [65,56,9,23,84,34,8,6,9,54,11]
#因为列表数据范围在100以内,所以将使用十个桶来进行排序
def radix_sort(lists, radix=10):
  k = int(math.ceil(math.log(max(lists), radix)))
  bucket = [[] for i in range(radix)]
  for i in range(1, k+1):
    for j in lists:
      gg = int(j/(radix**(i-1))) % (radix**i)
      bucket[gg].append(j)
    del lists[:]
    for z in bucket:
      lists += z
      del z[:]
      print(lists)
  return lists
登录后复制

程序运行测试结果:

这里写图片描述

以上是总结有关python八大排序算法(下)的详细内容。更多信息请关注PHP中文网其他相关文章!

本站声明
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn

热AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智能驱动的应用程序,用于创建逼真的裸体照片

AI Clothes Remover

AI Clothes Remover

用于从照片中去除衣服的在线人工智能工具。

Undress AI Tool

Undress AI Tool

免费脱衣服图片

Clothoff.io

Clothoff.io

AI脱衣机

Video Face Swap

Video Face Swap

使用我们完全免费的人工智能换脸工具轻松在任何视频中换脸!

热工具

记事本++7.3.1

记事本++7.3.1

好用且免费的代码编辑器

SublimeText3汉化版

SublimeText3汉化版

中文版,非常好用

禅工作室 13.0.1

禅工作室 13.0.1

功能强大的PHP集成开发环境

Dreamweaver CS6

Dreamweaver CS6

视觉化网页开发工具

SublimeText3 Mac版

SublimeText3 Mac版

神级代码编辑软件(SublimeText3)

PHP和Python:解释了不同的范例 PHP和Python:解释了不同的范例 Apr 18, 2025 am 12:26 AM

PHP主要是过程式编程,但也支持面向对象编程(OOP);Python支持多种范式,包括OOP、函数式和过程式编程。PHP适合web开发,Python适用于多种应用,如数据分析和机器学习。

在PHP和Python之间进行选择:指南 在PHP和Python之间进行选择:指南 Apr 18, 2025 am 12:24 AM

PHP适合网页开发和快速原型开发,Python适用于数据科学和机器学习。1.PHP用于动态网页开发,语法简单,适合快速开发。2.Python语法简洁,适用于多领域,库生态系统强大。

Python vs. JavaScript:学习曲线和易用性 Python vs. JavaScript:学习曲线和易用性 Apr 16, 2025 am 12:12 AM

Python更适合初学者,学习曲线平缓,语法简洁;JavaScript适合前端开发,学习曲线较陡,语法灵活。1.Python语法直观,适用于数据科学和后端开发。2.JavaScript灵活,广泛用于前端和服务器端编程。

PHP和Python:深入了解他们的历史 PHP和Python:深入了解他们的历史 Apr 18, 2025 am 12:25 AM

PHP起源于1994年,由RasmusLerdorf开发,最初用于跟踪网站访问者,逐渐演变为服务器端脚本语言,广泛应用于网页开发。Python由GuidovanRossum于1980年代末开发,1991年首次发布,强调代码可读性和简洁性,适用于科学计算、数据分析等领域。

vs code 可以在 Windows 8 中运行吗 vs code 可以在 Windows 8 中运行吗 Apr 15, 2025 pm 07:24 PM

VS Code可以在Windows 8上运行,但体验可能不佳。首先确保系统已更新到最新补丁,然后下载与系统架构匹配的VS Code安装包,按照提示安装。安装后,注意某些扩展程序可能与Windows 8不兼容,需要寻找替代扩展或在虚拟机中使用更新的Windows系统。安装必要的扩展,检查是否正常工作。尽管VS Code在Windows 8上可行,但建议升级到更新的Windows系统以获得更好的开发体验和安全保障。

visual studio code 可以用于 python 吗 visual studio code 可以用于 python 吗 Apr 15, 2025 pm 08:18 PM

VS Code 可用于编写 Python,并提供许多功能,使其成为开发 Python 应用程序的理想工具。它允许用户:安装 Python 扩展,以获得代码补全、语法高亮和调试等功能。使用调试器逐步跟踪代码,查找和修复错误。集成 Git,进行版本控制。使用代码格式化工具,保持代码一致性。使用 Linting 工具,提前发现潜在问题。

vscode怎么在终端运行程序 vscode怎么在终端运行程序 Apr 15, 2025 pm 06:42 PM

在 VS Code 中,可以通过以下步骤在终端运行程序:准备代码和打开集成终端确保代码目录与终端工作目录一致根据编程语言选择运行命令(如 Python 的 python your_file_name.py)检查是否成功运行并解决错误利用调试器提升调试效率

vscode 扩展是否是恶意的 vscode 扩展是否是恶意的 Apr 15, 2025 pm 07:57 PM

VS Code 扩展存在恶意风险,例如隐藏恶意代码、利用漏洞、伪装成合法扩展。识别恶意扩展的方法包括:检查发布者、阅读评论、检查代码、谨慎安装。安全措施还包括:安全意识、良好习惯、定期更新和杀毒软件。

See all articles