Sorting Algorithms in Python (排序算法)

这篇具有很好参考价值的文章主要介绍了Sorting Algorithms in Python (排序算法)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

本篇文章主要介绍几种经典排序算法:冒泡排序、快速排序、选择排序、堆排序、插入排序、希尔排序、归并排序、桶排序和基数排序。并给出用python实现的算法代码。

目录

一、冒泡排序

二、快速排序

三、选择排序

四、堆排序

五、插入排序

六、希尔排序

七、归并排序

八、桶排序

九、基数排序

一、冒泡排序

冒泡排序如名所见,最大元素像泡泡一样逐渐向上冒,直至顶端(此处指从小到大排序)。最好时间复杂度为O(n),即需排序数组已为有序数组;最坏时间复杂度为O(n²),即需排序数组与要求顺序相反;平均复杂度为O(n²),如下代码所示,两层循环每层时间复杂度均为O(n)。空间复杂度为O(1),无需额外空间消耗,算法稳定。

代码:

def bubbleSort(nums):
	for i in range(len(nums)):
		is_sort = True
		for j in range(len(nums) - i - 1):
			if nums[j] > nums[j + 1]:
				nums[j], nums[j + 1] = nums[j + 1], nums[j]
				is_sort = False
		if is_sort:
			break
	return nums

解释:

1)设置is_sort判断元素是否已经有序,若元素已完成该轮排序则直接跳出该轮循环进行新一轮排序(即i+1) 

2)每轮排序结束,最后一个元素已为最大值(按从小到大顺序排列),下一轮排序则只需对除此之外的元素进行排序:

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

        其中i为轮次,-1是因为在元素比较时为向后比较(nums[j], nums[j + 1])。

3)算法图解:

Sorting Algorithms in Python (排序算法),排序算法,算法,数据结构,python

图1 冒泡排序算法图解(图源@独影月下酌酒) 

二、快速排序

快速排序通过选择“哨兵”结合递归实现排序。最好时间复杂度为O(nlogn),最坏时间复杂度为O(n*n),平均复杂度为O(n*n)。空间复杂度为O(nlogn),算法不稳定。

代码:

def quickSort(nums, left, right):
	
	def partition(nums, left, right):
		pivot = nums[left]
		while left < right:
			while left < right and nums[right] >= pivot:
				right -= 1
			nums[left] = nums[right]

			while left < right and nums[left] <= pivot:
				left += 1
			nums[right] = nums[left]
		nums[left] = pivot
		return left

	if left < right:
		pivotIndex = partition(nums, left, right)
		quickSort(nums, left, pivotIndex - 1)
		quickSort(nums, pivotIndex + 1, right)
	return nums

解释:

1)快速排序思想实质上是先找到哨兵,然后对哨兵左右边的元素再进行快速排序。partiton函数即对初始数组进行一次快排并返回哨兵元素的下标,接着主函数调用快排函数本身实现哨兵左右元素的排序。

2)需要注意在partition函数中,先对数组右边元素进行判断,若右边元素大于等于哨兵(pivot),则说明无需移动该元素,右指针左移,直到发现一个哨兵右侧元素小于pivot,此时需要把该元素移到左边,此时将该值赋给左指针指向的位置元素。当pivot右侧元素全都大于等于pivot且右指针仍然在左指针右边时,开始判断pivot左侧元素,当左侧元素小于等于pivot时,左指针右移直到发现某元素大于pivot,将该值赋给右指针指向的位置元素,直到左右指针重合,说明已找到哨兵pivot应放的位置,此时left=right=pivot下标,返回left或right即为pivot位置。

3)在得到哨兵位置后能确定pivot左侧元素均小于哨兵,右侧元素均大于哨兵,此时只需对哨兵左右元素再递归进行快速排序即可。

4)注意大前提left<right

5)算法图解:

Sorting Algorithms in Python (排序算法),排序算法,算法,数据结构,python

图2 快速排序算法图解(图源@独影月下酌酒)  

三、选择排序

选择排序即每轮选取一个最小(大)元素放置起始位置,直到所有元素均排序完成。最好时间复杂度为O(n²); 平均时间复杂度为O(n²); 最差时间复杂度为O(n²)。

