归并函数python,归并函数的代码

python中有哪些简单的算法？

你好：

跟你详细说一下python的常用8大算法：

1、插入排序

插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为O(n^2)。是稳定的排序方法。插入算法把要排序的数组分成两部分：第一部分包含了这个数组的所有元素，但将最后一个元素除外(让数组多一个空间才有插入的位置)，而第二部分就只包含这一个元素(即待插入元素)。在第一部分排序完成后，再将这个最后元素插入到已排好序的第一部分中。

2、希尔排序

希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因DL．Shell于1959年提出而得名。 希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

3、冒泡排序

它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。

4、快速排序

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

5、直接选择排序

基本思想：第1趟，在待排序记录r1 ~ r[n]中选出最小的记录，将它与r1交换；第2趟，在待排序记录r2 ~ r[n]中选出最小的记录，将它与r2交换；以此类推，第i趟在待排序记录r[i] ~ r[n]中选出最小的记录，将它与r[i]交换，使有序序列不断增长直到全部排序完毕。

6、堆排序

堆排序(Heapsort)是指利用堆积树(堆)这种数据结构所设计的一种排序算法，它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。堆分为大根堆和小根堆，是完全二叉树。大根堆的要求是每个节点的值都不大于其父节点的值，即A[PARENT[i]] = A[i]。在数组的非降序排序中，需要使用的就是大根堆，因为根据大根堆的要求可知，最大的值一定在堆顶。

7、归并排序

归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

归并过程为：比较a[i]和a[j]的大小，若a[i]≤a[j]，则将第一个有序表中的元素a[i]复制到r[k]中，并令i和k分别加上1；否则将第二个有序表中的元素a[j]复制到r[k]中，并令j和k分别加上1，如此循环下去，直到其中一个有序表取完，然后再将另一个有序表中剩余的元素复制到r中从下标k到下标t的单元。归并排序的算法我们通常用递归实现，先把待排序区间[s,t]以中点二分，接着把左边子区间排序，再把右边子区间排序，最后把左区间和右区间用一次归并操作合并成有序的区间[s,t]。

8、基数排序

