排序算法总结(python实现)

news/2024/12/18 13:13:25/

前言

算法>排序算法是一类常见的算法,在学习算法的过程中,都会学习这些算法>排序算法的实现。尽管现在大多数程序语言以及扩展包中对算法>排序算法进行了封装,只要调用接口函数即可实现算法。学习和总结算法>排序算法对于理解算法思维还是很有帮助的。因此本文在学习了相关资料后对常见算法进行的总结。

算法>排序算法

算法>排序算法是指将一组无序的数组,按照一定的规则,变成有序的数组。

数组的初始状态会影响算法>排序算法,一般可分为最坏情况,平均情况,和接近有序的情况。衡量算法>排序算法复杂度通常使用的是平均情况或最坏情况下的算法复杂度。

排序按数组逐渐增大或减小可分为升序和降序。对于算法而言,它们是对称的。因此只需要考虑其中一种情况即可。为了简单起见,本文考虑数组升序的排序。

1.冒泡排序

冒泡排序

思路

冒泡排序的思路是将数组中的元素,通过交换相邻元素,将大的元素逐渐移到数组的后面。

实例

待排序序列:[4 3 2 1]
第一轮冒泡
初始:[4 3 2 1]
第一次:[ 3 \color{red}{3} 3 4 \color{red}{4} 4 2 1]
第二次 [3 2 \color{red}{2} 2 4 \color{red}{4} 4 1]
第三次 [3 2 1 \color{red}{1} 1 4 \color{red}{4} 4]

第二轮
初始:[3 2 1 4]
第一次:[ 2 \color{red}{2} 2 3 \color{red}{3} 3 1 4]
第二次:[2 1 \color{red}{1} 1 3 \color{red}{3} 3 4]

第三轮
初始:[2 1 3 4]
第一次:[ 1 \color{red}{1} 1 2 \color{red}{2} 2 3 4]

代码

python">a = [4, 3, 2, 1]
def bubble_sort(a):n = len(a)for i in range(1,n,1):#print("第{}轮初始状态".format(i))#print(a)for	j in range(0,n-i,1):# print("第{}轮第{}次".format(i,j+1))if a[j] > a[j+1]:a[j],a[j+1] = a[j+1],a[j]#print(a)return a

算法复杂度分析:

对于数组元素大小n=4的时候,以交换为基本操作,需要3+2+1次。
所以算法时间复杂度为 O ( n 2 ) O(n^2) O(n2)
空间复杂度 O ( 1 ) O(1) O(1)

提前终止的冒泡排序

如果冒泡排序在一轮中没有发生交换说明该序列已经为一个有序序列可以提前终止排序.因此可以添加一个标志位。

python">a = [4, 3, 2, 1]
def bubble_sort(a):n = len(a)for i in range(1,n,1):no_swap_flag = Truefor	j in range(0,n-i,1):  if a[j] > a[j+1]:a[j],a[j+1] = a[j+1],a[j]no_swap_flag = Falseif no_swap_flag = True:breakreturn a

2.插入排序

思路:

选择排序的过程为在数组选择一个元素,往前插入到合适的位置。

实例

[4 3 2 1]
第一轮 选中3。3的位置空出来,用来移动前面的元素。3比4小,4往后移动到3这,然后3放到4的位置。相当于3插入到4前面。

第一轮 [4 3 2 1]
初始状态 :选中3。3的位置空出来用于移动前面的元素, [4 空 2 1]
第一次比较:3小于4,4向右移动到空的位置。
[空 4 2 1]没有其他元素了。所以3放入到空的这个位置上。
得到 [3 4 2 1]

第二轮 [3 4 2 1]
初始状态,选中2,2的位置空出来用于移动前面的元素,[3 4 空 1]
第一次 2比4小,4往后移动到空的位置。[3 空 4 1]
第二次 2比3小,3往后移动一个位置。[空 3 4 1]
第三次 没有其他元素,2放到空的位置。[2 4 3 1]

第三轮 [2 4 3 1]
初始状态,选中1,1的位置空出来用于移动前面的元素,[2 3 4 空]
第一次 1比4小,4往后移动到空的位置。[2 3 空 4 ]
第二次 1比3小,3往后移动一个位置。[2 空 3 4 ]
第三次 1比2小,2放到空的位置。[空 2 3 4]

上述看上去有点像冒泡。换个例子[4 2 3 1]模拟一下可以发现不同。移动3的时候不用移动到最左边。

实例2

[4 2 3 1]
第一轮 选中3。3的位置空出来,用来移动前面的元素。3比4小,4往后移动到3这,然后3放到4的位置。相当于3插入到4前面。

