一、归并排序法
1、任务要求
请用python编写一个程序，用归并排序法将包含N个元素（用户自行输入）的数列按升序排列。
2、解题思路
首先以整个数组为对象执行mergeSort函数，mergeSort函数是将给定的列表数组每次都分割成两个左右子列表数组，对两个左右子列表数组又分别递归执行mergeSort函数，并用merge函数每次将两个左右子列表数组进行递归排序和整合成分割前的数组。
3、代码及结果
def mergeSort(arr): if(len(arr) < 2): return arr middle = len(arr) // 2 left = arr[0:middle] # 截片0到middle-1，属于左子列表数组 right = arr[middle:] # 截片middle到最后一个列表元素，属于右子列表数组 return merge(mergeSort(left), mergeSort(right)) def merge(left,right): result = [] # 排序从小到大 while left and right: # 左右列表都有元素存在需要比较大小 if left[0] <= right[0]: # 相同元素左列表优先 result.append(left.pop(0)) else: result.append(right.pop(0)) while left: # 左列表存在元素 result.append(left.pop(0)) while right: # 右列表存在元素 result.append(right.pop(0)) return result # 返回每次左右列表合并排序后的结果 x = list(map(int,input().split())) # 输入需要排序的列表元素 print(mergeSort(x)) # 输出排序后的列表结果
二、分割法
1、任务要求
请用python编写一个程序，用分割法将包含N个元素（用户自行输入）的数列执行分割，数列相邻元素用空格隔开，用作分割基准的元素用“[ ]”标出。
2、解题思路
将列表数组元素依次与分割基准元素std进行大小比较，若小于则向前和数组中前面大于分割基准元素的第一个元素进行位置和数值交换，不断循环最后直到完成基准分割元素和大于它的第一个元素进行位置和数值交换，最后按要求输出。
3、代码及结果
def partitions(arr): # 分割函数 std = arr[-1] # 分割基准元素赋值 w = [] # 记录大于分割基准元素的数组下标 for i in range(len(arr)): if arr[i] > std: w.append(i) else: if w: # 若为空时无法交换，就不动元素的位置 j = w.pop(0) temp = arr[i] arr[i] = arr[j] arr[j] = temp w.append(i) # 元素交换后相应下标会同时改动，所以重新加入下标列表 for k in range(len(arr)): if k == j: # 最后一次交换前的列表下标也是分割基准元素最后的归处 print("[" + str(arr[k]) + "]",end=" ") else: print(arr[k],end=" ") x = list(map(int,input().split())) # 输入 partitions(x) # 调用分割函数
三、快速排序法
1、任务要求
请用python编写一个程序，用快速排序法将包含N个元素（用户自行输入）的数列按升序排列。
2、解题思路
首先以整个数组为对象不断进行分割，每次分割就是将列表数组元素依次与分割基准元素std进行大小比较，若小于则向前和数组中前面大于分割基准元素的第一个元素进行位置和数值交换，不断循环最后直到完成基准分割元素和大于它的第一个元素进行位置和数值交换，然后定下基准分割元素不动，其余以基准分割元素为中间值继续左右分割，最后按要求输出。
3、代码及结果
def partitions(arr,l,r): # 分割函数 std = arr[r] # 分割基准元素赋值 j = l # 指向比基准元素大的值的第一个数组下标 i = j while i < r: # 循环与分割基准元素进行比较 if arr[i] <= std: arr[i],arr[j] = arr[j],arr[i] # 交换值 j += 1 i += 1 arr[r],arr[j] = arr[j],arr[r] # 最后一次交换前的列表下标也是分割基准元素最后的归处 return j # 返回分割基准元素的下标，等同于定位 def quicksorts(arr,l,r): # 快速排序函数 if l < r : q = partitions(arr,l,r) # 返回每次分割基准元素的下标，等同于定位 quicksorts(arr, l, q - 1) # 递归左排序 quicksorts(arr, q + 1, r) # 递归右排序 x = list(map(int,input().split())) # 输入 a = len(x) - 1 quicksorts(x,0,a) # 调用快速排序函数 print(x) # 输出排序后的结果
四、计数排序法
1、任务要求
请用python编写一个程序，用计数排序法将包含N个元素（用户自行输入）的数列按升序排列。
2、解题思路
首先将输入数组的各个元素分别对应到w数组的下标上（也就是输入数组元素的值对应w的下标的值，元素重复的次数对应w[下标]的值），每次对应上w数组下标的值时，w[下标]的值自加1，然后再根据w数组的下标的值，从头开始用w[下标]的值循环递减到0，将w的下标的值依次添加到arrs数组，最后按要求输出。
3、代码及结果
def countingsorts(arr): # 计数函数 w = [] # 统计输入的列表中各元素的次数 arrs = [] # 排列结果列表 maxindex = max(arr) + 1 # 输入的列表中的元素的最大值加1 for k in range(maxindex): w.append(0) # 根据输入的列表中的元素的最大值加1进行数组所有元素元素初始化0 for i in arr: # 元素对应w列表的下标进行数目统计 w[i] += 1 for i in range(len(w)): while w[i] > 0: # 根据列表w的统计数目进行排序赋值给arrs数组 arrs.append(i) w[i] -= 1 return arrs x = list(map(int,input().split())) # 输入 print(countingsorts(x)) # 输出
想要了解更多数据结构基本算法（python版本）：请点击打开此文章链接
