寫在前面
看到好像春招都已經陸續都開始了，最近抽空打算把自己和朋友的經驗整理一下分享出來。作為一個剛剛經曆秋招打擊的自閉兒童，可以非常負責任地說手撕算法是面試中必考的點，而且非常重要。
這一篇就從最常見的排序算法開始。
1.排序及其分類
所謂排序就是将一組無序的記錄序列調整為有序的記錄序列。
- 選擇排序：主要包括簡單選擇排序和堆排序
- 插入排序：簡單插入排序、希爾排序
- 交換排序：冒泡排序、快速排序
- 歸并排序
- 非比較排序：計數排序、桶排序、基數排序屬于非比較排序，算法時間複雜度O(n)， 屬于空間換時間。
2. 經典排序的python實作
2.1 選擇排序
從待排序的資料元素中選出最小的一個元素，存放在序列的起始位置，直到全部帶排序的資料元素排完。
def select_sort(lists):
n = len(list)
for i in range(n):
for j in range(i,n):
if list[i]<list[j]:
list[i],list[j]=list[j],list[i]
return lists
複制
2.2 插入排序
插入排序的基本操作就是将一個資料插入到已經排好序的有序資料中，進而得到一個新的、個數加一的有序資料。算法适用于少量資料的排序，時間複雜度為O(n^2)。
插入算法把要排序的數組分成兩部分：第一部分包含了這個數組的所有元素，但将最後一個元素除外（讓數組多一個空間才有插入的位置），而第二部分就隻包含這一個元素（即待插入元素）。在第一部分排序完成後，再将這個最後元素插入到已排好序的第一部分中。步驟如下：
- 假設序列的第一個數是排序好的，（如果序列長度為1，那就更好了，不用排序了）。
- 取出已排序的數的下一個數，目前這個數是需要排序的（未排序）。用目前這個數與之前排序好的數進行比較，比較的順序是從後往前。
- 如果目前已經排序的數比未排序的數大，則已經排序的數往後挪一個位置，空出目前已經排序位置，下次比較的已經排序好的數是目前已經排序好的數的前一個數。
- 重複步驟3，直到未排序的數小于已排序的數，将未排序的數插入到空出的位置。
- 重複2-5 ，直到所有數都排序好
def insert_sort(lists):
size = len(lists)
for i in range(1, size):
key = lists[i]
j = i-1
while j >= 0:
if lists[j] > key:
lists[j+1] = lists[j]
lists[j] = key
j -= 1
return lists
複制
2.3 希爾排序
希爾排序是插入排序的一種。克服了插入排序每次隻比較相鄰元素的缺陷。
基本思想：
把記錄按下标的一定增量進行分組，對每組直接使用插入排序算法排序；随着增量逐漸減少，每組包含的關鍵詞越來越多，當增量減至1時，整個檔案恰被分成一組，算法便終止。
def shell_sort(lists):
n =len(lists)
dist = n // 2
while dist>0:
for i in range(dist,n):
temp = lists[i]
j = i
while j >= dist and temp < lists[j-dist]:
lists[j] = lists[j-dist]
j -= dist
lists[j] = temp
dist //= 2
return lists
複制
2.4 冒泡排序
重複地走訪過要排序的數列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。
走訪數列的工作是重複地進行直到沒有再需要交換，也就是說該數列已經排序完成。
時間複雜度為O(n^2)
def bubble_sort(lists):
n = len(lists)
for i in range(n):
for j in range(1, n-i): # 每一次冒泡将最大的數交換到數列的最後一位
if lists[j-1] > lists[j]:
lists[j - 1],lists[j] = lists[j], lists[j-1]
return lists
複制
2.5 歸并排序
基本思想：
将數組A[0...n-1]中的元素分成兩個子數組，A1[0...n/2] 和A2[n/2+1...n-1]。分别對這兩個子數組單獨排序（遞歸），然後将已排序的兩個子數組歸并成一個含有n個元素的有序數組。
合并的過程：
比較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的單元。
def merge_sort(lst):
if len(lst) <= 1:
return lst
mid = len(lst) //2
left = merge_sort(lst[:mid])
right = merge_sort(lst[mid:])
return merge(left, right)
def merge(left, right):
res = []
i = j = 0
while i <len(left) and j <len(right):
if left[i] <= right[j]:
res.append(left[i])
i += 1
else:
res.append(right[j])
j += 1
res += left[i:]
res += right[j:]
return res
複制
2.6 堆排序
利用數組的特點快速定位指定索引的元素，堆分為大根堆和小根堆，是完全二叉樹。
基本思想：
- 最大堆調整(adjust_heap): 将堆的末端子節點作調整，使得子節點永遠小于父節點。這是核心步驟，在建堆和堆排序都會用到。比較i的根節點和與其所對應i的孩子節點的值。當i根節點的值比左孩子節點的值要小的時候，就把i根節點和左孩子節點所對應的值交換，當i根節點的值比右孩子的節點所對應的值要小的時候，就把i根節點和右孩子節點所對應的值交換。然後再調用堆調整這個過程，可見這是一個遞歸的過程。
- 建立最大堆(Build_Heap): 将堆所有資料重新排序。建堆的過程其實就是不斷做最大堆調整的過程，從len/2出開始調整，一直比到第一個節點。
- 堆排序(Heap_Sort): 移除位在第一個資料的根節點，并做最大堆調整的遞歸運算。堆排序是利用建堆和堆調整來進行的。首先先建堆，然後将堆的根節點選出與最後一個節點進行交換，然後将前面len-1個節點繼續做堆調整的過程。直到将所有的節點取出，對于n個數我們隻需要做n-1次操作。
def heap_sort(lists):
# 堆排序
size = len(lists)
build_heap(lists, size)
for i in range(0, size)[::-1]:
lists[0], lists[i] = lists[i], lists[0]
adjust_heap(lists, 0, i)
return lists
def adjust_heap(lists, i, size):
# 調整堆
lchild = 2 * i + 1
rchild = 2 * i + 2
maxi = i
if lchild < size and lists[maxi] < lists[lchild]:
maxi = lchild
if rchild < size and lists[maxi] < lists[rchild]:
maxi = rchild
if maxi != i:
# 如果做了堆調整則maxi的值等于左節點或者右節點的，這個時候做對調值操作
lists[maxi], lists[i] = lists[i], lists[maxi]
adjust_heap(lists, maxi, size)
def build_heap(lists, size):
# 堆的建構
for i in range(0, int(size/2))[::-1]:
adjust_heap(lists, i, size)
複制
2.7 快速排序
快速排序是一種基于劃分的排序方法,劃分Partition思想：
選取待排序集合A中的某個元素t，按照與t的大小關系重新整理A中元素，使得整理後的序列中所有在t以前出現的元素均小于t，而所有出現在t以後的元素均大于等于t；元素t稱為劃分元素。反複地對A進行劃分達到排序的目的。
劃分算法：
對于數組A[0...n-1]:
- 設定兩個變量i， j：i=0, j=n-1
- 以A[0]為關鍵資料，即key=A[0]
- 從j開始向前搜尋，直到找到第一個小于key的值a[j]，将a[i] = a[j]；
- 從i開始向後搜尋，直到找到第一個大于等于key的值a[i]，a[j] = a[i]；
- 重複第3、4步，直到i≥j.
def quick_sort(lists):
less = []
pivotList = []
more = []
if len(lists) <= 1:
return lists
else:
pivot = lists[0] # 将第一個值作為基準值
for i in lists:
if i < pivot:
less.append(i)
elif i > pivot:
more.append(i)
else:
pivotList.append(i)
less = quick_sort(less)
more = quick_sort(more)
return less + pivotList + more
def QuickSort(myList,start,end):
#判斷low是否小于high,如果為false,直接傳回
if start < end:
i,j = start,end
#設定基準數
base = myList[i]
while i < j:
#如果清單後邊的數,比基準數大或相等,則前移一位直到有比基準數小的數出現
while (i < j) and (myList[j] >= base):
j = j - 1
#如找到,則把第j個元素指派給第個元素i,此時表中i,j個元素相等
myList[i] = myList[j]
#同樣的方式比較前半區
while (i < j) and (myList[i] <= base):
i = i + 1
myList[j] = myList[i]
#做完第一輪比較之後,清單被分成了兩個半區,并且i=j,需要将這個數設定回base
myList[i] = base
#遞歸前後半區
QuickSort(myList, start, i - 1)
QuickSort(myList, j + 1, end)
return myList
複制
2.8 計數排序
基本思想： 對于每一個元素A[i]，确定小于a[i]的元素個數。是以直接可以把a[I]放到輸出數組的相應位置上，比如有5個數小于a[i]，則a[i]應該放在輸出數組的第六個位置上。
def count_sort(a, k): # k = max(a)
n = len(a) # 計算a序列的長度
b = [0 for i in range(n)] # 設定輸出序列并初始化為0
c = [0 for i in range(k + 1)] # 設定計數序列并初始化為0，
for j in a:
c[j] = c[j] + 1
for i in range(1, len(c)):
c[i] = c[i] + c[i-1]
for j in a:
b[c[j] - 1] = j
c[j] = c[j] - 1
return b
複制
2.9 桶排序
基本思想： 把數組A劃分為n個大小相同的區間（即桶），每個子區間各自排序，最後合并。桶排序要求資料的分布必須均勻，否則可能會失效。計數排序是桶排序的一種特殊情況，可以把計數排序當成每個桶裡隻有一個元素的情況。
def bucket_sort(a):
buckets = [0] * ((max(a) - min(a)) + 1) # 初始化桶元素為0
for i in range(len(a)):
buckets[a[i] - min(a)] += 1 # 周遊數組a，在桶的相應位置累加值
b = []
for i in range(len(buckets)):
if buckets[i] != 0:
b += [i + min(a)] * buckets[i]
return b
複制
2.10 基數排序
基本思想： 将待排序的資料按照位數切割成不同的數字，然後按每個位數分别比較。
基數排序可以采用兩種方式：
- LSD（Least Significant Digital）：從待排序元素的最右邊開始計算（如果是數字類型，即從最低位個位開始）。
- MSD（Most Significant Digital）：從待排序元素的最左邊開始計算（如果是數字類型，即從最高位開始）。
def radix_sort(list, d=3): # 預設三位數，如果是四位數，則d=4，以此類推
for i in range(d): # d輪排序
s = [[] for k in range(10)] # 因每一位數字都是0~9，建10個桶
for j in list:
s[int(j / (10 ** i)) % 10].append(j)
re = [a for b in s for a in b]
return re
複制
3.排序算法的比較
- END -