排序思路:
1.将数组分成两组A,B,建立临时数组 C,C长度=A + B
2. i,j分别属于A,B
3. 若A[i] > B[j] , 将B[j]放入C, j++; 否则 A[i]放入C, i++
4.循环3步骤,将A或B中剩余的元素放入C,再将C复制到数组中
5.递归3-4直到A,B序列的长度=1
#归并排序 class MergeSort: def __init__(self, arrData): self.arrData = arrData; self.tmpData=[]; #建立临时数组 for i in range(len(self.arrData)): self.tmpData.append(0); return; #left 要排序的序列的最小索引 #right 要排序的序列的最大索引 def sortHalf(self,arrData,left,right): center = (left + right) // 2; self.mergeSort(arrData,left,center,right); return; #排序方法 #[left,center]为第一个序列 #[center, right]为第二个序列 #两个序列进行归并排序 def mergeSort(self,arrData,left,center,right): ##将左边和右边递归分别分成两组再进行排序 #直到两个序列的长度为1后停止递归 if left < center : self.sortHalf(arrData,left,center); if center < right: self.sortHalf(arrData,center+1,right); i = left; j = center + 1; k = i; #排序算法 while k <= right: #print(i,center,j); if i > center: self.tmpData[k] = arrData[j]; j = j + 1; elif j > right: self.tmpData[k] = arrData[i]; i = i + 1; elif arrData[i] > arrData[j]: self.tmpData[k] = arrData[j]; j = j + 1; else: self.tmpData[k] = arrData[i]; i = i + 1; k = k + 1; #复制tmpData序列到arrData序列 for l in range(left,right + 1): arrData[l] = self.tmpData[l]; return; #排序入口 def sort(self): arrData = self.arrData; left = 0; right = len(arrData) - 1; center = (left + right) // 2; self.sortHalf(arrData,left,right); return; def __del__(self): del self.tmpData; arr = [7,2,5,3,1,8,6,100,48,38,45,20,34,67,12,23,90,58]; print(arr); shellSort = MergeSort(arr); shellSort.sort(); print(arr);
归并排序的时间复杂度为O(nLog2n),空间效率较差
相关推荐
python 归并排序算法 归并排序是一种基于分治思想的排序算法,它将待排序的序列分成若干个子序列,每个子序列都是有序的,然后再将这些有序的子序列合并成一个有序的序列。归并排序的时间复杂度为O(nlogn),是一种...
关于python的算法一直都是让我们又爱又恨,但是如果可以灵活运用起来,对我们的编写代码过程,可以大大提高效率,针对算法之一“归并排序”的灵活掌握,一起来看下吧~ 归并算法——小试牛刀 实例内容: 有 1 个无序...
归并排序.py 使用python代码实现归并排序.py 使用python代码实现归并排序.py 使用python代码实现归并排序.py 使用python代码实现归并排序.py 使用python代码实现归并排序.py 使用python代码实现归并排序.py 使用...
详细描述请查看该文章:https://blog.csdn.net/qq_28531269/article/details/122415336?spm=1001.2014.3001.5502
pyhton编写的归并排序是一种高效的快速排序算法,也是python本身内部的排序算法,它不仅时间复杂度小而且简单,符合分而治之的原则,也让很多程序员喜欢,大家快打开看看吧。
基于python的归并排序算法设计与实现
Python实现归并排序.rar
主要为大家详细介绍了python编程实现归并排序的具体代码,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
基于python的排序算法-归并排序Merge Sort
/usr/bin/python import sys def merge(array, q, p, r): left_array = array[q:p+1] right_array = array[p+1:r+1] left_array_num = len(left_array) right_array_num = len(right_array) i, j , k= [0, 0, q] ...
1、归并排序算法是什么? 冒泡排序(Bubble Sort)是一种建立在归并操作上面的一种有效的排序算法,由John von neumann于1945年发明。采用分治法(Divide and Conquer)的经典应用!!将规模较大的排序问题化归到较小...
文件归并排序 命令行说明: sort.py -i <input_filename> -o <output_filename> [-d ] [-c ] [-s ] [-t ] -i 输入源文件名 -o 输出目标文件名,如果未指定,则结果覆盖到源文件 -d 可选项,文件文本行的列分隔符,...
归并排序
选择排序,冒泡排序,插入排序,归并排序Python代码
python八个常用排序(插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序)
Python 算法 16归并排序实现.mp4
Python 算法 15归并排序思想.mp4
在Python中,常用的排序算法包括冒泡排序、选择排序、插入排序、快速排序、归并排序等。下面将对这些排序算法进行详细的介绍。 1. 冒泡排序 冒泡排序是一种简单的排序算法,它的基本思想是通过不断交换相邻的元素,...
归并排序
归并排序是典型的分治法的应用 思想:先递归分解数组,再合并数组 原理:将数组分解最小之后,然后合并两个有序数组,基本思想是比较两个数组的最前面的数,谁小就取谁,取完后,将相应的指针后移以为。然后再比较,...