第一轮 [4 2 3 1]
初始状态 :选中2。2的位置空出来用于移动前面的元素, [4 空 3 1]
第一次比较:2小于4,4向右移动到空的位置。
[空 4 3 1]没有其他元素了。所以2放入到空的这个位置上。
得到 [2 4 3 1]

第二轮 [2 4 3 1]
初始状态,选中3,2的位置空出来用于移动前面的元素,[2 4 空 1]
第一次 3比4小,4往后移动到空的位置。[2 空 4 1]
第二次 3比2大,3插入到当前位置。[2 3 4 1]

第三轮 [2 3 4 1]
初始状态,选中1,1的位置空出来用于移动前面的元素,[2 3 4 空]
第一次 1比4小,4往后移动到空的位置。[2 3 空 4 ]
第二次 1比3小,3往后移动一个位置。[2 空 3 4 ]
第三次 1比2小,2放到空的位置。[空 2 3 4]

从上面的模拟可以发现,单轮结束条件为两种:
第一种:选中的元素大于等于前一个元素。在该位置放置选中的元素
第二种:到了数组最开头。在数组开头放置选中的元素。

代码

python">def insert_sort_version1(a):n = len(a)for i in range(1, n, 1):temp = a[i]for j in range(i - 1, -1, -1):if temp < a[j]:a[j + 1] = a[j]else:a[j + 1] = tempbreakelse:a[0] = tempreturn adef insert_sort_version2(a):n =len(a)for i in range(1,n,1):temp = a[i]j = i - 1while(j>=0 and a[j]<temp):a[j+1] = a[j]j = j -1a[j+1] = tempreturn a

算法复杂度分析:

逆序数组的时候和冒泡算法>排序算法类似,所以算法时间复杂度也为 O ( n 2 ) O(n^2) O(n2)
空间复杂度 O ( 1 ) O(1) O(1)

3.选择排序

思路:选择排序是很好理解的,选择最小的放到数组前。在剩下的数组中再选择最小的放在数组前。

实例:

待排序序列:[4 3 2 1]
第一轮:从数组[4 3 2 1]中挑出最小的 1 。与数组第一个位置的4 交换。[1 3 2 4]
第二轮:从数组[3 2 4]中选出最小的2。与数组第二个位置的3交换。[1 2 3 4]
第三轮:从数组[3 4]中选出最小的3。与数组第三个位置3交换。

代码

python">def select_sort(a):n = len(a)for i in range(0, n - 1, 1):min_index = ifor j in range(i + 1, n, 1):if a[j] < a[min_index]:min_index = ja[i], a[min_index] = a[min_index],a[i]return aimport numpy as np
a = np.random.randint(100, size=10)
print(select_sort(a))

算法复杂度分析:

算法时间复杂度也为 O ( n 2 ) O(n^2) O(n2),空间复杂度 O ( 1 ) O(1) O(1)

4.归并排序

思路:先将数组拆成一个个元素,然后合并起来。
实例:[4,3,2,1]

欲对[4,3,2,1]排序,先对左半数组[4,3]和右半数组[2,1]排序,再将[3,4]和[1,2]合并。
欲对[4,3]数组排序,先对左半数组[4]和右半数组[3]排序,再将[4]和[3]合并。
[4]和[3]是基本情况,因此只需要合并即可。
同理[2,1]数组。

python">def merge_sort(a):n = len(a)# 基本情况if n <= 1:return amid = n // 2left = a[:mid]right = a[mid:]left_half = merge_sort(left)right_half = merge_sort(right)n_left = len(left_half)n_right = len(right_half)result = []i = 0j = 0while (i < n_left and j < n_right):if (left_half[i] < right_half[j]):result.append(left_half[i])i = i + 1else:result.append(right_half[j])j = j + 1while (i < n_left):result.append(left_half[i])i = i + 1while (j < n_right):result.append(right_half[j])j =j + 1return result

算法复杂度分析

算法空间复杂度 O ( n ) O(n) O(n),比较好理解,额外需要一个大小为n的result数组来存储元素。
算法的时间复杂度,容易得合并操作为O(n)。递归的表达式 O(T(N)) = 2 O(T(N/2)) + O(N)。根据主定理, a = 2 , b = 2 , n l o g b a = n a= 2,b= 2, n^{log_b a} =n a=2,b=2,nlogba=n 算法复杂度为 O ( n l g ( n ) ) O(n lg(n) ) O(nlg(n))

5.快速排序

思路

数组中挑选一个数,将数组分为两部分,左边都小于这个数,右边都小于这个数。重复这个操作,直到分成的数组只有一个元素。

实例

选取中间的数作为基准。选择2。数组拆成 [1] [2] [4 3]
继续对 [4 3] 进行操作 分为[],[3],[4]
当数组为[]或者单个元素的时候,返回。
将排好顺序的数组合并起来。因为左边都小于这个数,右边都大于这个数。合并起来很容易。

