《AI笔试面试题库-Python题目解析4》由会员分享，可在线阅读，更多相关《AI笔试面试题库-Python题目解析4（7页珍藏版）》请在金锄头文库上搜索。
1、1、请用Python手写实现插入排序。解析：插入排序（Insertion Sort）的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。算法执行步骤：（1）从第一个元素开始，该元素可以认为已经被排序；（2）取出下一个元素，在已经排序的元素序列中从后向前扫描；（3）如果被扫描的元素（已排序）大于新元素，则将被扫描元素后移一位；（4）重复步骤（3），直到找到已排序的元素小于或者等于新元素的位置；（5）将新元素插入到该位置后；（6）重复步骤（2）-（5）。Python实现def insert_sort(ary): n = len(ary) for i in
2、range(1,n): if aryi temp : aryj+1 = aryj #记录待插入下标 index = j else : break aryindex = temp return ary2、请用Python手写实现快速排序。解析：步骤：（1）从数列中挑出一个元素，称为 “基准”（pivot）；（2）重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值 大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基 准就处于数列的中间位置。这个称为分区（partition）操作；（3）递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序
3、。换言之快速排序时基于分治模式处理的，对一个典型子数组Ap.r排序的分治过程为三个步骤：（1）分解：Ap.r被划分为俩个（可能空）的子数组Ap .q-1和Aq+1 .r，使得Ap .q-1 = Aq = Aq+1 .r；（2）解决：通过递归调用快速排序，对子数组Ap .q-1和Aq+1 .r排序；（3）合并。QUICKSORT(A, p, r)1 if p r2 then q PARTITION(A, p, r) /关键3 QUICKSORT(A, p, q - 1)4 QUICKSORT(A, q + 1, r)数组划分快速排序算法的关键是PARTITION过程，它对Ap.r进行就地重排：P
4、ARTITION(A, p, r)1 x Ar2 i p - 13 for j p to r - 14 do if Aj x5 then i i + 16 exchange Ai Aj7 exchange Ai + 1 Ar8 return i + 1下图是一个例子 这是另外一个可视化图Python实现def quick_sort(ary): return qsort(ary,0,len(ary)-1)def qsort(ary,left,right): #快排函数，ary为待排序数组，left为待排序的左边界，right为右边界 if left = right : return ary ke
5、y = aryleft #取最左边的为基准数 lp = left #左指针 rp = right #右指针 while lp = key and lp rp : rp -= 1 while arylp = key and lp end : break if child+1 = end and arychild arychild+1 : #取较大的子节点 child = child+1 #较大的子节点成为父节点 if aryroot arychild : #交换 aryroot,arychild = arychild,aryroot root = child else : break4、请用Py
6、thon手写实现归并排序。解析：归并排序是采用分治法的一个非常典型的应用。归并排序的思想就是先递归分解数组，再合并数组。先考虑合并两个有序数组，基本思路是比较两个数组的最前面的数，谁小就先取谁，取了后相应的指针就往后移一位。然后再比较，直至一个数组为空，最后把另一个数组的剩余部分复制过来即可。再考虑递归分解，基本思路是将数组分解成left和right，如果这两个数组内部数据是有序的，那么就可以用上面合并数组的方法将这两个数组合并排序。如何让这两个数组内部是有序的？可以再二分，直至分解出的小组只含有一个元素时为止，此时认为该小组内部已有序。然后合并排序相邻二个小组即可。Python实现def m
7、erge_sort(ary): if len(ary) = 1 : return ary num = int(len(ary)/2) #二分分解 left = merge_sort(ary:num) right = merge_sort(arynum:) return merge(left,right) #合并数组def merge(left,right): 合并操作， 将两个有序数组left和right合并成一个大的有序数组 #left与right数组的下标指针 l,r = 0,0 result = while l5、请创建一个函数检查一个词是否具有回文结构，使用 Python 进行编写。解析：def huiwen(str):if len(str)=1:return Trueelse:return str0=str-1 and huiwen(str1:-1)
