做设计应该看哪些网站,亚马逊查关键词排名工具,免费网站建设ppt模板,网络舆情管控## 排序篇
#### 二路归并排序
- 介绍
- 归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。归并排序是一种稳定的排序方法。将已有序的子序列合并#xff0c;得到完全有序的序列#xff1b;即先使每个子序列…## 排序篇
#### 二路归并排序
- 介绍
- 归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。归并排序是一种稳定的排序方法。将已有序的子序列合并得到完全有序的序列即先使每个子序列有序再使子序列段 间有序。若将两个有序表合并成一个有序表称为2-路归并。
- 算法思路
1. 把长度为n的输入序列分成两个长度为n/2的子序列
2. 对这两个子序列分别采用归并排序
3. 将两个排序好的子序列合并成一个最终的排序序列。
- 复杂度与稳定性
- 空间复杂度
- 时间复杂度
- 最佳情况最佳情况T(n) O(n)
- 最差情况T(n) O(nlogn)
- 平均情况T(n) O(nlogn)
- 属于稳定性排序
- 代码
Python
def merge_array(L, first, mid, last, temp):
合并的函数合并数组# 将序列L[first...mid]与序列L[mid1...last]进行合并
# 对i,j,k分别进行赋值
i, j, k first, mid 1, 0
# 当左右两边都有数时进行比较取较小的数
while i mid and j last: # 等号必须要有否则会出现遗漏
if L[i] L[j]:
temp[k] L[i]
i 1
else:
temp[k] L[j]
j 1
k 1
# 以下两个while只会执行两个
# 如果左边序列还有数
while i mid:
temp[k] L[i]
i 1
k 1
# 如果右边序列还有数
while j last:
temp[k] L[j]
j 1
k 1
# 将temp当中该段有序元素赋值给L待排序列使之部分有序
for x in range(0, k):
L[first x] temp[x] # 将辅助空间的值加入到原数组中对应的位置
def divide_array(L, first, last, temp):
分组
if first last: # 这里不可以等号否则无法递归退出
mid (last-first)//2 first)
# 使左边序列有序
divide_array(L, first, mid, temp)
# 使右边序列有序
divide_array(L, mid 1, last, temp)
# 将两个有序序列合并
merge_array(L, first, mid, last, temp)
# 归并排序的函数
def merge_sort(L):
# 声明一个长度为len(L)的空列表
temp len(L) * [None] # 不能写成temp[]
# 调用归并排序
divide_array(L, 0, len(L) - 1, temp)
return L #### 基数排序
- 介绍
- 基数排序也是非比较的排序算法对每一位进行排序从最低位开始排序复杂度为O(kn),为数组长度k为数组中的数的最大的位数
- 算法思路
1. 取得数组中的最大数并取得位数
2. arr为原始数组从最低位开始取每个位组成radix数组
3. 对radix进行计数排序(利用计数排序适用于小范围数的特点)
- 复杂度与稳定性
- 空间复杂度O(k),辅助空间需要k个队列
- 时间复杂度
- 最佳情况最佳情况T(n) O(n * k)
- 最差情况T(n) O(n * k)
- 平均情况T(n) O(n * k)
- 属于稳定性排序
- 队列先进先出
- 代码
Python
def radix_sort(lst):
基数排序
if not lst:
return lst
RADIX 10
placement 1
# 获取最大值最后为循环退出出口
max_digit max(lst)
while placement max_digit:
# 0到9的柱状桶使用列表表示用于存放基数相同的数据
buckets [list() for _ in range(RADIX)]
# 遍历列表按基数分类放入桶中
for i in lst:
tmp (i // placement) % RADIX
buckets[tmp].append(i)
# 从低到高将桶中数据依次放入到列表中
a 0
# 相同的数据在原列表中靠前分配到桶中时也靠前取出时也先取出b也从0开始所以是稳定性排序
for b in range(RADIX):
buck buckets[b]
for i in buck:
lst[a] i
a 1
# 进入下一个循环
placement * RADIX
return lst ### 交换排序
#### 交换排序之冒泡排序
- 算法思路
1. 将序列当中的左右元素依次比较保证右边的元素始终大于左边的元素( 第一轮结束后序列最后一个元素一定是当前序列的最大值)
2. 对序列当中剩下的n-1个元素再次执行步骤1。
3. 对于长度为n的序列一共需要执行n-1轮比较
- 复杂度与稳定性
- 空间复杂度
- 时间复杂度
- 最佳情况T(n) O(n) 当输入的数据已经是正序时
- 最差情况T(n) O(n2) 当输入的数据是反序时
- 平均情况T(n) O(n2)
- 属于稳定性排序
- 代码
Python
def bubble_sort(collection):
冒泡排序
length len(collection)
for i in range(length - 1):
swapped False
for j in range(length - 1 - i):
if collection[j] collection[j 1]:
swapped True
collection[j], collection[j 1] collection[j 1], collection[j]
# 当某趟遍历时未发生交换则已排列完成跳出循环
if not swapped:
break
return collection - 代码优化方向之一设置一标志性变量pos,用于记录每趟排序中最后一次进行交换的位置。由于pos位置之后的记录均已交换到位,故在进行下一趟排序时只要扫描到pos位置即可。
Python
def bubble_sort(collection):
冒泡排序优化之记录每一趟最后交换的位置
length len(collection)
i length-1
# pos用于记录最后一次交换的位置并将其赋值给i
while i 0:
pos 0
for j in range(i):
if collection[j] collection[j 1]:
pos j
collection[j], collection[j 1] collection[j 1], collection[j]
i pos
return collection - 代码优化方向之二传统冒泡排序中每一趟排序操作只能找到一个最大值或最小值,我们考虑利用在每趟排序中进行正向和反向两遍冒泡的方法一次可以得到两个最终值(最大者和最小者) , 从而使排序趟数几乎减少了一半
Python
def bubble_sort(collection):
冒泡排序优化之正反两方向冒泡
# 标记反向
low 0
# 标记正向比较结束位置
high len(collection)-1
while low high:
# 正向找最大
for j in range(low,high):
if collection[j] collection[j 1]:
collection[j], collection[j 1] collection[j 1], collection[j]
high - 1
# 反向找最小
for j in range(high,low,-1):
if collection[j] collection[j - 1]:
collection[j], collection[j - 1] collection[j - 1], collection[j]
low 1
return collection ### 选择排序
#### 选择排序之简单选择排序
- 算法思路
1. 初始状态无序区为R[1..n]有序区为空
2. 第i趟排序(i1,2,3...n-1)开始时当前有序区和无序区分别为R[1..i-1]和R(i..n)。该趟排序 从当前无序区中-选出关键字最小的记录 R[k]将它与无序区的第1个记录R交换使R[1..i]和R[i1..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区
3. n-1趟结束数组有序化了
- 主要的两层循环
- 第一层循环依次遍历序列当中的每一个元素
- 第二层循环将遍历得到的当前元素依次与余下的元素进行比较符合最小元素的条件则交换
- 复杂度与稳定性
- 空间复杂度
- 时间复杂度
- 最佳情况T(n) O(n2)
- 最差情况T(n) O(n2)
- 平均情况T(n) O(n2)
- 属于不稳定性排序
- 比如[2,2,1]
- 优缺点及应用场景
- 注意与直接插入排序比较当初始表基本有序时选择直接插入排序其时间复杂度O(n)
- 代码
Python
# 简单选择排序的关键点在于从未排序的序列中选择出最小的放在未排序序列的最前端
def select_sort(nums):
简单选择排序
# 依次遍历序列中的每一个元素n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果
for x in range(0, len(nums) - 1):
# 将当前位置的元素定义此轮循环当中的最小值
minimum nums[x]
# 将该元素与剩下的元素依次比较寻找最小元素
for i in range(x 1, len(nums)):
# 当小时才交换则是稳定排序
if nums[i] minimum:
# 每一次比较当发现比当前临时最小值还要小时及时交换更新
nums[i], minimum minimum, nums[i]
# 遍历比较后将比较后得到的真正的最小值赋值给当前位置
nums[x] minimum
return nums #### 选择排序之堆排序
- 算法思路
1. 将初始待排序关键字序列(R1,R2....Rn)构建成大顶堆此堆为初始的无序区
2. 将堆顶元素R[1]与最后一个元素R[n]交换此时得到新的无序区(R1,R2,......Rn-1)和新的有序区(Rn),且满足R[1,2...n-1]R[n]
3. 由于交换后新的堆顶R[1]可能违反堆的性质因此需要对当前无序区(R1,R2,......Rn-1)调整为新堆然后 再次将R[1]与无序区最后一个元素交换得到新的无序区(R1,R2....Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元 素个数为n-1则整个排序过程完成。
- 复杂度与稳定性
- 空间复杂度O(1)
- 时间复杂度
- 最佳情况T(n) O(nlogn)
- 最差情况T(n) O(nlogn)
- 平均情况T(n) O(nlogn)
- 属于不稳定性排序
- 例如L[1,2,2]
- 优缺点及应用场景
- 堆排序需要的辅助空间小于快速排序不会出现快速排序可能出现的最坏情况
- 代码
Python
def heapify(unsorted, index, heap_size):
构建大根堆
# 定义当前节点为临时最大值的索引largest
largest index
# 获取当前节点下标(index)的左右子节点下标
left_index 2 * index 1
right_index 2 * index 2
# 在不超过堆容量时进行左节点与父节点的比较若比父节点大则更新最大值的下标
if left_index heap_size and unsorted[left_index] unsorted[largest]:
largest left_index
# 在不超过堆容量时进行右节点与父节点的比较若比父节点大则更新最大值的下标
if right_index heap_size and unsorted[right_index] unsorted[largest]:
largest right_index
# 若当前节点并不是最大值则进行交换调整同时此处也是递归出口
if largest ! index:
# 将当前节点的值与最大值进行互换即父节点与子节点数据交换
unsorted[largest], unsorted[index] unsorted[index], unsorted[largest]
# 针对交换后的孩子节点的左右孩子节点进行递归调整判断
# 这一步必须要
heapify(unsorted, largest, heap_size)
def heap_sort(unsorted):
堆排序
n len(unsorted)
# 从n // 2 - 1节点处依次构建堆为最后一个叶子节点的父节点
for i in range(n // 2 - 1, -1, -1):
# 总共有n//2次遍历每次遍历都有一个递归函数
heapify(unsorted, i, n)
# 执行循环
# 1. 每次取出堆顶元素置于序列的最后(len - 1, len - 2, len - 3...)
# 2. 调整堆使其继续满足大顶堆的性质注意实时修改堆中序列的长度
for i in range(n - 1, 0, -1):
# i为序列下标从后往前移动所以最大值为于列表的最后
# 将抽象数据结构堆的最大值即索引0位置的数值移动i位置
unsorted[0], unsorted[i] unsorted[i], unsorted[0]
heapify(unsorted, 0, i)
return unsorted ### 插入排序
#### 插入排序之简单插入排序
- 算法思路
1. 从第一个元素开始该元素可以认为已经被排序
2. 取出下一个元素在已经排序的元素序列中从后向前扫描
3. 如果该元素(已排序)大于新元素将该元素移到下一位置
4. 重复步骤3直到找到已排序的元素小于或者等于新元素的位置
5. 将新元素插入到该位置后
6. 重复步骤2~5。
- 主要的两层循环
- 第一层循环遍历待比较的所有数组元素(从第二个元素开始)
- 第二层循环将上层循环选择的元素(selected)与已经排好序的所有元素(ordered)相比较从选择元素的前面一个开始直到数组的起始位置。如果selected ordered那么将二者交换位置继续遍历反之留在原地选择下一个元素
- 复杂度与稳定性
- 空间复杂度O(1)
- 时间复杂度
- 最佳情况输入数组按升序排列。T(n) O(n)
- 最坏情况输入数组按降序排列。T(n) O(n2)
- 平均情况T(n) O(n2)
- 属于稳定性排序
- 优缺点及应用场景
- 代码
PYTHON
# 这种写法时错误的
def insert_sort(nums):
直接插入排序
# 遍历数组中的所有元素其中0号索引元素默认已排序因此从1开始
# 当nums元素数量为空或者1时不会进入for循环
# i为待插入元素的索引位置此次遍历将确认nums[i]应该插入的位置
for i in range(1, len(nums)):
# 将该元素与已排序好的前序数组依次比较如果该元素小则交换
# range(x,0,-1):从x倒序循环到1依次比较
# 每次比较如果小于会交换位置正好按递减的顺序
# 每次内层循环开始时j为待插入元素位置最终循环结束时j即为插入位置
for j in range(i, 0, -1): #这里j时取不到0的
# 判断如果符合条件则交换,并由此处可见直接插入排序为稳定性排序
if nums[j] nums[j - 1]:
# 交换需要辅助空间空间复杂度O(1)交换三次不是真正的插入算法
nums[j], nums[j - 1] nums[j - 1], nums[j]
else:
break
return nums
# 插入算法特点选找到插入点后再插入之前只交换一次而非三次
def insert_sort(nums):
直接插入排序:param nums::return:
# 遍历数组中的所有元素其中0号索引元素默认已排序因此从1开始
# 当nums元素数量为空或者1时不会进入for循环
for i in range(1, len(nums)):
# 将该元素与已排序好的前序数组依次比较如果该元素小则交换
# range(i,0,-1):从i倒序循环到0依次比较
# 每次比较如果小于会交换位置正好按递减的顺序
temp nums[i]
for j in range(i - 1, -1, -1):
# 判断如果符合条件则交换,并由此处可见直接插入排序为稳定性排序
if nums[j] temp:
nums[j 1] nums[j]
elif nums[j] temp:
j 1
break
else:
break
# 最后插入点
nums[j] temp
return nums #### 插入排序之折半插入排序
- 在直接插入排序中查找插入位置时使用二分查找的方式 def binary_insert_sort(nums):
折半插入排序:param nums::return:
# 遍历数组中的所有元素其中0号索引元素默认已排序因此从1开始
# 当nums元素数量为空或者1时不会进入for循环
for i in range(1, len(nums)):
# 二分查找在已排序中寻找待插入位置确定待插入点
left 0
right i - 1
target nums[i]
while left right:
mid (right - left) // 2 left
if nums[mid] target:
left mid 1
else:
right mid - 1
print(left,right)
for j in range(i, right1, -1):
# 交换,并由此处可见折半插入排序为稳定性排序
nums[j], nums[j - 1] nums[j - 1], nums[j]
nums[right1] target
print(nums)
return nums
if __name__ __main__:
binary_insert_sort([5, 3, 2, 2, 0]) #### 插入排序之希尔排序
- 学习基础希尔排序是基于简单插入排序的
- 算法思路
- 复杂度与稳定性
- 空间复杂度O(1)
- 时间复杂度
- 最佳情况
- 最坏情况当n在特定范围时为O(n2)
- 平均情况当n在特定范围时为O(n1.3)
- 属于不稳定性排序
- 优缺点及应用场景
- 适用性只适用于当线性表为顺序存储的情况
- 代码
PYTHON
def shell_sort(nums):
# 初始化gap值此处利用序列长度的一半为其赋值
gap len(nums) // 2
# 第一层循环依次改变gap值对列表进行分组,当gap等于1时进行最后一遍循环
while gap 1:
# 下面利用直接插入排序的思想对分组数据进行排序
# range(gap, len(L)):由于数组下标从0开始所以从gap开始依次比较
# gap分组比较同等的数值可能分部不同组而导致后一组比较后交换而前一组比较后不交换
# 故而破坏稳定性成为不稳定性排序
# 这两个for循环则是一个小型的直接插入排序
for i in range(gap, len(nums)):
# range(i, 0, -gap):从i开始与选定元素开始倒序比较
# 每个比较元素之间间隔gap
for j in range(i, 0, -gap):
# 如果该组当中两个元素满足交换条件则进行交换
if nums[j] nums[j-gap]:
nums[j],nums[j-gap] nums[j-gap],nums[j]
else:
break
gap gap // 2
return nums
# 自定义gap
def shell_Sort(nums):
lens len(nums)
gap 1
# 动态定义间隔序列
while gap lens // 3:
gap gap * 3 1
while gap 0:
for i in range(gap, lens):
curNum, preIndex nums[i], i - gap # curNum 保存当前待插入的数
while preIndex 0 and curNum nums[preIndex]:
nums[preIndex gap] nums[preIndex] # 将比 curNum 大的元素向后移动
preIndex - gap
nums[preIndex gap] curNum # 待插入的数的正确位置
gap // 3 # 下一个动态间隔
return nums 对比记忆
1. 简单选择排序与直接插入排序的区别应用选择稳定性
选取排序算法需要考虑的因素
1. 待排序的元素数量n
2. 元素本身信息量的大小
1. 当n较少时(n 50)直接插入排序或者简单选择排序由于插入排序移动较多当记录本身信息很多时使用简单选择排序