代码:

def selectSort(nums):
	for i in range(len(nums)):
		min_index = i
		for j in range(i + 1, len(nums)):
			if nums[j] < nums[min_index]:
				min_index = j
		if min_index != i:
			nums[min_index], nums[i] = nums[i], nums[min_index]
	return nums

解释:

1)选择排序没有特别需要注意的地方,弄清算法逻辑就能很快实现。 

2)算法图解:

Sorting Algorithms in Python (排序算法),排序算法,算法,数据结构,python

图3 选择排序算法图解(图源@独影月下酌酒)  

四、堆排序

堆排序分小顶堆和大顶堆,前者根节点小于左右结点,后者根节点大于左右结点,本文用大顶堆排序。最好时间复杂度为O(nlogn),平均时间复杂度为O(nlogn),最差时间复杂度为O(nlogn)。

代码:

def heap(nums):

	def adjustHeap(nums, i, length):
		lchild, rchild = 2 * i + 1, 2 * i + 2
		largest = i
		if lchild < length and nums[lchild] > nums[largest]:
			largest = lchild
		if rchild < length and nums[rchild] > nums[largest]:
			largest = rchild
		if largest != i:
			nums[largest], nums[i] = nums[i], nums[largest]
			adjustHeap(nums, largest, length)
		return nums

	for i in range(len(nums) // 2)[::-1]:
		adjustHeap(nums, i, len(nums))
	for i in range(len(nums))[::-1]:
		nums[0], nums[i] = nums[i], nums[0]
		adjustHeap(nums, 0, i)
	return nums

解释:

1)拿到一个乱序数组,先将其初始为一个堆(即一棵二叉树),然后调整该堆(adjustHeap函数),使得根节点为最大值 :

        for i in range(len(nums) // 2)[::-1]:
                adjustHeap(nums, i, len(nums))

        堆初始化,从最后一个非叶子节点创建大顶堆

2)堆初始化完成且调整为大顶堆后,交换堆顶元素和需要排序的数组的最后一个元素,调整新数组为大顶堆,如此一来,每一轮调整都能找出此数组中的最大元素,并将其放在数组末端:

        for i in range(len(nums))[::-1]:
                nums[0], nums[i] = nums[i], nums[0]
                adjustHeap(nums, 0, i)

        注意:每完成完一轮调整堆,下一次需要调整的数组将不会包括已排序好的元素。

3)调整堆函数(adjustHeap)需要不断判断当前结点的左右结点是否均小于该结点,若出现某一结点大于父结点,则需要将更大的元素调整至父结点,形成一个小型的大顶堆,不断调整至整棵二叉树为一个大顶堆。

        if lchild < length and nums[lchild] > nums[largest]:
            largest = lchild
        if rchild < length and nums[rchild] > nums[largest]:
            largest = rchild
        if largest != i:
            nums[largest], nums[i] = nums[i], nums[largest]
            adjustHeap(nums, largest, length)

        需要注意的是,在交换完新的更大结点后要重新进行堆调整,以确保每一个小堆均为一个大顶堆。 

4)算法图解:

Sorting Algorithms in Python (排序算法),排序算法,算法,数据结构,python

Sorting Algorithms in Python (排序算法),排序算法,算法,数据结构,python

图4 堆排序算法图解(图源@独影月下酌酒)

五、插入排序

插入排序思想很简单,取出一个元素,在已排好序的数组中找到自己要插入的位置放入即可。最好时间复杂度为O(n),平均时间复杂度为O(n²),最差时间复杂度为O(n²)。

代码:

def insertSort(nums):
	for i in range(len(nums) - 1):
		curNum, preIndex = nums[i + 1], i
		while preIndex >= 0 and curNum < nums[preIndex]:
			nums[preIndex + 1] = nums[preIndex]
			preIndex -= 1
		nums[preIndex + 1] = curNum
	return nums

解释:

1)curNum和preIndex分别为当前需要插入的元素和其前一个元素下标,若当前元素小于前一个元素,说明该元素应该插在前一个元素之前,即前一个元素需要后移一位,后移完成,preIndex下标需向前移动一位,继续判断当前元素和前一个元素的大小关系,直到与第一个元素比较完成后确定curNum最终应该插入的位置 。

        while preIndex >= 0 and curNum < nums[preIndex]:
            nums[preIndex + 1] = nums[preIndex]
            preIndex -= 1
        nums[preIndex + 1] = curNum

        需要注意的是,在最后放curNum时,由于最后一次判断已将preIndex前移了一位,故此时应插入的位置为preIndex + 1。

2)算法图解:

Sorting Algorithms in Python (排序算法),排序算法,算法,数据结构,python

Sorting Algorithms in Python (排序算法),排序算法,算法,数据结构,python

Sorting Algorithms in Python (排序算法),排序算法,算法,数据结构,python

Sorting Algorithms in Python (排序算法),排序算法,算法,数据结构,python

Sorting Algorithms in Python (排序算法),排序算法,算法,数据结构,python

图5 插入排序算法图解(图源@独影月下酌酒) 

六、希尔排序

希尔排序本质上是插入排序的一种,思想同插入排序一样,不同的的是,希尔排序会先分组,接着组内快速排序,随后不断缩小组间距直至所有元素排序完成。最好时间复杂度为O(n),平均时间复杂度为O(n²),最差时间复杂度为O(n²)。

代码:

def shellSort(nums):
	gap = len(nums) // 2
	while gap:
		for i in range(gap, len(nums)):
			curNum, preIndex = nums[i], i - gap
			while preIndex >= 0 and curNum < nums[preIndex]:
				nums[preIndex + gap] = nums[preIndex]
				preIndex -= gap
			nums[preIndex + gap] = curNum
		gap //= 2
	return nums

解释:

1)gap即为组间距,希尔排序主体仍是快速排序,不断调整组间距直至组间距为0:

        while gap:
                for i in range(gap, len(nums)):
                    curNum, preIndex = nums[i], i - gap
                    while preIndex >= 0 and curNum < nums[preIndex]:
                        nums[preIndex + gap] = nums[preIndex]
                        preIndex -= gap
                    nums[preIndex + gap] = curNum
                gap //= 2
       return nums

        注意:与简单的插入排序不同的是,希尔排序的前一个元素下标为 i - gap。

2)算法图解:

Sorting Algorithms in Python (排序算法),排序算法,算法,数据结构,python

图6 希尔排序算法图解(图源@独影月下酌酒)  

七、归并排序

归并排序的核心思想即是分而治之,先将数组从中间分为左右两个数组,对左右两个数组进行归并排序后合并左右两个数组即可。

代码:

def mergeSort(nums):

	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 = result + left[i:] + right[j:]
		return result

	if len(nums) <= 1:
		return nums

	mid = len(nums) // 2
	left = mergeSort(nums[:mid])
	right = mergeSort(nums[mid:])
	return merge(left, right)

解释:

1)若数组长度<=1则无需排序返回数组本身即可。

2)将需要排序的数组一分为二,分别进行归并排序,即左右子数组分别进行递归(mergeSort)得到两个排序好的数组,最后合并这两个数组即可。

3)合并左右两个数组即设置两个指针分别遍历两个数组,取两者中最小值加入结果数组即可,直到某个数组被遍历完,只需把另一个数组的剩余元素加入结果数组即可(因为两个数组都已事先被排序好了):

        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 = result + left[i:] + right[j:]
        return result

4)算法图解:

Sorting Algorithms in Python (排序算法),排序算法,算法,数据结构,python

图7 归并排序算法图解(图源@独影月下酌酒)   

八、桶排序

桶排序即将数组元素根据某种映射放在各个桶里,先在桶内进行排序,然后将排序好的元素拼接起来即可。最好时间复杂度为O(n+k),最差时间复杂度为O(n²),平均时间复杂度为O(n+k)。

