冒泡排序
冒泡排序（英语：Bubble Sort）是⼀种简单的排序算法。它重复地遍历要排序的数列，⼀次⽐较两个元素，如果他们的顺序错误就把他们交换过来。遍历数列的⼯作是重复地进⾏直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越⼩的元素会经由交换慢慢“浮”到数列的顶端。
冒泡排序算法的运作如下：
- ⽐较相邻的元素。如果第⼀个⽐第⼆个⼤（升序），就交换他们两个。
- 对每⼀对相邻元素作同样的⼯作，从开始第⼀对到结尾的最后⼀对。步做完后，最后的元素会是最⼤的数。
- 针对所有的元素重复以上的步骤，除了最后⼀个。
- 持续每次对越来越少的元素重复上⾯的步骤，直到没有任何⼀对数字需要⽐较。
import random
def get_rand_list(num):
# 获取随机列表数据
data = [random.randint(0, num * 2) for _ in range(num)]
print('get_rand_li:', data)
return data
def bubble_sort(data):
""" 冒泡排序
最优: O(N),对已经有序数据排序,只用遍历一遍
最坏: O(N^2)
稳定性: 稳定(如果比较为'>='则不稳定)
"""
n = len(data)
for i in range(n - 1):
flag = True # 表示没有交换
# 一次遍历,最大放最后,下一次不用比较最大值
for j in range(n - 1 - i):
if data[j] > data[j + 1]: # 将大元素后移
data[j], data[j + 1] = data[j + 1], data[j]
flag = False # 存在交换
if flag: # 如果没有交换则已经排序好
break
return data
if __name__ == '__main__':
list_num = 10
print('bubble_sort:', bubble_sort(get_rand_list(list_num)), 'n')选择排序
选择排序（Selection sort）是⼀种简单直观的排序算法。它的⼯作原理如下。⾸先在未排序序列中找到最⼩（⼤）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最⼩（⼤）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上，则它不会被移动。选择排序每次交换⼀对元素，它们当中⾄少有⼀个将被移到其最终位置上，因此对n个元素的表进⾏排序总共进⾏⾄多n-1次交换。在所有的完全依靠交换去移动元素的排序⽅法中，选择排序属于⾮常好的⼀种。
import random
def get_rand_list(num):
# 获取随机列表数据
data = [random.randint(0, num * 2) for _ in range(num)]
print('get_rand_li:', data)
return data
def select_sort(data):
""" 选择排序
最优,最坏: O(N^2)
稳定性: 不稳定(相同元素,后面元素会先移到前面元素之前)
"""
n = len(data)
for i in range(n - 1):
min_index = i # 赋值最小值下标
for j in range(i + 1, n):
if data[j] < data[min_index]:
min_index = j # 找到更小的值则记录下标
if i != min_index:
data[i], data[min_index] = data[min_index], data[i]
return data
if __name__ == '__main__':
list_num = 10
print('select_sort:', select_sort(get_rand_list(list_num)), 'n')插入排序
插⼊排序（英语：Insertion Sort）是⼀种简单直观的排序算法。它的⼯作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插⼊。插⼊排序在实现上，在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插⼊空间。
import random
def get_rand_list(num):
# 获取随机列表数据
data = [random.randint(0, num * 2) for _ in range(num)]
print('get_rand_li:', data)
return data
def insert_sort(data):
""" 插入排序
最优: O(N),对已经有序数据排序,只用遍历一遍
最坏: O(N^2)
稳定性: 稳定
"""
for i in range(1, len(data)): # 从第二个元素开始
for j in range(i, 0, -1):
# j遍历的范围:[i,i-1,i-2,...,1]
if data[j] < data[j - 1]:
data[j], data[j - 1] = data[j - 1], data[j]
else: # 当前元素和前面数组组成有序,不需要再循环
break
return data
if __name__ == '__main__':
list_num = 10
print('insert_sort:', insert_sort(get_rand_list(list_num)), 'n')希尔排序
希尔排序(Shell Sort)是插⼊排序的⼀种。也称缩⼩增量排序，是直接插⼊排序算法的⼀种更⾼效的改进版本。希尔排序是⾮稳定排序算法。该⽅法因DL．Shell于1959年提出⽽得名。 希尔排序是把记录按下标的⼀定增量分组，对每组使⽤直接插⼊排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减⾄1时，整个⽂件恰被分成⼀组，算法便终⽌。
希尔排序过程：希尔排序的基本思想是：将数组列在⼀个表中并对列分别进⾏插⼊排序，重复这过程，不过每次⽤更⻓的列（步⻓更⻓了，列数更少了）来进⾏。最后整个表就只有⼀列了。将数组转换⾄表是为了更好地理解这算法，算法本身还是使⽤数组进⾏排序。
例如，假设有这样⼀组数[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10]，如果我们以步⻓为5开始进⾏排序，我们可以通过将这列表放在有5列的表中来更好地描述算法，这样他们就应该看起来是这样(竖着的元素是步⻓组成)：
13 14 94 33 82
25 59 94 65 23
45 27 73 25 39
10
然后我们对每列进⾏排序：
10 14 73 25 23
13 27 94 33 39
25 59 94 65 82
45
将上述四⾏数字，依序接在⼀起时我们得到：[ 10 14 73 25 23 13 27 94 3339 25 59 94 65 82 45 ]。这时10已经移⾄正确位置了，然后再以3为步⻓进⾏排序：
10 14 73
25 23 13
27 94 33
39 25 59
94 65 82
45
排序之后变为：
10 14 13
25 23 33
27 25 59
39 65 73
45 94 82
94
最后以1步⻓进⾏排序（此时就是简单的插⼊排序了）
import random
def get_rand_list(num):
# 获取随机列表数据
data = [random.randint(0, num * 2) for _ in range(num)]
print('get_rand_li:', data)
return data
def shell_sort(data):
""" 希尔排序
最优: 根据步⻓序列的不同⽽不同,去掉那个break就是O(N)
最坏: O(N^2)
稳定性: 不稳定(因为相同元素可能存在不同步长中,排序后相对位置会变)
"""
n = len(data)
gap = n // 2 # 初始步长为长度的一半
while gap >= 1: # 步长为1的时候完成排序
for j in range(gap, n): # 按步长进行插入排序
while (j - gap) >= 0:
if data[j] < data[j - gap]:
data[j], data[j - gap] = data[j - gap], data[j]
j -= gap
else: # 当前已经有序
break
gap //= 2 # 更新间隔
return data
if __name__ == '__main__':
list_num = 10
print('shell_sort :', shell_sort(get_rand_list(list_num)), 'n')快速排序
快速排序（英语：Quicksort），⼜称划分交换排序（partition-exchangesort），通过⼀趟排序将要排序的数据分割成独⽴的两部分，其中⼀部分的所有数据都⽐另外⼀部分的所有数据都要⼩，然后再按此⽅法对这两部分数据分别进⾏快速排序，整个排序过程可以递归进⾏，以此达到整个数据变成有序序列。
步骤为：
- 从数列中挑出⼀个元素，称为”基准”（pivot）
- 重新排序数列，所有元素⽐基准值⼩的摆放在基准前⾯，所有元素⽐基准值⼤的摆在基准的后⾯（相同的数可以到任⼀边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
- 递归地（recursive）把⼩于基准值元素的⼦数列和⼤于基准值元素的⼦数列排序。
递归的最底部情形，是数列的⼤⼩是零或⼀，也就是永远都已经被排序好了。虽然⼀直递归下去，但是这个算法总会结束，因为在每次的迭代（iteration）中，它⾄少会把⼀个元素摆到它最后的位置去。
import random
def get_rand_list(num):
# 获取随机列表数据
data = [random.randint(0, num * 2) for _ in range(num)]
print('get_rand_li:', data)
return data
def quick_sort(data):
""" 快速排序
最优: O(nlogn)
最坏: O(N^2)
稳定性: 不稳定
"""
def quick_sort_base(base_data, start, end):
# 定义快速排序递归实现
if start >= end:
return # 递归结束条件
# 设定起始元素基准元素
mid = base_data[start]
# left为序列左边的由左向右移动的游标
left = start
# right为序列右边的由右向左移动的游标
right = end
# left与right未重合,就向中间移动
while left < right:
# 如果left与right未重合,right指向的元素不⽐基准元素⼩,则right向左移动
while left < right and base_data[right] >= mid:
right -= 1
# 将right指向的元素放到left的位置上
base_data[left] = base_data[right]
# 如果left与right未重合,left指向的元素⽐基准元素⼩,则left向右移动
while left < right and base_data[left] < mid:
left += 1
# 将left指向的元素放到right的位置上
base_data[right] = base_data[left]
# 从循环退出后,left与right相遇,即left==right
base_data[left] = mid
# 对左边部分执行快速排序
quick_sort_base(base_data, start, left - 1)
# 对右边部分执行快速排序
quick_sort_base(base_data, left + 1, end)
quick_sort_base(data, 0, len(data) - 1)
return data
if __name__ == '__main__':
list_num = 10
print('quick_sort :', quick_sort(get_rand_list(list_num)), 'n')归并排序
归并排序是采⽤分治法的⼀个⾮常典型的应⽤。归并排序的思想就是先递归分解数组，再合并数组。将数组分解最⼩之后，然后合并两个有序数组，基本思路是⽐较两个数组的最前⾯的数，谁⼩就先取谁，取了后相应的指针就往后移⼀位。然后再⽐较，直⾄⼀个数组为空，最后把另⼀个数组的剩余部分复制过来即可。
import random
def get_rand_list(num):
# 获取随机列表数据
data = [random.randint(0, num * 2) for _ in range(num)]
print('get_rand_li:', data)
return data
def merge_sort(data):
""" 归并排序
最优: O(nlogn)
最坏: O(nlogn)
稳定性: 稳定
"""
# 当只剩余一个元素,则返回这个列表
if (n := len(data)) <= 1:
return data
# 从中间二分数据
mid = n // 2
# 对左半部分进行归并排序
left_sorted_list = merge_sort(data[:mid])
# 对右半部分进行归并排序
right_sorted_list = merge_sort(data[mid:])
# 合并两个有序集合
left, right = 0, 0
# 存放最终结果
merge_sorted_list = []
# 得到左右列表长度
left_n, right_n = len(left_sorted_list), len(right_sorted_list)
# 当左右游标都在范围内则进行排序
while left < left_n and right < right_n:
if left_sorted_list[left] <= right_sorted_list[right]:
# 左边小则添加左边元素
merge_sorted_list.append(left_sorted_list[left])
left += 1
else:
# 右边小则添加左边元素
merge_sorted_list.append(right_sorted_list[right])
right += 1
# 将左边列表剩余元素追加
merge_sorted_list += left_sorted_list[left:]
# 将右边列表剩余元素追加
merge_sorted_list += right_sorted_list[right:]
return merge_sorted_list
if __name__ == '__main__':
list_num = 10
print('merge_sort :', merge_sort(get_rand_list(list_num)), 'n')常⻅排序算法效率⽐较
关于排序算法稳定性的定义：待排序元素中两个相同元素A和B，A在B前面，当经过排序后B移动到了A前面则说明该排序算法不稳定，如果A还是在B前面则说明该排序算法稳定。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 2476560997@qq.com 举报，一经查实，本站将立刻删除。
微信扫一扫 
