一:三种比较LOW的排序算法
1、冒泡排序:
冒泡算法的时间复杂度为o(n2),有两个循环,外层循环为趟数,循环的趟数为数组长度值减一,因为最后剩一个元素时,不用比较了,所以减一(趟数大了,超过这个数计算结果仍然正确,只是计算的时间会加长)。内层循环为下标移动比较的范围,一次比较选择两个下标因此(j+1)为每一趟比较的后一个数,j+1最多到达每一趟的最后一个元素。
代码实现:
def bubble_sort(li):
"""
升序排列,降序排列把加号改为减号
:param li: 输入的乱序列表
:return: 原地改变列表的值
"""
# 趟数,比列表长度少1,为最后个元素下标
for i in range(len(li)-1):
# j的循环范围,j在j+1前,为每趟循环的最后元素位置,第一次循环时,两个range内的值相等
for j in range(len(li)-i-1):
if li[j] > li[j+1]:
li[j], li[j+1] = li[j+1], li[j]
2、选择排序
两种写代码的思路:
1、依次将该元素和后面的元素比较,如果出现后面的元素小于前面的元素则交换,一趟比较完成后,往后移,再依次比较。
2、找到需要比较的元素中最小的元素,将最小元素和需要保存该元素的位置的元素交换
代码实现:
1、
def selection_sort(li):
"""
选择排序,
:param li: 输入乱序列表
:return: 原地排序
"""
for i in range(len(li)-1):#需要确定的最小元素的位置,该位置之前有序区。开始时,在0号元素之前没有元素,所有的均为无序区
for j in range(i+1,len(li)):#上述位置后的元素位置,在上述位置和之后的位置为无序区
if li[i] > li[j]:
li[i], li[j] = li[j], li[i]
2、
def selection_sort1(li):
for i in range(len(li)-1):
temp = li[i]
a = i
for j in range(i+1,len(li)):
if temp > li[j]:
temp = li[j]
a = j
li[a] = li[i]
li[i] = temp
相比较第二种思路,思路比较麻烦,代码也比较麻烦。不用管第二种,知道就行。第二种方法多了中间变量,有点类似于c语言的交换,这种写法更适合c语言。
3、插入排序
先维持一个有序列表,再选择一个元素插入到具体位置,类似于打牌时插入扑克牌。
def insertion_sort(li): """ 插入排序; 思路:从第二个位置开始取数,取得的数自动加在最后面一个位置,从最后位置开始依次比较相邻位置数的大小。 如果后一个位置比前一个位置小,这交换两个数,(这儿类似于冒泡),这种思路写法简便 :param li: :return: """ for i in range(1,len(li)): for j in range(i-1,-1,-1): if li[j+1] < li[j]: li[j+1], li[j] = li[j], li[j+1]
二:
1、快速排序
快速排序利用的思想为分治法也就是递归,快速排序的优点,1期望时间复杂度为o(nlog(n));2、为原地排序
代码步骤
1、取出列表的第一个元素,归位,得到归位后该元素的在列表中的位置返回
2、递归该元素左右列表
3、终止条件为列表,left,right指针相等,即列表中只有一个元素
第一步是关键,也较难理解。
代码为:
def partition(li,left,right): """ :param li: 需要排序的列表 :param left: 需要排序的最左边位置 :param right: 需要排序的最右边位置 :return: 最左边元素归位的位置 """ temp = li[left] while left < right: while left < right and li[right] >= temp: right = right - 1 li[left] = li[right] while left < right and li[left] <= temp: left = left + 1 li[right] = li[left] li[left] = temp return left def quick_sort(li,left,right): """ :param li: 需要排序的列表 :param left: 需要排序的最左边位置 :param right: 需要排序的最右边位置 :return: 原地排序,无返回值 """ # 递归结束条件, if left < right: # 归位第一个元素,返回值为元素在列表中的位置 q = partition(li,left,right) # 递归左右,当不满足left<right条件时,结束 quick_sort(li,left,q-1) quick_sort(li,q+1,right)
2、堆排序
堆排序需要掌握的一些知识点:
树的一些概念
根节点、叶子节点、
树的深度:树的深度也就是树的层数
树的度:树的度为所有节点中度最大的一个的度,节点的度就是节点的分支数。
孩子节点/父亲节点,子树;
二叉树:度不超过2的树。分左右孩子;
两种特殊的二叉树:满二叉树,完全二叉树;
满二叉树:每一层的节点都达到最大,不能再增加了的二叉树,称为满二叉树;
完全二叉树:满二叉树从后依次拿走节点,满二叉树也是完全二叉树。
完全二叉树,父节点和孩子节点的下标关系,父节点下标为n时,左孩子节点为2n+1,右孩子节点为2n+2;孩子节点下标为m时,父节点下标为(m-1)//2
二叉树的存储方式:
1、链式存储方式
2、顺序存储方式
大根堆:是一个完全二叉树,满足任意一节点都大于其孩子节点。
小根堆:是一个完全二叉树,满足任意一节点都小于其孩子节点。
代码如下:
def adjust(li,low,high): """ 向下调整的函数 :param li: 需要调整的列表 :param low: 指向根的位置 :param high: 需要调整的堆的最大位置 :return: 原地调整列表,无返回值 """ i = low j = 2 * i + 1 while j <= high: if j+1 <= high and li[j+1] > li[j]: j = j + 1 if li[i] < li[j]: li[i],li[j] = li[j],li[i] i = j j = 2 * i + 1 else: break def heap_sort(li): """ 堆排序 :param li: 需要排序的堆 :return: 原地排序,无返回值 """ # 建堆 n = len(li) for i in range((n-1)//2,-1,-1): adjust(li,i,n-1) # 出数 for j in range(n-1,-1,-1): li[0],li[j] = li[j],li[0] adjust(li,0,j-1)
在python中有内置的堆排序模块heapq
建堆:原地,建立的是小根堆
heapq.heapify(li)
往建好的堆中插入值:
heapq.heappush(li,value)
返回堆中最小的值,就是挨个出数:
heapq.heappop(li)
heapq.nlargest(n,li)# 返回堆中前n大的值
heapq.nsmallest(n,li)# 返回堆中前n小的值
topk问题解决
1、先排好序,再取前k个值,时间复杂度nlog(n)
2、lowb3人组思路,时间复杂度nk
冒泡k次,选择k次,取k长度列表,排序;取值和列表中的值依次比较,比最后个小,则和最后个交换,再排序。
3、堆排序思路,时间复杂度nlog(k)
先建立小根堆,再和堆顶值比较,比他大则交换,在调整。这样就是前k大的。
3、归并排序
代码:
def merge(li,low,mid,high): """ 一次合并操作,在合并前,low-mid是有序的;mid+1-high也是有序的 :param li: 需要操作的列表 :param low: 需要操作的列表中的左边下标 :param mid: 需要操作的列表中的中间下标,mid是low和high的中间值mid =(low + high) // 2,mid写出来方便理解和思路理清 :param high: 需要操作的列表中的右边下标 :return: """ i = low j = mid + 1 temp_list = [] while i <= mid and j <= high: if li[i] <= li[j]: temp_list.append(li[i]) i += 1 else: temp_list.append(li[j]) j += 1 while i <= mid: temp_list.append(li[i]) i += 1 while j <= high: temp_list.append(li[j]) j += 1 li[low:high+1] = temp_list def merge_sort(li,low,high): if low < high: mid = (low + high) // 2 merge_sort(li,low,mid) merge_sort(li,mid+1,high) merge(li,low,mid,high)
归并排序是采用分治策略的一个很好例子。
三、线性时间排序
1、计数排序
需要排序的数据在一定范围内,通过计数来排序:
def count_sort(li, min_num=0, max_num=100): """ 基本思想:列表的最大值和最小值在一个范围内,开辟一个新的列表 :param li: 输入列表 :param min_num: 输入列表中的最小值 :param max_num: 输入列表中的最大值 :return: 返回排序好的列表 """ # 生成一个列表,列表中所有元素的初始值为0,元素个数为所有最小值到最大值之间所有可能的正整数。 count = [0 for i in range(min_num,max_num+1)] # 生成新的列表中,元素的位置对应函数输入列表的值,对其值进行计数 for value in li: count[value - min_num] += 1 # 创建新列表,接收排序后的值 li.clear() # 循环遍历计数列表,添加统计的个数个索引值(即传入列表中的值) for k,t in enumerate(count): for m in range(t): li.append(k + min_num) return li
2、桶排序
def bucket_sort(li,bucket_num=10): """ 基本思想:列表根据最大值和最小值,依次有序均分为bucket_num个桶,将每个桶排序,再将排序后的桶合并。 :param li: 传入需要排序的列表 :param bucket_num: 创建的桶的个数 :return: 返回排序号的列表 """ # 取得列表中的最大值和最小值 max_num = max(li) min_num = min(li) # 创建bucket_num个桶 bucket_list = [[] for i in range(bucket_num)] # 将li列表中的数据装入桶中,并对每个桶进行排序操作 bucket_length = (max_num - min_num)/bucket_num for value in li: k = int((value - min_num)//bucket_length) if k == bucket_num: k = bucket_num - 1 bucket_list[k].append(value) # 对每个桶进行排序 for i in range(bucket_num): if len(bucket_list[i]) > 0: quick_sort(bucket_list[i],0,len(bucket_list[i])-1) # 将桶中的数据依次添加到一个列表中并返回。 result = [] for item in bucket_list: for value in item: result.append(value) return result
3、基数排序
def radix_sort(li): """ 基数排序的思想基于关键字排序,就是把次关键的先排好序再排序关键的因素,保证排序是稳定的排序,这样得到的排序列表就是根据关键 因素的排序,如果关键因素相同的则是根据次关键因素排序 :param li: 需要排序的序列 :return: 排序好的序列,不是原地排序,因此需要返回值 """ i = 0 while (max(li)//(10**i)) > 0: # 往干净的十个桶里放数据 bucket_list = [[] for i in range(10)] for j in range(len(li)): k = (li[j]//(10**i))%10 bucket_list[k].append(li[j]) # 往干净的列表中放数据 li = [] for bucket in bucket_list: for item in bucket: li.append(item) # 调整放在根据哪一位放在桶中,和循环 i += 1 return li
四、希尔排序
def insert_sort_gap(li,gap): """ 插入排序,间隔gap; 思路:从第二个位置开始取数,取得的数自动加在最后面一个位置,从最后位置开始依次比较相邻位置数的大小。 如果后一个位置比前一个位置小,这交换两个数,(这儿类似于冒泡),这种思路写法简便 :param li: :return: """ for i in range(1,len(li)): temp = li[i] j = i - gap # j 表示前面一个 while j >= 0 and li[j] > temp: li[j + gap] = li[j] j -= gap li[j+gap] = temp def shell_sort(li): """ 希尔排序,d为gap,最后d=1,就是插入排序;希尔排序的思想就是让整体逐渐有序 :param li: :return: """ d = len(li)//2 while d > 0: insert_sort_gap(li,d) d = d // 2