插入法排序和合并法排序
本帖最后由 yinda_peng 于 2023-5-31 08:07 编辑看到陶远航的帖子，突然想起来自己这学期大作业就是做的这个主题，因为这学期主要是numpy和pandas，所以用了这两个模块，考虑矩阵。
程序部分的设计主要是对插入法排序和合并法排序进行了时间上的对比：import pandas as pd
import numpy as np
import time
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr
j = i - 1
while j >= 0 and key < arr:
arr = arr
j -= 1
arr = key
def merge(arr, left, middle, right):
n1 = middle - left + 1
n2 = right - middle
L = for i in range(n1)]
R = for i in range(n2)]
i = j = 0
k = left
while i < n1 and j < n2:
if L <= R:
arr = L
i += 1
else:
arr = R
j += 1
k += 1
while i < n1:
arr = L
i += 1
k += 1
while j < n2:
arr = R
j += 1
k += 1
def merge_sort(arr, left, right):
if left < right:
middle = (left + right) // 2
merge_sort(arr, left, middle)
merge_sort(arr, middle+1, right)
merge(arr, left, middle, right)
class SortTest:
def __init__(self, size):
self.arr = np.random.randint(size, size=size)
self.insertion_time = None
self.merge_time = None
def test_insertion(self):
arr_copy = self.arr.copy()
start = time.time()
insertion_sort(arr_copy)
self.insertion_time = time.time() - start
def test_merge(self):
arr_copy = self.arr.copy()
start = time.time()
merge_sort(arr_copy, 0, len(arr_copy) - 1)
self.merge_time = time.time() - start
if __name__ == '__main__':
size = 10000
sort_test = SortTest(size)
sort_test.test_insertion()
sort_test.test_merge()
df_data = {"size": , "insertion time": , "merge time": }
df_results = pd.DataFrame(data=df_data)
print(df_results)
输出结果： sizeinsertion timemerge time010000 4.334727 0.042265在这个代码中，我们定义了插入法排序和合并法排序两个函数，分别用于对数组进行排序。同时，我们也实现了一个名为SortTest的类，用于生成随机数数组并测试两种排序算法的执行时间。最终，我们通过Pandas的DataFrame输出了排序结果。需要注意的是，由于Python的内置排序函数sorted()已经使用了优化后的快速排序（Quicksort），因此在实际应用中，如果只是为了排序而不需要手写算法，可以考虑直接使用sorted()函数进行排序，以免重复造轮子。可能会觉得既然已经有sorted()函数了，我们做这个有什么意义，但是对排序进行一定层级的理解是非常有必要的，我们使用其他的编程语言就不一定有像python这样的sorted()函数了，是以这对我们以后学习编程是十分有帮助的。同时可以利用合并排序法对矩阵的某一行或者某一列进行排序：import pandas as pd
import numpy as np
def merge(arr, left, middle, right):
n1 = middle - left + 1
n2 = right - middle
L = for i in range(n1)]
R = for i in range(n2)]
i = j = 0
k = left
while i < n1 and j < n2:
if L <= R:
arr = L
i += 1
else:
arr = R
j += 1
k += 1
while i < n1:
arr = L
i += 1
k += 1
while j < n2:
arr = R
j += 1
k += 1
def merge_sort_row(matrix, row):
merge_sort(matrix, 0, len(matrix) - 1)
if __name__ == '__main__':
matrix = np.random.randint(100, size=(5, 5))
print(f"Before sorting:\n{matrix}")
row_to_sort = 3
merge_sort_row(matrix, row_to_sort)
print(f"After sorting row {row_to_sort}:\n{matrix}")
输出结果：Before sorting:[ ]After sorting row 3:[ ]代码首先生成了一个随机矩阵，然后选择了需要排序的行号（在本例中为第三行）。最终使用merge_sort_row()函数进行排序。该函数中，我们直接使用了前面代码的merge_sort()函数，但是因为矩阵的行是一个一维数组，所以直接传入了matrix作为排序对象。同理，如果需要对某一列进行合并法排序，只需将合并排序算法中对于下标的操作改为操作矩阵的列即可，或者应用矩阵转置来实现。提一句，在Numpy库中也有和sorted对应的用于矩阵某行某列排序的函数numpy.sort，还有实现间接排序的函数argsort和lexsort，不过多延伸了。今天下午C语言考试，祝我好运（满绩）{:10_297:} @夏季的春秋 mouse man{:10_325:} 首楼{:9_217:}
@zhangjinxuan @歌者文明清理员 @星期五打篮球 @中英文泡椒 @一点沙 鱼币飞来@sfqxx_小 sfqxx 发表于 2023-5-16 18:01
首楼
@zhangjinxuan @歌者文明清理员 @星期五打篮球 @中英文泡椒 @一点沙
支持！！ 星期五打篮球 发表于 2023-5-16 18:02
支持！！
再来一次{:9_217:}
建议使用表情+文字 {:7_146:}{:7_146:} sfqxx 发表于 2023-5-16 18:01
首楼
@zhangjinxuan @歌者文明清理员 @星期五打篮球 @中英文泡椒 @一点沙
币 www.hao123.com {:10_257:} 支持支持{:10_298:} 歌者文明清理员 发表于 2023-5-16 18:06
www.hao123.com
{:7_132:} 考完了，满绩不可能了，考得真的细，错了好几题了已经{:10_266:}
支持支持 sfqxx_小 发表于 2023-5-16 19:18
123 sfqxx 发表于 2023-5-16 18:02
再来一次
建议使用表情+文字
{:7_146:}支持！！ 考试冲冲冲！！ 币 渔币 {:5_106:}