def bucketSort(nums):

	def insertSort(nums):
		for i in range(len(nums) - 1):
			curNum, preIndex = nums[i + 1], i
			while preIndex >= 0 and curNum < nums[preIndex]:
				nums[preIndex + 1] = nums[preIndex]
				preIndex -= 1
			nums[preIndex + 1] = curNum
		return nums

	bucketSize = 4
	bucketCount = (max(nums) - min(nums)) // bucketSize + 1
	buckets = [[] for _ in range(bucketCount)]
	for num in nums:
		buckets[(num - min(nums)) // bucketSize].append(num)
	nums.clear()
	for bucket in buckets:
		insertSort(bucket)
		nums.extend(bucket)
	return nums

解释:

1)根据桶大小和元素分布确定桶个数,初始化桶内元素:

        bucketSize = 4

        bucketCount = (max(nums) - min(nums)) // bucketSize + 1        

        buckets = [[] for _ in range(bucketCount)] 

2)判断数组元素应该放在哪个桶,将元素全都装桶后清空数组方便放后续排序好的元素:

        for num in nums:
                buckets[(num - min(nums)) // bucketSize].append(num)
        nums.clear()

3)元素装桶完成后进行桶内元素排序,本文桶内元素用的插入排序,然后将排序好的元素全部一起extend到原数组中:

        for bucket in buckets:
                insertSort(bucket)
                nums.extend(bucket)

4)算法图解:

Sorting Algorithms in Python (排序算法),排序算法,算法,数据结构,python

 图8 桶排序算法图解(图源@独影月下酌酒)   

九、基数排序

基数排序是特殊的桶排序,其根据元素每位数字来分配桶(桶个数为10,分别对应各位取值0~9),按照先低位排序后高位排序的顺序依次排序直到元素有序即可,排序轮次即为数组中最大元素的位数。最好时间复杂度为O(n×k),最差时间复杂度为O(n×k),平均时间复杂度为O(n×k)。

代码:

def radixSort(nums):
	mod, div = 10, 1
	mostBit = len(str(max(nums)))
	buckets = [[] for _ in range(mod)]
	
	while mostBit:
		for num in nums:
			buckets[num // div % mod].append(num)

		i = 0
		for bucket in buckets:
			while bucket:
				nums[i] = bucket.pop(0)
				i += 1
		div *= 10
		mostBit -= 1
	return nums

解释:

1)mod和div用于取元素各个位数的取值,mostBit是轮次(即元素最大值的位数),buckets个数为10,分别对应各位取值0~9。

2)先将数组中每个元素放到对应桶中,然后按序弹出元素完成第一轮低位排序,接着进行第二轮高位排序,直到所有位均排序完成,此时数组排序完成:    

        while mostBit:
                for num in nums:
                    buckets[num // div % mod].append(num)

                i = 0
                for bucket in buckets:
                    while bucket:
                        nums[i] = bucket.pop(0)
                        i += 1
                div *= 10
                mostBit -= 1

3)算法图解:

Sorting Algorithms in Python (排序算法),排序算法,算法,数据结构,python

Sorting Algorithms in Python (排序算法),排序算法,算法,数据结构,python

Sorting Algorithms in Python (排序算法),排序算法,算法,数据结构,python

 图9 基数排序算法图解(图源@独影月下酌酒)

附上@独影月下酌酒的博客以供参考学习:

Python实现十大排序算法_python排序-CSDN博客文章来源地址https://www.toymoban.com/news/detail-852336.html

