Python程序員面試分類真題20

Python程序員面試分類真題20(總分：100.00，做題時間：90分鐘)面試題(總題數(shù)：8，分?jǐn)?shù)：100.00)1.

如何進(jìn)行選擇排序

（分?jǐn)?shù)：12.50）__________________________________________________________________________________________

正確答案：(選擇排序是一種簡單直觀的排序算法，它的基本原理如下：對于給定的一組記錄，經(jīng)過第一輪比較后得到最小的記錄，然后將該記錄與第一個記錄進(jìn)行交換；接著對不包括第一個記錄以外的其他記錄進(jìn)行第二輪比較，得到最小的記錄并與第二個記錄進(jìn)行位置交換；重復(fù)該過程，直到進(jìn)行比較的記錄只有一個時為止。以數(shù)組{38，65，97，76，13，27，49}為例(假設(shè)要求為升序排列)，具體步驟如下：

第一次排序后：13[659776382749]

第二次排序后：1327[9776386549]

第三次排序后：132738[76976549]

第四次排序后：13273849[976576]

第五次排序后：1327384965[9776]

第六次排序后：132738496576[97]

最后排序結(jié)果：13273849657697

示例代碼如下：

defselect_sort(lists):

#選擇排序

count=len(lists)

foriinrange(0,count):

min=i

forjinrange(i+1,count):

iflists[min]＞lists[j]:

min=j

lists[min],lists[i]=lists[i],lists[min]

returnlists

if__name__=="__main__":

lists=[3,4,2,8,9,5,1]

print'排序前序列為:',

foriin(lists):

print1,

print'\n排序后結(jié)果為:',

foriin(select_sort(lists)):

printi,

程序的運行結(jié)果為：

排序前序列為：3428951

排序后結(jié)果為：1234589

選擇排序是一種不穩(wěn)定的排序方法，最好、最壞和平均情況下的時間復(fù)雜度都為O(n2)，空間復(fù)雜度為O(1)。)解析：[考點]如何進(jìn)行選擇排序2.

如何進(jìn)行插入排序

（分?jǐn)?shù)：12.50）__________________________________________________________________________________________

正確答案：(對于給定的一組記錄，初始時假設(shè)第一個記錄自成一個有序序列，其余的記錄為無序序列；接著從第二個記錄開始，按照記錄的大小依次將當(dāng)前處理的記錄插入到其之前的有序序列中，直至最后一個記錄插入到有序序列中為止。以數(shù)組{38，65，97，76，13，27，49}為例(假設(shè)要求為升序排列)，直接插入排序具體步驟如下：

第一步插入38以后：[38]659776132749

第二步插入65以后：[3865]9776132749

第三步插入97以后：[386597]76132749

第四步插入76以后：[38657697]132749

第五步插入13以后：[1338657697]2749

第六步插入27以后：[132738657697]49

第七步插入49以后：[13273849657697]

示例代碼如下：

definsert_sort(lists):

#插入排序

count=len(lists)

foriinrange(1,count):

key=lists[i]

j=i-1

whilej＞=0:

iflists[j]＞key:

lists[j+1]=lists[j]

lists[j]=key

j-=1

returnlists

if__name__=="__main__":

lists=[3,4,2,8,9,5,1]

print'排序前序列為:',

foriinlists:

printi,

print'\n排序后結(jié)果為:',

forjin(insert_sort(lists)):

printi,

程序的運行結(jié)果為：

排序前序列為：3428951

排序后結(jié)果為：1234589

插入排序是一種穩(wěn)定的排序方法，最好情況下的時間復(fù)雜度為O(n)，最壞情況下的時間復(fù)雜度為O(n2)，平均情況下的時間復(fù)雜度為O(n2)。空間復(fù)雜度為O(1)。)解析：[考點]如何進(jìn)行插入排序3.

如何進(jìn)行冒泡排序

（分?jǐn)?shù)：12.50）__________________________________________________________________________________________

