马上注册，结交更多好友，享用更多功能^_^
您需要 登录 才可以下载或查看，没有账号？立即注册
x
本帖最后由 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[j]:
- arr[j + 1] = arr[j]
- j -= 1
- arr[j + 1] = key
- def merge(arr, left, middle, right):
- n1 = middle - left + 1
- n2 = right - middle
- L = [arr[left + i] for i in range(n1)]
- R = [arr[middle + 1 + i] for i in range(n2)]
- i = j = 0
- k = left
- while i < n1 and j < n2:
- if L <= R[j]:
- arr[k] = L
- i += 1
- else:
- arr[k] = R[j]
- j += 1
- k += 1
- while i < n1:
- arr[k] = L
- i += 1
- k += 1
- while j < n2:
- arr[k] = R[j]
- 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": [size], "insertion time": [sort_test.insertion_time], "merge time": [sort_test.merge_time]}
- df_results = pd.DataFrame(data=df_data)
- print(df_results)
[i][i]输出结果：[/i][/i] [i][i] size insertion time merge time[/i][/i] [i][i]0 10000 4.334727 0.042265[/i][/i]
[i][i]在这个代码中，我们定义了插入法排序和合并法排序两个函数，分别用于对数组进行排序。同时，我们也实现了一个名为SortTest的类，用于生成随机数数组并测试两种排序算法的执行时间。最终，我们通过Pandas的DataFrame输出了排序结果。需要注意的是，由于Python的内置排序函数sorted()已经使用了优化后的快速排序（Quicksort），因此在实际应用中，如果只是为了排序而不需要手写算法，可以考虑直接使用sorted()函数进行排序，以免重复造轮子。[/i][/i] [i][i]可能会觉得既然已经有sorted()函数了，我们做这个有什么意义，但是对排序进行一定层级的理解是非常有必要的，我们使用其他的编程语言就不一定有像python这样的sorted()函数了，是以这对我们以后学习编程是十分有帮助的。[/i][/i]
[i][i]同时可以利用合并排序法对矩阵的某一行或者某一列进行排序：[/i][/i] - import pandas as pd
- import numpy as np
- def merge(arr, left, middle, right):
- n1 = middle - left + 1
- n2 = right - middle
- L = [arr[left + i] for i in range(n1)]
- R = [arr[middle + 1 + i] for i in range(n2)]
- i = j = 0
- k = left
- while i < n1 and j < n2:
- if L <= R[j]:
- arr[k] = L
- i += 1
- else:
- arr[k] = R[j]
- j += 1
- k += 1
- while i < n1:
- arr[k] = L
- i += 1
- k += 1
- while j < n2:
- arr[k] = R[j]
- j += 1
- k += 1
- def merge_sort_row(matrix, row):
- merge_sort(matrix[row], 0, len(matrix[row]) - 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}")
[i][i]输出结果：[/i][/i] [i][i]Before sorting:[/i][/i] [i][i][[82 0 67 5 36][/i][/i] [i][i] [42 38 13 21 45][/i][/i] [i][i] [33 41 87 67 81][/i][/i] [i][i] [10 70 57 25 40][/i][/i] [i][i] [88 18 90 96 65]][/i][/i] [i][i]After sorting row 3:[/i][/i] [i][i][[82 0 67 5 36][/i][/i] [i][i] [42 38 13 21 45][/i][/i] [i][i] [33 41 87 67 81][/i][/i] [i][i] [10 25 40 57 70][/i][/i] [i][i] [88 18 90 96 65]][/i][/i]
[i][i]代码首先生成了一个随机矩阵，然后选择了需要排序的行号（在本例中为第三行）。最终使用merge_sort_row()函数进行排序。该函数中，我们直接使用了前面代码的merge_sort()函数，但是因为矩阵的行是一个一维数组，所以直接传入了matrix[row]作为排序对象。同理，如果需要对某一列进行合并法排序，只需将合并排序算法中对于下标的操作改为操作矩阵的列即可，或者应用矩阵转置来实现。提一句，在Numpy库中也有和sorted对应的用于矩阵某行某列排序的函数numpy.sort，还有实现间接排序的函数argsort和lexsort，不过多延伸了。[/i][/i]
[i][i] 今天下午C语言考试，祝我好运（满绩） [/i][/i] | 
( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)
狗仔卡
发表于 2023-5-16 08:13:27
置顶卡
千斤顶
显身卡
楼主
发表于 2023-5-16 19:17:46
