用python實(shí)現(xiàn)經(jīng)典排序算法
01 冒泡排序
時(shí)間復(fù)雜度：O(n^2)
算法描述：
比較相鄰的元素，如果第一個(gè)比第二個(gè)大，就交換它們兩個(gè)；對(duì)每一對(duì)相鄰元素作同樣的工作，從開始第一對(duì)到結(jié)尾的最后一對(duì)，這樣在最后的元素應(yīng)該會(huì)是最大的數(shù)；針對(duì)所有的元素重復(fù)以上的步驟，除了最后一個(gè)；重復(fù)上述步驟，直到排序完成。
算法實(shí)現(xiàn)：
def bubbleSort(alist):n = len(alist)for j in range(n - 1):????????count?=?0??for i in range(n - 1 - j):if alist[i] > alist[i + 1]:alist[i], alist[i + 1] = alist[i + 1], alist[i]count += 1if count == 0:breakreturn alist
02?選擇排序
時(shí)間復(fù)雜度：O(n^2)
算法描述：
首先從未排序的序列中找到最小（大）的元素，存放到排序序列的起始位置，然后，再從剩余未排序元素中繼續(xù)尋找最小（大）元素，然后放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。
算法實(shí)現(xiàn)：
def selectSort(alist):n = len(alist)for i in range(n):for j in range(i + 1, n):if alist[i] > alist[j]:alist[i], alist[j] = alist[j], alist[i]return alist
03?插入排序
時(shí)間復(fù)雜度：O(n^2)
算法描述：
原理是通過構(gòu)建有序序列，對(duì)于未排序數(shù)據(jù)，在已排序序列中從后往前掃描，找到相應(yīng)位置并插入。
核心在于把一個(gè)無序序列看成兩個(gè)數(shù)列，如第一個(gè)元素構(gòu)成了第一個(gè)數(shù)列，那剩余元素構(gòu)成第二個(gè)數(shù)列，顯然第一個(gè)數(shù)列是有序的（只有一個(gè)元素），把第二個(gè)數(shù)列中的第一個(gè)元素拿出來插到第一個(gè)數(shù)列，使它構(gòu)成一個(gè)有序數(shù)列，直到第二個(gè)數(shù)列中的元素全部插入到第一個(gè)數(shù)列。
將待插入元素與前一個(gè)元素進(jìn)行比較，若小于，則將前一個(gè)元素后移一位，再跟前前一位進(jìn)行比較，直到遇到小于待插入元素，插入到該位后一位。
算法實(shí)現(xiàn)：
def insertSort(alist):n = len(alist)for j in range(1, n):i = jwhile i > 0:if alist[i] < alist[i - 1]:alist[i], alist[i - 1] = alist[i - 1], alist[i]i -= 1else:????????????????breakreturn alist
04?希爾排序（縮小增量排序）
時(shí)間復(fù)雜度：O(n^1.3)
算法描述：
是插入排序的優(yōu)化版，當(dāng)數(shù)據(jù)規(guī)模較小或數(shù)據(jù)已基本有序時(shí)非常有效。
希爾排序是把記錄按下標(biāo)的一定增量分組，對(duì)每組使用直接插入排序算法排序，隨著增量逐漸減少，每組包含的關(guān)鍵詞越來越多，當(dāng)增量減至1時(shí)，整個(gè)文件恰被分成一組，算法終止。
算法實(shí)現(xiàn)：
def?shellSort(alist):????n =?len(alist)t = n // 2while t > 0:for i in range(t, n):j, cur = i, alist[i]while (j - t >= 0) and (cur < alist[j - t]):alist[j] = alist[j - t]j = j - talist[j] = curt = t // 2return alist
05?歸并排序
時(shí)間復(fù)雜度：O(nlogn)
算法描述：
先按組拆，拆到都剩單獨(dú)一個(gè)數(shù)據(jù)為止，再按照拆分的順序進(jìn)行合并，小的在前，大的在后，使用左右兩個(gè)游標(biāo)進(jìn)行比較。
分析時(shí)間復(fù)雜度：因?yàn)樯婕斑f歸所以不通過代碼來看。橫向?yàn)閚次，縱向是除二除二，也就是logn，最壞最好都是nlogn，需要額外空間復(fù)雜度。
穩(wěn)定性：代碼中可保證穩(wěn)定。
算法實(shí)現(xiàn)：
def mergeSort(alist):n = len(alist)if n <= 1:return alistmid = n // 2 #求得列表中間位置#對(duì)左邊列表進(jìn)行歸并排序left_list = mergeSort(alist[:mid])#對(duì)右邊列表進(jìn)行歸并排序right_list = mergeSort(alist[mid:])#將兩個(gè)有序的子序列進(jìn)行合并right_pointer = 0, 0result = []while left_pointer < len(left_list) and right_pointer < len(right_list):if left_list[left_pointer] < right_list[right_pointer]:result.append(left_list[left_pointer])left_pointer += 1else:result.append(right_list[right_pointer])right_pointer += 1#走到頭之后，將剩下的部分直接添加上result += left_list[left_pointer:]result += right_list[right_pointer:]return result
06?快速排序
時(shí)間復(fù)雜度：O(nlogn)
算法描述：
通過一趟排序?qū)⒋庞涗浄指舫瑟?dú)立的兩部分，一部分記錄的關(guān)鍵字比另一部分的關(guān)鍵字小，則可分別對(duì)這兩部分繼續(xù)進(jìn)行排序，代價(jià)是需要額外的內(nèi)存空間。
算法實(shí)現(xiàn)：
def quickSort(alist, first, last):if first >= last:returnmid_value = alist[first]low = firsthigh = lastwhile low < high:#high左移while low < high and alist[high] >= mid_value:high -= 1alist[low] = alist[high]while low < high and alist[low] < mid_value:low += 1alist[high] = alist[low]#從循環(huán)退出時(shí),low=highalist[low] = mid_value#對(duì)low左邊的列表執(zhí)行快速排序quickSort(alist, first, low - 1)#對(duì)low右邊的列表執(zhí)行快速排序quickSort(alist, low + 1, last)
完結(jié)。
能力有限，所以我就學(xué)習(xí)了以上六種排序算法。面試中遇到過冒泡、歸并和快排的手寫代碼考察。筆試中好像堆排序會(huì)經(jīng)常考察，然而我是真的沒學(xué)會(huì)。你們可不要學(xué)我，想進(jìn)一步學(xué)習(xí)的可以參考這里（https://b23.tv/yj3k6y）的方法講述。
友情提示：百分之八九十的數(shù)分筆試都會(huì)手撕算法coding（數(shù)據(jù)結(jié)構(gòu)），這方面能力欠缺的同學(xué)建議多練習(xí)，多思考，別學(xué)我。或者抓住提前批（一些公司沒有筆試）的機(jī)會(huì)，還有某些廠筆試不考手撕算法的機(jī)會(huì)。