正確答案：(冒泡排序顧名思義就是整個過程就像氣泡一樣往上升，單向冒泡排序的基本思想是(假設(shè)由小到大排序)：對于給定的n個記錄，從第一個記錄開始依次對相鄰的兩個記錄進(jìn)行比較，當(dāng)前面的記錄大于后面的記錄時，交換其位置，進(jìn)行一輪比較和換位后，n個記錄中的最大記錄將位于第n位；然后對前(n-1)個記錄進(jìn)行第二輪比較；重復(fù)該過程直到進(jìn)行比較的記錄只剩下一個時為止。

以數(shù)組{36，25，48，12，25，65，43，57}為例(假設(shè)要求為升序排列)，具體排序過程如下：

初始狀態(tài)：[3625481225654357]

1次排序：[2536122548435765]

2次排序：[251225364348]5765

3次排序：[1225253643]485765

4次排序：[12252536]43485765

5次π序：[122525]3643485765

6次排序：[1225]253643485765

7次排序：[12]25253643485765

示例代碼如下：

defbubble_sort(lists):

#冒泡排序

count=len(lists)

foriinrange(0,count):

forjinrange(i+1,count):

iflists[i]＞lists[j]:

lists[i],lists[j]=lists[j],lists[i]

returnlists

if__name__=="__main__":

lists=[3,4,2,8,9,5,1]

print'排序前序列為:',

foriinlists:

printi,

print'\n排序后結(jié)果為:',

foriin(bubble_sort(lists)):

printi,

程序的運行結(jié)果為：

排序前序列為：3428951

排序后結(jié)果為：1234589

冒泡排序是一種穩(wěn)定的排序方法，最好的情況下的時間復(fù)雜度為O(n)，最壞情況下時間復(fù)雜度為O(n2)，平均情況下的時間復(fù)雜度為O(n2)?？臻g復(fù)雜度為O(1)。)解析：[考點]如何進(jìn)行冒泡排序4.

如何進(jìn)行歸并排序

（分?jǐn)?shù)：12.50）__________________________________________________________________________________________

正確答案：(歸并排序是利用遞歸與分治技術(shù)將數(shù)據(jù)序列劃分成為越來越小的半子表，再對半子表排序，最后再用遞歸步驟將排好序的半子表合并成為越來越大的有序序列。其中“歸”代表的是遞歸的意思，即遞歸地將數(shù)組折半地分離為單個數(shù)組。例如，數(shù)組[2，6，1，0]會先折半，分為[2，6]和[1，0]兩個子數(shù)組，然后再折半將數(shù)組分離，分為[2]，[6]和[1]，[0]?！安ⅰ本褪菍⒎珠_的數(shù)據(jù)按照從小到大或者從大到小的順序再放到一個數(shù)組中。如上面的[2]、[6]合并到一個數(shù)組中是[2，6]，[1]、[0]合并到一個數(shù)組中是[0，1]，然后再將[2，6]和[0，1]合并到一個數(shù)組中即為[0，1，2，6]。

具體而言，歸并排序算法的原理如下：對于給定的一組記錄(假設(shè)共有n個記錄)，首先將每兩個相鄰的長度為1的子序列進(jìn)行歸并，得到n/2(向上取整)個長度為2或1的有序子序列，再將其兩兩歸并，反復(fù)執(zhí)行此過程，直到得到一個有序序列為止。

所以，歸并排序的關(guān)鍵就是兩步：第一步，劃分子表；第二步，合并半子表。以數(shù)組{49，38，65，97，76，13，27}為例(假設(shè)要求為升序排列)，排序過程如下：

示例代碼如下：

defmerge(left,right):

i,j=0,0

result=[]

whilei＜len(left)andj＜len(right):

ifleft[i]＜=right[j]:

result.append(left:[i])

i+=1

else:

result.append(right[j])

j+=1

result+=left[i:]

result+=right[j:]

returnresult

defmerge_sort(lists):

#歸并排序

iflen(lists)＜=1:

returnlists

num=len(lists)/2

left=merge_sort(lists[:num])

right=merge_sort(lists[num:])

returnmerge(left,right)

if__name__=="__main__":

lists=[3,4,2,8,9,5,1]

print'排序前序列為:',

foriinlists:

printi,

print'\n排序結(jié)果為:',

foriin(merge_sort(lists)):

printi,

程序的運行結(jié)果為：

排序前序列為：3428951

排序后結(jié)果為：1234589

二路歸并排序的過程需要進(jìn)行l(wèi)ogn次。每一趟歸并排序的操作，就是將兩個有序子序列進(jìn)行歸并，而每一對有序子序列歸并時，記錄的比較次數(shù)均小于等于記錄的移動次數(shù)，記錄移動的次數(shù)均等于文件中記錄的個數(shù)n，即每一趟歸并的時間復(fù)雜度為O(n)。因此二路歸并排序在最好、最壞和平均情況的時間復(fù)雜度為O(nlogn)，而且是一種穩(wěn)定的排序方法，空間復(fù)雜度為O(1)。)解析：[考點]如何進(jìn)行歸并排序5.

如何進(jìn)行快速排序

（分?jǐn)?shù)：12.50）__________________________________________________________________________________________

