本文共 8265 字,大约阅读时间需要 27 分钟。
排序算法是一种将一串无规律数据依照特定顺序进行排列的一种方法或思路
队列中有相同的元素,排序前后,这两个相同元素的顺序有没有发生变化。
冒泡排序是一种简单的排序算法。 相邻的元素两两比较。 经过数次比较循环,最终达到一个从小到大(升序)或者从大到小(降序)的有序序列。由于类似于气泡从水底冒出,所以叫“冒泡”排序。
def bubble_sort(lists): n = len(lists) for i in range(n-1,0,-1): count = 0 for j in range(i): if lists[j] > lists[j+1]: lists[j],lists[j+1] = lists[j+1],lists[j] count += 1 if count == 0: breakif __name__ == "__main__": lists = [1,2,3,4,5] print(lists) bubble_sort(lists) print(lists)
选择排序(Selection sort)是一种简单直观的排序算法。
简单来说就是从无序队列里面挑选最小的元素,和无序队列头部元素替换(放到有序队列中),最终全部元素形成一 个有序的队列。首先在未排序序列中找到最小(大)元素,和无序队列的第一个元素替换位置,(即形成有序队列) 以此类推,直到所有元素全部进入有序队列,即排序完毕。
选择排序的主要特点与元素替换有关。 每次移动一个元素,就有一个元素放到有序队列, n个元素的无序队列最多进行(n-1)次交换,就可以形成有序队列。 如果整个队列已排序,那么它不会被移动。def sortlist(lists): n = len(lists) for i in range(n-1,0,-1): index = 0 for j in range(i+1): if lists[j] > lists[index]: index = j lists[i],lists[index] = lists[index],lists[i]if __name__ == "__main__": li = [54,26,93,17,77,31,44,77,20,34,67,99,87,33,43,88,98,89] print(li) sortlist(li) print(li)
def selection_sort(lists): n = len(lists) for i in range(n-1): min_index = i for j in range(i+1,n): if lists[min_index] > lists[j]: min_index = j if min_index != i: lists[i],lists[min_index] = lists[min_index],lists[i]if __name__ == "__main__": lists = [54,26,93,17,77,31,44,55,20] print(lists) selection_sort(lists) print(lists)
插入排序也是一种简单的排序算法。
简单来说,先定义一个有序队列,然后把无序队列中的第一个元素放到有序队列的 合适位置,重复操作,直至形成一个完整的有序队列。 生活实例: 打扑克1、构建有序序列
2、选择无序队列的第一个元素,先放在有序队列末尾,然后进行冒泡排序,放到指定的位置 3、循环2步,直到无序队列中所有元素全部进入有序队列的合适位置def insert_sort(lists): n = len(lists) for i in range(n): for j in range(i,0,-1): if lists[j] < lists[j-1]: lists[j],lists[j-1] = lists[j-1],lists[j] else: breakif __name__ == "__main__": lists = [54,26,93,17,77,31,44,55,20] print(lists) insert_sort(lists) print(lists)
希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序,是插入排序算法的一种高效的改进版本。
特点:
下标增量分组,对小组元素进行插入排序 下标增量的特点: 第一次分组,gap=n/2 , 从第二次分组,gap=gap/2, 最后一次分组gap=1 整个分组过程就是:递归def shell_sort(lists): n = len(lists) gap = n >> 1 while gap >= 1 : for i in range(gap,n): for j in range(i,0,-gap): if lists[j] > lists[j-gap]: lists[j-gap],lists[j] = lists[j],lists[j-gap] else: break gap >>= 1if __name__ == "__main__": lists = [54,26,93,17,77,31,44,77,20] print(lists) shell_sort(lists) print(lists)
def shell_sort(alist): # 获取列表的长度 n = len(alist) # 获取 gap 的偏移值 gap = n // 2 # 只要 gap 在我们的合理范围内,就一直分组下去 while gap >= 1: # 指定 i 下标的取值范围 for i in range(gap, n): # 对移动元素的下标进行条件判断 while (i - gap) >= 0: # 组内大小元素进行替换操作 if alist[i] < alist[i - gap]: alist[i], alist[i - gap] = alist[i - gap], alist[i] # 更新迁移元素的下标值为最新值 i = i - gap # 否则的话,不进行替换 else: break # 每执行完毕一次分组内的插入排序,对 gap 进行/2 细分 gap = gap // 2if __name__ == "__main__": li = [54,26,93,17,77,31,44,77,20] print(li) shell_sort(li) print(li)
我们知道希尔排序的本质就是插入排序,所以最坏也就是插入排序的最坏时间复杂度了,也就是O(n2)
快速排序,又称划分交换排序,从无序队列中挑取一个元素,把无序队列分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行, 以此达到整个数据变成有序序列。
通过上面对快速排序的简介,我们知道了,快速排序主要包括以下两方面:
挑元素划分组、整体递归分组特点:
1、因为是无序队列,所以位置可以随机挑 2、临时划分一个空间,存放我们挑选出来的中间元素 3、左标签位置空,移动右标签,反之一样 4、重复3,直到左右侧标签指向同一个位置, 5、把临时存放的中间元素, 归位 一句话:左手右手一个慢动作,右手左手慢动作重播特点:
1、递归拆分 2、拆分到最后,所有小组内的元素个数都是1 一句话:递归拆分到不能再拆def quick_sort(lists,start,end): if start < end : left = start right = end mid = lists[start] while left < right: while left < right and lists[right] >= mid: right -= 1 lists[left] = lists[right] while left < right and lists[left] < mid: left += 1 lists[right] = lists[left] lists[left] = mid quick_sort(lists, start, left-1) quick_sort(lists, left+1, end)if __name__ == "__main__": lists = [54,26,93,17,77,31,44,55,20] print(lists) quick_sort(lists,0,len(lists)-1) print(lists)
对于每次快排,left和right的标签分别在左右两册数据全部都移动了一遍,相当于遍历了所有数据,那么时 间复杂度是O(n)
因为涉及到了递归分组,所以他的时间复杂度是O(logn) 整体来说:最优的时间复杂度是 O(nlogn)。
因为递归分组分组的条件不一定是二分,有可能每一次mid指定的都是最大或者最小,那么有多少个元素,我们
就可能分多少次组,这种情况时间复杂度就是O(n)了 所以最坏的时间复杂度就是O(n2),那么最坏也不过如此了。
归并排序是采用分治法的一个非常典型的应用。 将无序队列拆分成两个小组,组内元素排序,然后组间元素逐个比较,把小元素依次放到新队列中。
归并排序分为两个阶段:
分组排序阶段: 1、将无序队列alist,拆分成两个小组A和B, 2、分别对两个小组进行同样的冒泡排序 3、用标签left和right,分别对小组A和B进行管理 合并新队列阶段: 4、两个标签所在的元素比较大小, 5、将小的元素放到一个新队列中,然后小元素所在的标签向右移 6、多次执行4和5,最终肯定有一个小组先为空 7、把不为空的小组元素,按顺序全部移到新队列的末尾 8、无序队列中的所有元素就在新队列中形成有序队列了 特点: 两个阶段:分组排序+合并 合并策略:组间比较,新增小,小移标def fen_zu(lists): n = len(lists) if n <= 1: return lists mid = n//2 zuo = fen_zu(lists[:mid]) you = fen_zu(lists[mid:]) return merge(zuo,you)def merge(zuo,you): l,r = 0,0 result = [] zuo_len = len(zuo) you_len = len(you) while l
对于每次合并,left和right的标签分别在左右两组数据全部都移动了一遍,相当于遍历了所有数据,那么时
间复杂度是O(n);对于分组来说,因为他是递归,所以他的时间复杂度是O(logn) 整体来说:最优的时间复杂度是 O(nlogn)
堆是采用顺序表存储的一种完全二叉树的结构。
父节点和子节点关系:
父节点位置 i,找子节点: 左子节点位置:2i + 1 右子节点位置:2i + 2它是指利用堆这种树结构所设计的一种排序算法。
简单来说,就是将无序列表先构造一个有特点的堆,然后利用列表的特点快速定位最大/小的元素,将其放到一个队列中。 1、根据完全二叉树结构,将无序队列构造成一个大顶堆, 2、将堆顶的根节点移走,与无序列表的末尾元素交换,此时末尾元素就是最大值,相当于进入了一个有序队列。 3、再将剩余的n-1个无序队列重新构造一个同样堆, 4、重复循环1-3步,最终将所有元素都移动到有序队列。 特点: 无序队列构建一个堆,堆顶和堆尾元素替换位置 重新构建堆,堆顶和堆尾元素替换位置, … 简单来说:头尾替换,恢复堆后再继续以大顶堆为例:
# 堆的调整def sift(data, low, high): i = low # 堆顶节点的下标 i j = 2 * i + 1 # 上移节点标号 j,临时指向左侧子节点标号 tmp = data[i] # 把堆顶节点移动到临时队列, while j <= high: # 左侧子节点小于堆的最大范围值 if j + 1 <= high and data[j] < data[j+1]: # 右侧节点元素如果大于左侧节点元素 j += 1 # 上移节点标号 j 指向右侧节点 if data[j] > tmp: # 如果上移节点标号的元素大于移除的堆顶元素 data[i] = data[j] # 把上移节点元素移动到堆顶位置 i = j # 调整空位置节点标号 i 指向最新的空位置节点标号 j = 2 * i +1 # 上移节点标号 j,临时指向空位置节点的左侧子节点标号 else: # 如果子节点标号不在队列中,就退出操作 break data[i] = tmp# 构建堆def heap_sort(data): n = len(data) # 获取队列的长度 # 构建初始堆结构 for i in range(int(n/2) - 1, -1, -1): # 调整的节点范围,从 n/2 - 1 开始,倒序到 0 sift(data, i, n-1) # 调整当前结点堆序列 #堆顶元素排序 for i in range(n-1, -1, -1): # 遍历队列最小元素 data[0], data[i] = data[i], data[0] # 堆顶元素和堆最小元素进行替换 sift(data, 0, i - 1) # 调整新队列 # 返回排序后的队列 return dataif __name__ == "__main__": a = [0, 2, 6, 98, 34, 5, 23, 11, 89, 100, 7] print("排序之前:%s" % a) c = heap_sort(a) print("排序之后:%s" % c)
以从小到大进行排序为例: 冒泡排序:在无序队列中选择最小的移动到最左侧, 选择排序:定一个有序队列,从无序队列中选择最小的元素追加到有序队列的末尾 插入排序:定一个有序队列,从无序队列中选择第一个元素,插入到到有序队列的合适位置 希尔排序:通过对无序队列进行分组,然后再采用插入的排序方法 快速排序:指定一个元素,将无序队列拆分为大小两部分,然后层级递进,最终实现有序队列 归并排序:是将无序队列拆分,然后小组内排序,组间元素比较后在新队列中进行排序 堆 排 序:顺序表方式构造堆,首尾替换调整堆
他们的执行时间如下:
系统排序 < 快速排序 < 归并排序 < 堆 排 序 < 希尔排序 < 选择排序 < 插入排序 < 冒泡排序转载地址:http://isili.baihongyu.com/