Python 面试题 - 堆排序 & 演算过程

清疚 2022-09-18 04:50 120阅读 0赞

### [Python 面试题 - 堆排序 & 演算过程 ][Python _ - _ _ _] ###

分类： [ python面试][python] 2013-03-05 15:16  232人阅读 [评论][Link 1](0) 收藏 [举报][Link 2]

[堆排序][Link 3] [python面试题][python 1]

今天头给我份python招聘的笔试题，让我看看难度如何？

最后编程大题是： 请使用python实现整数数组的推排序？

由于过于一直对于此排序很触头，如何用python实现让我有些头疼，于是度娘理清了下概念，开始自己实现，并附上推演过程。

具体概念请参考：[http://blog.csdn.net/v\_july\_v/article/details/6198644][http_blog.csdn.net_v_july_v_article_details_6198644]

**\[html\]** [ view plain][view plain] [copy][view plain] [print][view plain] [?][view plain]

1.  <span style="font-size:14px;">\#! /usr/bin/env python  
2.  \# -\*- coding: utf-8 -\*-  
3.  \# vim: tabstop=4 shiftwidth=4 softtabstop=4  
4.    
5.  \# TODO: left child  
6.  \# param: index  
7.  \# return: the index of left child  
8.  def leftChild(index):  
9.      return index\*2+1  
10.   
11. \# TODO: right child  
12. \# param: index  
13. \# return: the index of right child  
14. def rightChild(index):  
15.     return index\*2+2  
16.   
17. \# TODO: max exchange  
18. \# param: array index headSize  
19. def maxHeap(array, index, heapSize):  
20.       
21.     \# 01 Get the left and right node  
22.     leftInd = leftChild(index)  
23.     rightInd = rightChild(index)  
24.       
25.     \# 02 compare the left,right,index vals  
26.     \#    get the max val and ind  
27.     largest = index  
28.     if leftInd < heapSize and array\[index\] < array\[leftInd\]:  
29.         largest = leftInd  
30.       
31.     if rightInd < heapSize and array\[leftInd\] < array\[rightInd\]:  
32.         largest = rightInd  
33.       
34.     \# 03 exchange the largest and index val when index -ne largest and then recursive  
35.     if largest != index:  
36.         array\[largest\], array\[index\] = array\[index\], array\[largest\]  
37.         maxHeap(array,largest,heapSize)  
38.       
39.           
40. \# TODO build the heap  
41. \# param: array  
42. def buildHeap(array):  
43.     for i in range(len(array)/2,-1,-1):  
44.         maxHeap(array,i,len(array))  
45.   
46. \# TODO: heap sort  
47. \# param: array  
48. \# return: heap sorted array  
49. def heapSort(array):  
50.     buildHeap(array)  
51.     for i in range(len(array)-1,0,-1):  
52.         array\[0\], array\[i\] = array\[i\], array\[0\]  
53.         maxHeap(array,0,i)  
54.       
55. arr=\[1,2,7,4,34,25,67\]  
56. heapSort(arr)  
57. print arr</span>

Result: \[1, 2, 4, 7, 25, 34, 67\]

=============华丽的分割线=================

**名词解释：**

初始数组： 输入，需要排序的数组

初始堆：基于初始数组，创建符合堆特征的完全二叉树

大根堆头： 大根堆的根节点

无序堆：对排序中取出大根堆头后的剩余堆。

1\[0\]：1为数组的值，0代表标识位

**以下为推演过程：**

A. 初始数组： 1\[0\] 2\[1\] 7\[2\] 4\[3\] 34\[4\] 25\[5\] 67\[6\]

B. 初始堆：

条件区间：

**\[html\]** [ view plain][view plain] [copy][view plain] [print][view plain] [?][view plain]

1.  <span style="font-size:14px;">range(len(array)/2,-1,-1) \# 即3,2,1,0</span>

子条件区间：

**\[html\]** [ view plain][view plain] [copy][view plain] [print][view plain] [?][view plain]

1.  <span style="font-size:14px;">maxHeap(array,largest,heapSize) \#即 最大值的index</span>

1. 条件：index = len(arr)/2  值为3

leftChild: 3\*2+1=7 rightChild: 3\*2+2=8 此时都大于arrSize(heapSize) Pass

2. 条件:  2

leftChild: 2\*2+1=5 rightChild: 2\*2+2=6 此时最大值67\[6\]，与7\[2\] 交换。

此时数组变为：1\[0\] 2\[1\] 67\[2\] 4\[3\] 34\[4\] 25\[5\] 7\[6\]

2.1 子条件： 6

leftChild: 6\*2+1=13 rightChild: 6\*2+2=14 此时都大于arrSize(heapSize) 递归回归

3. 条件： 1

leftChild: 1\*2+1=3 rightChild: 1\*2+2=4 此时最大值34\[4\]，与2\[1\]交换

此时数组变为：1\[0\] 34\[1\] 67\[2\] 4\[3\] 2\[4\] 25\[5\] 7\[6\]

3.1 子条件：4

leftChild: 4\*2+1=9 rightChild: 4\*2+2=10 此时都大于arrSize(heapSize) 递归回归

4. 条件：0

leftChild: 0\*2+1=1 rightChild: 0\*2+2=2 此时最大值67\[2\]，与1\[0\]交换

此时数组变为： 67\[0\] 34\[1\] 1\[2\] 4\[3\] 2\[4\] 25\[5\] 7\[6\]

4..1 子条件: 2

leftChild: 2\*2+1=5 rightChild: 2\*2+2=6 此时最大值25\[5\]， 与1\[2\]交换

此时数组变为： 67\[0\] 34\[1\] 25\[2\] 4\[3\] 2\[4\] 1\[5\] 7\[6\]

4.2 子条件：5

leftChild: 5\*2+1=11 rightChild: 5\*2+2=12 此时都大于arrSize(heapSize) 递归回归

初始堆为：67\[0\] 34\[1\] 25\[2\] 4\[3\] 2\[4\] 1\[5\] 7\[6\]

树形展示为：

67\[0\]  
                    /        \\  
               34\[1\]     25\[2\]  
                /   \\          /    \\  
            4\[3\] 2\[4\] 1\[5\]  7\[6\]

C 堆排序：

注意： 条件一直是无序堆的0

1. 交换大堆根头和最后的一个元素。

交换67\[0\]与7\[6\]，并将67\[0\]从无序堆中取出，此时无序堆: 7\[0\] 34\[1\] 25\[2\] 4\[3\] 2\[4\] 1\[5\]

根据条件 0 来整理无序堆(逻辑同上): 34\[0\] 7\[1\] 25\[2\] 4\[3\] 2\[4\] 1\[5\]

2.  交换34\[0\]与1\[5\]，并将34\[0\]从无序堆中取出，此时无序堆: 1\[0\] 7\[1\] 25\[2\] 4\[3\] 2\[4\]

根据条件 0 来整理无序堆为：25\[0\] 7\[1\] 1\[2\] 4\[3\] 2\[4\]

3. 重复1和2

最后无序堆中的元素全部取出，并组成堆排序的最后结果。

\[1, 2, 4, 7, 25, 34, 67\]

【备注】 至未能描述清楚处，望抿然一笑，并指正之。

[Python _ - _ _ _]: http://blog.csdn.net/soft_lawrency/article/details/8637857
[python]: http://blog.csdn.net/soft_lawrency/article/category/1357466
[Link 1]: http://blog.csdn.net/soft_lawrency/article/details/8637857#comments
[Link 2]: http://blog.csdn.net/soft_lawrency/article/details/8637857#report
[Link 3]: http://blog.csdn.net/tag/details.html?tag=%e5%a0%86%e6%8e%92%e5%ba%8f
[python 1]: http://blog.csdn.net/tag/details.html?tag=python%e9%9d%a2%e8%af%95%e9%a2%98
[http_blog.csdn.net_v_july_v_article_details_6198644]: http://blog.csdn.net/v_july_v/article/details/6198644
[view plain]: http://blog.csdn.net/soft_lawrency/article/details/8637857#