正確答案：(快速排序是一種非常高效的排序算法，它采用“分而治之”的思想，把大的拆分為小的，小的再拆分為更小的。其原理是：對于一組給定的記錄，通過一趟排序后，將原序列分為兩部分，其中前部分的所有記錄均比后部分的所有記錄小，然后再依次對前后兩部分的記錄進(jìn)行快速排序，遞歸該過程，直到序列中的所有記錄均有序為止。

具體算法步驟如下：

(1)分解：將輸入的序列array[m,…,n]劃分成兩個非空子序列array[m,…,k]和array[k+1,…,n]，使array[m,…,k]中任一元素的值不大于array[k+1,…,n]中任一元素的值。

(2)遞歸求解：通過遞歸調(diào)用快速排序算法分別對array[m,…,k]和array[k+1,…,n]進(jìn)行排序。

(3)合并：由于對分解出的兩個子序列的排序是就地進(jìn)行的，所以在array[m,…,k]和array[k+1,…,n]都排好序后，不需要執(zhí)行任何計算，array[m,…,n]就已排好序。

以數(shù)組{49，38，65，97，76，13，27，49}為例(假設(shè)要求為升序排列)。

第一次排序過程如下：

初始化關(guān)鍵字[4938659776132749]

第一次交換后：[2738659776134949]

第二次交換后：[2738499776136549]

j向左掃描，位置不變，第三次交換后：[2738139776496549]

i向右掃描，位置不變，第四次交換后：[2738134976976549]

j向左掃描[2738134976976549]

整個排序過程如下：

初始化關(guān)鍵字[4938659776132749]

一次排序之后：[273813]49[76976549]

二次排序之后：[13]27[38]49[4965]76[97]

三次排序之后：1327384949[65]7697

最后的排序結(jié)果：1327384949657697

示例代碼如下：

defquick_sort(lists,left,right):

#快速排序

ifleft＞=right:

returnlists

key=lists[left]

low=left

high=right

whileleft＜right:

whileleft＜rightandlists[right]＞=key:

right-=1

lists[left]=lists[right]

whileleft＜rightandlists[left]＜=key:

left+=1

lists[right]=lists[left]

lists[right]=key

quick_sort(lists,low,left-1)

quick_sort(lists,left+1,high)

returnlists

if__name__=='__main__":

lists=[3,4,2,8,9,5,1]

print'排序前序列為:',

foriin(lists):

printi,

print'\n排序后結(jié)果為:',

foriin(quick_sort(lists,0,len(lists)-1)):

printi,

程序的運行結(jié)果為：

排序前序列為：3428951

排序后結(jié)果為：1234589

當(dāng)初始的序列整體或局部有序時，快速排序的性能將會下降，此時快速排序?qū)⑼嘶癁槊芭菖判颉?/p>

快速排序的相關(guān)特點如下：

(1)最壞時間復(fù)雜度

最壞情況是指每次區(qū)間劃分的結(jié)果都是基準(zhǔn)關(guān)鍵字的左邊(或右邊)序列為空，而另一邊的區(qū)間中的記錄項僅比排序前少了一項，即選擇的基準(zhǔn)關(guān)鍵字是待排序的所有記錄中最小或者最大的。例如，若選取第一個記錄為基準(zhǔn)關(guān)鍵字，當(dāng)初始序列按遞增順序排列時，每次選擇的基準(zhǔn)關(guān)鍵字都是所有記錄中的最小者，這時記錄與基準(zhǔn)關(guān)鍵字的比較次數(shù)會增多。因此，在這種情況下，需要進(jìn)行(n-1)次區(qū)間劃分。對于第k(0＜k＜n)次區(qū)間劃分，劃分前的序列長度為(n-k+1)，需要進(jìn)行(n-k)次記錄的比較。當(dāng)k從1～(n-1)時，進(jìn)行的比較次數(shù)總共為n(n-1)/2，所以在最壞情況下快速排序的時間復(fù)雜度為O(n2)。

(2)最好時間復(fù)雜度

最好情況是指每次區(qū)間劃分的結(jié)果都是基準(zhǔn)關(guān)鍵字左右兩邊的序列長度相等或者相差為1，即選擇的基準(zhǔn)關(guān)鍵字為待排序的記錄中的中間值。此時，進(jìn)行的比較次數(shù)總共為nlogn，所以在最好情況下快速排序的時間復(fù)雜度為O(nlogn)。

(3)平均時間復(fù)雜度

快速排序的平均時間復(fù)雜度為O(nlogn)。雖然快速排序在最壞情況下的時間復(fù)雜度為O(n2)，但是在所有平均時間復(fù)雜度為O(nlogn)的算法中，快速排序的平均性能是最好的。