到了这里,关于Sorting Algorithms in Python (排序算法)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • Python篇——数据结构与算法(第四部分:希尔排序及其讨论、计数排序、桶排序、基数排序)

    希尔排序(shell sort)是一种分组插入排序算法 首先取一个整数d1=n/2,将元素分为d1个组,每组相邻两元素之间距离为d1,在各 组内 进行直接插入排序 取第二个整数d2=d1/2,重复上述分组排序过程,知道di=1,即所有元素在同一组内进行直接插入排序。 希尔排序每趟并不使某些

    2024年02月07日
    浏览(42)
  • ⌈算法进阶⌋图论::拓扑排序(Topological Sorting)——快速理解到熟练运用

    目录  一、原理 1. 引例:207.课程表  2. 应用场景 3. 代码思路 二、代码模板 三、练习 1、210.课程表Ⅱ🟢 2、2392.给定条件下构造举证🟡 3、310.最小高度树🟡 4、 2603.收集树中金币 🔴 1. 引例:207.课程表 就如大学课程安排一样,如果要学习数据结构与算法、机器学习这类课程

    2024年02月11日
    浏览(48)
  • 【数据结构与算法】排序算法(选择排序,冒泡排序,插入排序,希尔排序)

    基本概念这了就不浪费时间解释了,这四种都是很简单的排序方式,本专栏后续文章会出归并排序,计数排序,快速排序,堆排序,桶排序等排序算法,今天这篇文章中给出选择排序,冒泡排序,插入排序和希尔排序的实现; 如果发现文章中有错误,还请大家指出来,我会非

    2024年02月15日
    浏览(86)
  • 数据结构和算法笔记4:排序算法-归并排序

    归并排序算法完全遵循分治模式。直观上其操作如下: 分解:分解待排序的n个元素的序列成各具n/2个元素的两个子序列。 解决:使用归并排序递归地排序两个子序列。 合并:合并两个已排序的子序列以产生已排序的答案。 我们直接来看例子理解算法的过程,下面是要排序

    2024年01月21日
    浏览(64)
  • 【数据结构与算法】十大经典排序算法-希尔排序

    🌟 个人博客: www.hellocode.top 🏰 Java知识导航: Java-Navigate 🔥 CSDN: HelloCode. 🌞 知乎 :HelloCode 🌴 掘金 :HelloCode ⚡如有问题,欢迎指正,一起学习~~ 希尔排序是一种插入排序的改进版本,旨在解决插入排序在处理大规模数据时的效率问题。通过将数组分为多个子序列并对

    2024年02月12日
    浏览(80)
  • 【数据结构与算法】十大经典排序算法-快速排序

    🌟 个人博客: www.hellocode.top 🏰 Java知识导航: Java-Navigate 🔥 CSDN: HelloCode. 🌞 知乎 :HelloCode 🌴 掘金 :HelloCode ⚡如有问题,欢迎指正,一起学习~~ 快速排序(Quick Sort)是一种高效的排序算法,是对冒泡排序的优化。它采用分治法(Divide and Conquer)的思想,将待排序序列

    2024年02月13日
    浏览(65)
  • 【数据结构与算法】十大经典排序算法-冒泡排序

    🌟 个人博客: www.hellocode.top 🏰 Java知识导航: Java-Navigate 🔥 CSDN: HelloCode. 🌴 掘金 :HelloCode 🌞 知乎 :HelloCode ⚡如有问题,欢迎指正,一起学习~~ 冒泡排序(Bubble Sort)是一种简单的排序算法,它通过重复地交换相邻元素的位置来将最大(或最小)的元素逐步“冒泡”到

    2024年02月14日
    浏览(75)
  • 【数据结构与算法】十大经典排序算法-插入排序

    🌟 个人博客: www.hellocode.top 🏰 Java知识导航: Java-Navigate 🔥 CSDN: HelloCode. 🌞 知乎 :HelloCode 🌴 掘金 :HelloCode ⚡如有问题,欢迎指正,一起学习~~ 插入排序(Insertion Sort)是一种简单直观的排序算法,其基本思想是将一个记录插入到已排好序的有序序列中,直到所有记录

    2024年02月13日
    浏览(83)
  • 【数据结构与算法】排序算法:冒泡排序,冒泡排序优化,选择排序、选择排序优化

    目录 一、冒泡排序 1、冒泡排序思想 2、冒泡排序算法的性能分析 代码实现: 二、选择排序 1、选择排序思想 2、选择排序算法的性能分析  代码实现: 1、冒泡排序思想 冒泡排序的基本思想是通过相邻元素之间的比较和交换来逐步将最大(或最小)的元素移到右边(或左边

    2024年01月19日
    浏览(50)
  • 数据结构——排序算法——归并排序

    在第二个列表向第一个列表逐个插入的过程中,由于第二个列表已经有序,所以后续插入的元素一定不会在前面插入的元素之前。在逐个插入的过程中,每次插入时,只需要从上次插入的位置开始,继续向后寻找插入位置即可。这样一来,我们最多只需要将两个有序数组遍历

    2024年02月09日
    浏览(47)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包