基数排序(radix sort)属于“分配式排序”(distribution sort)，又称“桶子法”(bucket sort)或bin sort，顾名思义，它是透过键值的部分资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其时间复杂度为O (nlog(r)m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的稳定性排序法。

相关问答

Q1: PYTHON 归并排序，求排错！

def merge(left,right): 

    result = [] 

    i,j = 0, 0 

    while i  len(left) and j  len(right):

        if left[i] = right[j]:

            result.append(left[i]) 

            i = i + 1 

        else:

            result.append(right[j]) 

            j = j + 1

    while (i  len(left)):

        result.append(left[i]) 

        i = i + 1 

    while (j  len(right)):

        result.append(right[j]) 

        j = j + 1 

    return(result)

def mergsort(L):

    print(L)

    if len(L)  2:

        print(L[:])

        # Missing the following line

        return L

    else:

        middle = len(L)/2

        left = mergsort(L[:int(middle)])

        right = mergsort(L[int(middle):])

        together = merge(left,right)

        print(together)

        return(together)

Q2: python d=map怎么理解

Python中map()、filter()、reduce()这三个都是应用于序列的内置函数。

格式：

map(func, seq1[, seq2,…])

第一个参数接受一个函数名，后面的参数接受一个或多个可迭代的序列，返回的是一个集合。

Python函数编程中的map()函数是将func作用于seq中的每一个元素，并将所有的调用的结果作为一个list返回。如果func为None，作用同zip()。

1、当seq只有一个时，将函数func作用于这个seq的每个元素上，并得到一个新的seq。

让我们来看一下只有一个seq的时候，map()函数是如何工作的。

从上图可以看出，函数func函数会作用于seq中的每个元素，得到func(seq[n])组成的列表。下面举得例子来帮助我们更好的理解这个工作过程。

#使用lambda

print map(lambda x: x % 2, range(7))

[0, 1, 0, 1, 0, 1, 0]123123

#使用列表解析

print [x % 2 for x in range(7)]

[0, 1, 0, 1, 0, 1, 0]123123

一个seq时，可以使用filter()函数代替，那什么情况不能代替呢？

2、当seq多于一个时，map可以并行（注意是并行）地对每个seq执行如下图所示的过程：

从图可以看出，每个seq的同一位置的元素同时传入一个多元的func函数之后，得到一个返回值，并将这个返回值存放在一个列表中。下面我们看一个有多个seq的例子：

print map(lambda x , y : x ** y, [2,4,6],[3,2,1])

[8, 16, 6]1212

如果上面我们不使用map函数，就只能使用for循环，依次对每个位置的元素调用该函数去执行。还可以使返回值是一个元组。如：

print map(lambda x , y : (x ** y, x + y), [2,4,6],[3,2,1])

[(8, 5), (16, 6), (6, 7)]1212

当func函数时None时，这就同zip()函数了，并且zip()开始取代这个了，目的是将多个列表相同位置的元素归并到一个元组。如：

print map(None, [2,4,6],[3,2,1])

[(2, 3), (4, 2), (6, 1)]1212

需要注意的是：

map无法处理seq长度不一致、对应位置操作数类型不一致的情况，这两种情况都会报类型错误。如下图：

3、使用map()函数可以实现将其他类型的数转换成list，但是这种转换也是有类型限制的，具体什么类型限制，在以后的学习中慢慢摸索吧。这里给出几个能转换的例子：

***将元组转换成list***

map(int, (1,2,3))

[1, 2, 3]

***将字符串转换成list***

map(int, '1234')

[1, 2, 3, 4]

***提取字典的key，并将结果存放在一个list中***

map(int, {1:2,2:3,3:4})

[1, 2, 3]

***字符串转换成元组，并将结果以列表的形式返回***

map(tuple, 'agdf')

[('a',), ('g',), ('d',), ('f',)]

#将小写转成大写

def u_to_l (s):

return s.upper()

print map(u_to_l,'asdfd')

Q3: python实现折半查找和归并排序算法

python实现折半查找和归并排序算法

今天依旧是学算法，前几天在搞bbs项目，界面也很丑，评论功能好像也有BUG。现在不搞了，得学下算法和数据结构，笔试过不了，连面试的机会都没有……

今天学了折半查找算法，折半查找是蛮简单的，但是归并排序我就挺懵比，看教材C语言写的归并排序看不懂，后来参考了别人的博客，终于搞懂了。

折半查找

先看下课本对于 折半查找的讲解。注意了，折半查找是对于有序序列而言的。每次折半，则查找区间大约缩小一半。low,high分别为查找区间的第一个下标与最后一个下标。出现lowhigh时，说明目标关键字在整个有序序列中不存在，查找失败。

看我用python编程实现:

defBinSearch(array, key, low, high): mid=int((low+high)/2) ifkey==array[mid]:# 若找到 returnarray[mid] iflow high: returnFalse ifkey array[mid]: returnBinSearch(array, key, low, mid-1)#递归 ifkey array[mid]: returnBinSearch(array, key, mid+1, high) if__name__=="__main__": array=[4,13,27,38,49,49,55,65,76,97] ret=BinSearch(array,76,0,len(array)-1)# 通过折半查找，找到65 print(ret)

输出: 在列表中查找76.

76

时间复杂度：O(logn)

归并排序算法

先阐述一下排序思路：

首先归并排序使用了二分法，归根到底的思想还是分而治之。归并排序是指把无序的待排序序列分解成若干个有序子序列，并把有序子序列合并为整体有序序列的过程。长度为1的序列是有序的。因此当分解得到的子序列长度大于1时，应继续分解，直到长度为1.

(下图是分解过程，图自python编程实现归并排序)

合并的过程如下:

很好，你现在可以和别人说，老子会归并排序了。但是让你写代码出来，相信你是不会的……

来来来，看我用python写的归并排序算法:

defmerge_sort(array):# 递归分解 mid=int((len(array)+1)/2) iflen(array)==1:# 递归结束的条件，分解到列表只有一个数据时结束 returnarray list_left=merge_sort(array[:mid]) list_right=merge_sort(array[mid:]) print("list_left:", list_left) print("list_right:", list_right) returnmerge(list_left, list_right)# 进行归并 defmerge(list_left, list_right):# 进行归并 final=[] whilelist_leftandlist_right: iflist_left[0] =list_right[0]:# 如果将"="改为"",则归并排序不稳定 final.append(list_left.pop(0)) else: final.append(list_right.pop(0)) returnfinal+list_left+list_right# 返回排序好的列表 if__name__=="__main__": array=[49,38,65,97,76] print(merge_sort(array))输出:

输出：

list_left: [49]

list_right: [38]

list_left: [38, 49]

list_right: [65]

list_left: [97]

list_right: [76]

list_left: [38, 49, 65]

list_right: [76, 97]

[38, 49, 65, 76, 97]

时间度杂度: 平均情况＝最好情况＝最坏情况＝O(nlogn)

空间复杂度:O(n)

稳定性:稳定

对序列{ 6, 5, 3, 1, 8, 7, 2, 4 }进行归并排序的实例如下:

使用归并排序为一列数字进行排序的宏观过程:

以上就是本文的全部内容，希望对大家的学习有所帮助

Q4: python实现归并排序时报错

因为merge_sort函数没有返回值,所以l1=merge_sort(left)和r1=merge_sort(right)中出l1和r1没有类型的错误,加一个返回值return li就没问题了.

完整的Python程序如下(改动的地方见注释)

def merge_sort(li):

 if len(li)==1:

  return li  #这里return改成return li

 mid=len(li)//2

 left=li[:mid]

 right=li[mid:]

 l1=merge_sort(left)

 r1=merge_sort(right)

 return merge(l1,r1)

def merge(left,right):

 result=[]

 while len(left)0 and len(right)0:

  if left[0]=right[0]:

   result.append(left.pop(0))

  else:

   result.append(right.pop(0))

 result+=left

 result+=right

 return result

a=[2,39,92,19,28,32,85,53]

print(merge_sort(a))

源代码(注意源代码的缩进)