(4)空間復(fù)雜度

快速排序的過程中需要一個?？臻g來實現(xiàn)遞歸。當(dāng)每次對區(qū)間的劃分都比較均勻時(即最好情況)，遞歸樹的最大深度為為向上取整)；當(dāng)每次區(qū)間劃分都使得有一邊的序列長度為0時(即最好情況)，遞歸樹的最大深度為n。在每輪排序結(jié)束后比較基準(zhǔn)關(guān)鍵字左右的記錄個數(shù)，對記錄多的一邊先進(jìn)行排序，此時，棧的最大深度可降為logn。因此，快速排序的平均空間復(fù)雜度為O(logn)。

(5)基準(zhǔn)關(guān)鍵字的選取

基準(zhǔn)關(guān)鍵字的選擇是決定快速排序算法性能的關(guān)鍵。常用的基準(zhǔn)關(guān)鍵字的選擇有以下幾種方式：

1)三者取中。三者取中是指在當(dāng)前序列中，將其首、尾和中間位置上的記錄進(jìn)行比較，選擇三者的中值作為基準(zhǔn)關(guān)鍵字，在劃分開始前交換序列中的第一個記錄與基準(zhǔn)關(guān)鍵字的位置。

2)取隨機(jī)數(shù)。取left(左邊)和right(右邊)之間的一個隨機(jī)數(shù)m(left≤m≤right)，用n[m]作為基準(zhǔn)關(guān)鍵字。這種方法使得n[left]～n[right]之間的記錄是隨機(jī)分布的，采用此方法得到的快速排序一般稱為隨機(jī)的快速排序。

需要注意快速排序與歸并排序的區(qū)別與聯(lián)系。快速排序與歸并排序的原理都是基于分治思想，即首先把待排序的元素分成兩組，然后分別對這兩組排序，最后把兩組結(jié)果合并起來。

而它們的不同點在于，進(jìn)行的分組策略不同，后面的合并策略也不同。歸并排序的分組策略是假設(shè)待排序的元素存放在數(shù)組中，那么其把數(shù)組前面一半元素作為一組，后面一半元素作為另外一組。而快速排序則是根據(jù)元素的值來分組，即大于某個值的元素放在一組，而小于某個值的元素放在另外一組，該值稱為基準(zhǔn)值。所以，對整個排序過程而言，基準(zhǔn)值的挑選非常重要，如果選擇不合適，太大或太小，那么所有的元素都分在一組了。對于快速排序和歸并排序來說，如果分組策略越簡單，那么后面的合并策略就越復(fù)雜，因為快速排序在分組時，已經(jīng)根據(jù)元素大小來分組了，而合并的時候，只需把兩個分組合并起來就行了，歸并排序則需要對兩個有序的數(shù)組根據(jù)大小進(jìn)行合并。)解析：[考點]如何進(jìn)行快速排序6.

如何進(jìn)行希爾排序

（分?jǐn)?shù)：12.50）__________________________________________________________________________________________

正確答案：(希爾排序也稱為“縮小增量排序”。它的基本原理是：首先將待排序的元素分成多個子序列，使得每個子序列的元素個數(shù)相對較少，對各個子序列分別進(jìn)行直接插入排序，待整個待排序序列“基本有序后”，再對所有元素進(jìn)行一次直接插入排序。

具體步驟如下：

(1)選擇一個步長序列t1，t2，…，tk，滿足ti＞tj(i＜j)，tk=1。

(2)按步長序列個數(shù)k，對待排序序列進(jìn)行k趟排序。

(3)每趟排序，根據(jù)對應(yīng)的步長ti，將待排序列分割成ti個子序列，分別對各個子序列進(jìn)行直接插入排序。

需要注意的是，當(dāng)步長因子為1時，所有元素作為一個序列來處理，其長度為n。以數(shù)組{26，53，67，48，57，13，48，32，60，50}(假設(shè)要求為升序排列)，步長序列{5，3，1}為例。具體步驟如下：

示例代碼如下：

defshell_sort(lists):

#希爾排序

count=len(lists)

step=2

group=count/step

whilegroup＞0:

foriinrange(0,group):

j=i+group

whilej＜count:

k=j-group

key=lists[j]

whilek＞=0:

iflists[k]＞key:

lists[k+group]=lists[k]

lists[k]=key

k-=group

j+=group

group/=step

returnlists

if__name__=="__main__":

lists=[3,4,2,8,9,5,1]

print'排序前序列為:',

foriin(lists):

prmti,

print'\n排序后結(jié)果為:',

foriin(shell_sort(lists)):

printi,

程序的運行結(jié)果為：

排序前序列為：3428951

排序后結(jié)果為：1234589

希爾排序的關(guān)鍵并不是隨便地分組后各自排序，而是將相隔某個“增量”的記錄組成一個子序列，實現(xiàn)跳躍式的移動，使得排序的效率提高。希爾排序是一種不穩(wěn)定的排序方法，平均時間復(fù)雜度為O(nlogn)，最差情況下的時間復(fù)雜度為O(ns)(1＜s＜2)，空間復(fù)雜度為O(1)。)解析：[考點]如何進(jìn)行希爾排序7.