代码

python">def quick_sort(a):n = len(a)if n <= 1:return amid = n // 2pivot = a[mid] # pivot 中心点,核心枢纽的意思left = [x for x in a if x < select_num]middle = [x for x in a if x == select_num]right = [x for x in a if x > select_num]return quick_sort(left) + middle + quick_sort(right)

这里用到了额外的空间。用来存储left、middle和right数组。所以空间复杂度为O(n).

希望是原地排序。

python">def quick_sort_in_place(a,low,high):def partition(a, low, high):pivot = a[low]while low < high:while low < high and a[high] < pivot:high = high - 1a[low] = a[high]while low < high and a[low] < pivot:low = low + 1a[high] = a[low]a[low] = pivotreturn lowif low < high:pivot_index = partition(a,low,high)quick_sort_in_place(a,low,pivot_index-1)quick_sort_in_place(a, pivot_index + 1,high)

算法复杂度分析

算法空间复杂度 O ( l o g n ) O(log n) O(logn),
算法的时间复杂度。递归的表达式 O(T(N)) = 2 O(T(N/2)) + O(N)。根据主定理, a = 2 , b = 2 , n l o g b a = n a= 2,b= 2, n^{log_b a} =n a=2,b=2,nlogba=n 算法复杂度为 O ( n l g ( n ) ) O(n lg(n) ) O(nlg(n))

6.堆排序

堆一种特殊的数据结构,它有两个显著的属性。它们是:
1.堆的结构属性:堆的元素形成一个完整的有序树。
2.堆的顺序属性:每个父级≥所有子级(包括所有后代)。

数组中任何元素的子元素都可以从父元素的索引计算出来:
l e f t C h i l d I n d e x = 2 ∗ p a r e n t I n d e x + 1 leftChildIndex = 2 * parentIndex + 1 leftChildIndex=2parentIndex+1
r i g h t C h i l d I n d e x = 2 ∗ p a r e n t I n d e x + 2 rightChildIndex = 2 * parentIndex + 2 rightChildIndex=2parentIndex+2
反之,父元素的索引为子元素的索引:
p a r e n t I n d e x = ( c h i l d I n d e x − 1 ) / / 2 parentIndex = (childIndex-1)//2 parentIndex=(childIndex1)//2

python">class MaxHeap:def __init__(self):self.data = []def has_left_child(self,i):return 2*i+1 <= len(self.data)-1def has_right_child(self,i):return 2*i+2 <= len(self.data)-1def has_parent(self,i):return (i-1)//2 <= len(self.data)def left_child(self,i):if self.has_left_child(i):return 2*i+1else:return Nonedef right_child(self,i):if self.has_right_child(i):return 2*i+2else:return Nonedef parent(self,i):if self.has_parent(i):return i-1 //2else:return Nonedef shift_down(self,i):while self.has_left_child(i):max_index = self.left_child(i)if self.has_right_child(i) and self.data[self.right_child(i)] > self.data[self.left_child(i)]:max_index = self.right_child(i)if self.data[i] < self.data[max_index]:self.data[i], self.data[max_index] = self.data[max_index], self.data[i]else:breaki = max_indexdef shift_up(self,i):while self.parent(i):if self.data[self.parent(i)] < self.data[i]:self.data[i], self.data[self.parent(i)] = self.data[self.parent(i)],self.data[i]i = self.parent(i)else:breakdef insert(self,num):self.data.append(num)self.shift_up(len(self.data) - 1)def extract_max(self):if len(self.data) <=0:return Nonemax_data = self.data[0]self.data[0] = self.data[-1]self.data.pop()self.shift_down(0)return max_datadef heapify(self,nums):self.data = numsfor i in range((len(nums)-2)//2,-1,-1):self.shift_down(i)return self.datadef heap_sort(nums):heap = MaxHeap()nums= heap.heapify(nums)result =[]for i in range(len(nums)):result.insert(0,heap.extract_max())return result		

算法复杂度分析

算法空间复杂度 O ( N ) O(N) O(N),
算法的时间复杂度 O ( N l o g N ) O(N logN) O(NlogN) ,一般情况下会比快速排序要慢。

7.基数排序

基数排序(Radix Sort)是一种非比较型整数算法>排序算法,它通过分配和收集的过程来对整数进行排序。基数排序的工作原理是将整数按位数切割成不同的数字,然后按每个位数进行比较排序。通常,基数排序用于整数或字符串的排序。
基数排序的基本步骤如下:
1.确定最大数位数:找出待排序数组中的最大数,并确定它的位数。
2.分配收集:从最低位(个位)开始,对每一位数字进行分配和收集操作。这一步骤会重复进行,直到所有位都被处理过。

