算法——列表排序和排序算法
2021-07-01 08:04
标签：希尔 结构 重复 列表排序 子节点 val 有序 构造 heapsort 排序就是将一组“无序”的记录序列调整为“有序”的记录序列。 列表排序：将无序列表变为有序列表。 输入：列表 输出：有序列表 两种基本的排序方式：升序和降序。 python内置的排序函数：sort()。 名称 复杂度 说明 备注 冒泡排序 O(N*N) 将待排序的元素看作是竖着排列的“气泡”，较小的元素比较轻，从而要往上浮 插入排序 Insertion sort O(N*N) 逐一取出元素，在已经排序的元素序列中从后向前扫描，放到适当的位置 起初，已经排序的元素序列为空 选择排序 O(N*N) 首先在未排序序列中找到最小元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小元素，然后放到排序序列末尾。以此递归。 快速排序 Quick Sort O(n *log2(n)) 先选择中间值，然后把比它小的放在左边，大的放在右边（具体的实现是从两边找，找到一对后交换）。然后对两边分别使用这个过程（递归）。 堆排序HeapSort O(n *log2(n)) 利用堆（heaps）这种数据结构来构造的一种排序算法。堆是一个近似完全二叉树结构，并同时满足堆属性：即子节点的键值或索引总是小于（或者大于）它的父节点。 近似完全二叉树 希尔排序 SHELL O(n1+￡) 0
选择一个步长(Step) ,然后按间隔为步长的单元进行排序.递归,步长逐渐变小,直至为1. 箱排序 O(n) 设置若干个箱子，把关键字等于 k 的记录全都装入到第k 个箱子里 ( 分配 ) ，然后按序号依次将各非空的箱子首尾连接起来 ( 收集 ) 。 分配排序的一种：通过" 分配 " 和 " 收集 " 过程来实现排序。 列表每两个相邻的数，如果前面比后面大，则交换这两个数。 一趟排序完成后，则无序区减少一个数，有序区增加一个数。 代码关键点：趟、无序区范围。 这样排序一趟后，最大的数9，就到了列表最顶成为了有序区，下面的部分则还是无序区。然后在无序区不断重复这个过程，每完成一趟排序，无序区减少一个数，有序区增加一个数。图示最后一张图要开始第六趟排序，排序从第0趟开始计数。剩一个数的时候不需要排序了，因此整个排序排了n-1趟。 如果要打印出每次排序结果： n是列表的长度，算法中也没有发生循环折半的过程，具备两层关于n的循环，因此它的时间复杂度是O(n2)。 如果在一趟排序过程中没有发生交换就可以认定已经排好序了。因此可做如下优化： 对比前面排序的次数少了很多，算法得到了优化~ 算法——列表排序和排序算法 标签：希尔 结构 重复 列表排序 子节点 val 有序 构造 heapsort 原文地址：https://www.cnblogs.com/xiugeng/p/9638052.html一、列表排序
二、常见排序算法
Bubble Sort
Bin Sort
1、冒泡排序（Bubble Sort）
（1）图示说明
（2）代码示例
import random
def bubble_sort(li):
for i in range(len(li)-1): # 总共是n-1趟
for j in range(len(li)-i-1): # 每一趟都有箭头，从0开始到n-i-1
if li[j] > li[j+1]: # 比对箭头指向和箭头后面的那个数的值
# 当箭头所指数大于后面的数时交换位置, 升序排列；条件相反则为降序排列
li[j], li[j+1] = li[j+1], li[j]
li = [random.randint(0, 10000) for i in range(30)]
print(li)
bubble_sort(li)
print(li)
"""
[5931, 5978, 6379, 4217, 9597, 4757, 4160, 3310, 6916, 2463, 9330, 8043, 8275, 5614, 8908, 7799, 9256, 3097, 9447, 9327, 7604, 9464, 417, 927, 1720, 145, 6451, 7050, 6762, 6608]
[145, 417, 927, 1720, 2463, 3097, 3310, 4160, 4217, 4757, 5614, 5931, 5978, 6379, 6451, 6608, 6762, 6916, 7050, 7604, 7799, 8043, 8275, 8908, 9256, 9327, 9330, 9447, 9464, 9597]
"""
import random
def bubble_sort(li):
for i in range(len(li)-1): # 总共是n-1趟
for j in range(len(li)-i-1): # 每一趟都有箭头，从0开始到n-i-1
if li[j] > li[j+1]: # 比对箭头指向和箭头后面的那个数的值
# 当箭头所指数大于后面的数时交换位置, 升序排列；条件相反则为降序排列
li[j], li[j+1] = li[j+1], li[j]
print(li)
li = [random.randint(0, 10000) for i in range(5)]
print(li)
bubble_sort(li)
print(li)
"""
[1806, 212, 4314, 1611, 8355]
[212, 1806, 1611, 4314, 8355]
[212, 1611, 1806, 4314, 8355]
[212, 1611, 1806, 4314, 8355]
[212, 1611, 1806, 4314, 8355]
[212, 1611, 1806, 4314, 8355]
"""
（3）算法时间复杂度
（4）冒泡排序优化
import random
def bubble_sort(li):
for i in range(len(li)-1): # 总共是n-1趟
exchange = False
for j in range(len(li)-i-1): # 每一趟都有箭头，从0开始到n-i-1
if li[j] > li[j+1]: # 比对箭头指向和箭头后面的那个数的值
# 当箭头所指数大于后面的数时交换位置, 升序排列；条件相反则为降序排列
li[j], li[j+1] = li[j+1], li[j]
exchange = True # 如果发生了交换就置为true
print(li)
if not exchange:
# 如果exchange还是False，说明没有发生交换，结束代码
return
# li = [random.randint(0, 10000) for i in range(5)]
li = [1806, 212, 4314, 1611, 8355]
bubble_sort(li)
"""
[212, 1806, 1611, 4314, 8355]
[212, 1611, 1806, 4314, 8355]
[212, 1611, 1806, 4314, 8355]
"""
2、选择排序
上一篇：数组练习：各种数组方法的使用
下一篇：Java-单例模式