如何進(jìn)行堆排序

（分?jǐn)?shù)：12.50）__________________________________________________________________________________________

正確答案：(堆是一種特殊的樹形數(shù)據(jù)結(jié)構(gòu)，其每個結(jié)點都有一個值，通常提到的堆都是指一棵完全二叉樹，根結(jié)點的值小于(或大于)兩個子結(jié)點的值，同時根結(jié)點的兩個子樹也分別是一個堆。

堆排序是一樹形選擇排序，在排序過程中，將R[1，…，N]看成是一棵完全二叉樹的順序存儲結(jié)構(gòu)，利用完全二叉樹中雙親結(jié)點和孩子結(jié)點之間的內(nèi)在關(guān)系來選擇最小的元素。

堆一般分為大頂堆和小頂堆兩種不同的類型。對于給定n個記錄的序列(r(1),r(2),…,r(n))，當(dāng)且僅當(dāng)滿足條件(r(i)≥r(2i),i=1,2,…,n)時稱之為大頂堆，此時堆頂元素必為最大值。對于給定n個記錄的序列(r(1),r(2),…,r(n))，當(dāng)且僅當(dāng)滿足條件(r(i)≤r(2i+1),i=1,2,…,n)時稱之為小頂堆，此時堆頂元素必為最小值。

堆排序的思想是對于給定的n個記錄，初始時把這些記錄看作為一棵順序存儲的二叉樹，然后將其調(diào)整為一個大頂堆，然后將堆的最后一個元素與堆頂元素(即二叉樹的根結(jié)點)進(jìn)行交換后，堆的最后一個元素即為最大記錄；接著將前(n-1)個元素(即不包括最大記錄)重新調(diào)整為一個大頂堆，再將堆頂元素與當(dāng)前堆的最后一個元素進(jìn)行交換后得到次大的記錄，重復(fù)該過程直到調(diào)整的堆中只剩一個元素時為止，該元素即為最小記錄，此時可得到一個有序序列。

堆排序主要包括兩個過程：一是構(gòu)建堆；二是交換堆頂元素與最后一個元素的位置。

示例代碼如下：

defadjust_heap(lists,i,size):

lchild=2*1+1

rchild=2*i+2

maxs=i

ifi＜size/2:

iflchild＜sizeandlists[lchild]＞lists[maxs]:

maxs=lchild

ifrchild＜sizeandlists[rchild]＞lists[maxs]:

maxs=rchild

ifmaxs!=i:

lists[maxs],lists[i]=lists[i],lists[maxs]

adjust_heap(lists,maxs,size)

defbuild_heap(lists,size):

foriinrange(0,(size/2))[::-1]:

adjust_heap(lists,i,size)

defheap_sort(lists):

size=len(lists)

build_heap(lists,size)

foriinrange(0,size)[::-1]:

lists[0],lists[i]=lists[i],lists[0]

adjust_heap(lists,0,i)

if__name__=="__main__":

lists=[3,4,2,8,9,5,1]

print'排序前序列為:',

foriinlists:

printi,

print'\n排序后結(jié)果為:',

heap_sort(lists)

foriinlists:

printi,

程序的運行結(jié)果為：

排序前序列為：3428951

排序后結(jié)果為：1234589

堆排序方法對記錄較少的文件效果一般，但對于記錄較多的文件還是很有效的，其運行時間主要耗費在創(chuàng)建堆和反復(fù)調(diào)整堆上。堆排序即使在最壞情況下，其時間復(fù)雜度也為O(nlogn)。它是一種不穩(wěn)定的排序方法。)解析：[考點]如何進(jìn)行堆排序8.

如何進(jìn)行基數(shù)排序

（分?jǐn)?shù)：12.50）__________________________________________________________________________________________

正確答案：(基數(shù)排序(radixsort)屬于“分配式排序”(distributionsort)，又稱“桶子法”(bucketsort或binsort)，排序的過程就是將最低位優(yōu)先法用于單關(guān)鍵字的情況。下面以[73，22，93，43，55，14，28，65，39，81]為例來介紹