###代码

python">def max_digits(nums):max_num = max(nums)digits = 0while max_num > 0:digits += 1max_num //= 10return digitsdef counting_sort_for_radix(nums, position):output = [-1] * len(nums)count = [0] * 10  # 因为每一位数字的范围是0到9# 计算每个数字在当前位上的出现次数for num in nums:index = (num // position) % 10count[index] += 1# 更新count数组,每个元素加上前一个元素的值(计数排序的步骤)for i in range(1, 10):count[i] += count[i - 1]# 构建输出数组for num in reversed(nums):index = (num // position) % 10output[count[index] - 1] = numcount[index] -= 1# 将排序好的数组复制回原数组for i in range(len(nums)):nums[i] = output[i]def radix_sort(nums):# 找到最大数的位数max_digit = max_digits(nums)# 对每一位进行排序position = 1for _ in range(max_digit):counting_sort_for_radix(nums, position)position *= 10# 示例
example_array = [170, 45, 75, 90, 802, 24, 2, 66]
radix_sort(example_array)
print(example_array)

复杂度分析

基数排序的时间复杂度是 O ( n k ) O(nk) O(nk),其中n是待排序元素的数量,k是最大数的位数。基数排序的空间复杂度是 O ( n + k ) O(n + k) O(n+k),因为它需要额外的空间来存储输出数组和计数数组。基数排序适用于整数排序,特别是当k不是很大时,它是一个非常高效的算法

参考文献

[1] 【数据结构】常见八大算法>排序算法(附动图)
[2] 数据结构和算法基础Python语言实现 陈良旭
[3] 六大算法>排序算法:插入排序、希尔排序、选择排序、冒泡排序、堆排序、快速排序
[4] Python基础课:那些面试常见的算法>排序算法


http://www.ppmy.cn/news/1556127.html

相关文章

模拟登录网页

模拟登录与数据采集 今天我们讨论了如何通过 Python 模拟登录并抓取登录后的数据&#xff0c;主要涵盖了以下内容&#xff1a; 模拟登录步骤&#xff1a; 分析登录页面&#xff1a;使用浏览器开发者工具&#xff08;F12&#xff09;分析登录表单&#xff0c;提取表单字段、提…

【echarts】数据过多时可以左右滑动查看(可鼠标可滚动条)

1. 鼠标左右拖动 在和 series 同级的地方配置 dataZoom&#xff1a; dataZoom: [{type: inside, // inside 鼠标左右拖图表&#xff0c;滚轮缩放&#xff1b; slider 使用滑动条start: 0, // 左边的滑块位置&#xff0c;表示从 0 开始显示end: 60, // 右边的滑块位置&#xf…

企业车辆管理系统(源码+数据库+报告)

一、项目介绍 352.基于SpringBoot的企业车辆管理系统&#xff0c;系统包含两种角色&#xff1a;管理员、用户,系统分为前台和后台两大模块 二、项目技术 编程语言&#xff1a;Java 数据库&#xff1a;MySQL 项目管理工具&#xff1a;Maven 前端技术&#xff1a;Vue 后端技术&a…

python基础:(八)文件

目录 一.从文件中读取数据1.1读取整个文件1.2文件路劲1.3逐行读取 二.写入文件 一.从文件中读取数据 各位小伙伴&#xff0c;文件这一块得好好学&#xff0c;多看多敲代码&#xff0c;以后处理数据&#xff0c;写爬虫少不了这个&#xff0c;先从基础&#xff08;简单的&#x…

Loadsh源码分析-filter,find,findLast,reject,partition

lodash源码研读之filter,find,findLast,reject,partition 一、源码地址 GitHub 地址: GitHub - lodash/lodash: A modern JavaScript utility library delivering modularity, performance, & extras.官方文档地址: Lodash 官方文档 二、结构分析 结构框图省略。 三、函…

css 实现呼吸灯效果

先看效果&#xff1a; 动画的结果就想实在呼吸,完整的代码如下&#xff1a; <template><div class"container"><div class"long-breath"></div></div> </template><style lang"less"> html, body{h…

什么是评价搭配

一、评价搭配的概念 评价搭配是指在文本中&#xff0c;由评价词&#xff08;如 “好”“坏”“优秀”“糟糕” 等表达主观意见的词&#xff09;和被评价对象&#xff08;如产品名称、服务类型、人物等&#xff09;组成的语义单元。例如&#xff0c;在 “这部手机的拍照效果很好…

element左侧导航栏

由element组件搭建的左侧导航栏 预览: html代码: <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><title>首页</title><style> /*<!-- 调整页面背景颜色-->*/body{background-colo…