關(guān)于Python的排序算法

　　各類排序?qū)Ρ?/p>

　　排序方法　　穩(wěn)定性　　最好復(fù)雜度　　最壞復(fù)雜度　　期望復(fù)雜度

　　冒泡排序　　穩(wěn)定　　O(n)O(n)O(n)　　O(n2)O(n^2)O(n2)　　O(n2)O(n^2)O(n2)

　　選擇排序　　穩(wěn)定　　O(n2)O(n^2)O(n2)　　O(n2)O(n^2)O(n2)　　O(n2)O(n^2)O(n2)

　　插入排序　　穩(wěn)定　　O(n)O(n)O(n)　　O(n2)O(n^2)O(n2)　　O(n2)O(n^2)O(n2)

　　快速排序　　不穩(wěn)定　　O(n)O(n)O(n)　　O(n2)O(n^2)O(n2)　　O(nlogn)O(nlogn)O(nlogn)

　　歸并排序　　穩(wěn)定　　O(nlogn)O(nlogn)O(nlogn)　　O(nlogn)O(nlogn)O(nlogn)　　O(nlogn)O(nlogn)O(nlogn)

　　冒泡排序

　　核心思路是與相鄰的元素比較大小，交換位置。

　　具體步驟可分為外循環(huán)和內(nèi)循環(huán)：

　　外循環(huán)每一步將數(shù)組中最大的元素“沉”到數(shù)組末尾(升序排列的情況下);

　　內(nèi)循環(huán)每一步按照大小交換相鄰元素的位置。

　　原數(shù)組： [1,2,9,9,4,5,6,6,3,9,4]

　　內(nèi)循環(huán)第一步：將元素1與元素2進行比較，不交換位置(升序);

　　內(nèi)循環(huán)第二步：將元素2與元素9進行比較，不交換位置;

　　內(nèi)循環(huán)第三步：將元素9與元素9進行比較，不交換位置;

　　內(nèi)循環(huán)第四步：將元素9與元素4進行比較，交換位置為 [1,2,9,4,9,5,6,6,3,9,4];

　　內(nèi)循環(huán)第五步：將元素9與元素5進行比較，交換位置為 [1,2,9,4,5,9,6,6,3,9,4];

　　內(nèi)循環(huán)第六步：將元素9與元素6進行比較，交換位置為 [1,2,9,4,5,6,9,6,3,9,4];

　　...

　　內(nèi)循環(huán)最后一步：將元素9與元素6進行比較，交換位置為 [1,2,9,4,5,6,6,3,9,4,9];

　　外循環(huán)第一步即為內(nèi)循環(huán)的結(jié)果，將元素9沉到末尾，為[1,2,9,4,5,6,6,3,9,4,9];

　　外循環(huán)第二步：將第二個元素9沉到末尾，為[1,2,4,5,6,6,3,9,4,9,9];

　　外循環(huán)第三步：將第三個元素9沉到末尾，為[1,2,4,5,6,3,6,4,9,9,9];

　　外循環(huán)第四步：將第三個元素9沉到末尾，為[1,2,4,5,3,6,4,6,9,9,9];

　　...

　　外循環(huán)最后一步：得到最終結(jié)果[1,2,3,4,4,5,6,6,9,9,9]。

　　算法實現(xiàn)

　　冒泡排序是一種穩(wěn)定排序;

　　最優(yōu)情況下，數(shù)組都為正序，時間復(fù)雜度為O(n)O(n)O(n);

　　最壞情況為逆序，時間復(fù)雜度為O(n2)O(n^2)O(n2)。

　　def bubbleSort(nums):

　　if len(nums) < 2:

　　return nums

　　# 因為后面index要加1進行比較，所以這里是len(nums) - 1

　　for i in range(len(nums)-1):

　　# -i是已經(jīng)將i個元素沉到末尾

　　for j in range(len(nums)-i-1):

　　if nums[j] > nums[j+1]:

　　nums[j], nums[j+1] = nums[j+1], nums[j]

　　return nums

　　選擇排序

　　核心思想是將剩余元素中最小(最大)的元素取出來，放在首位(末尾)。

　　具體步驟為：

　　遍歷n個元素，找到其中最小的元素放在首位;

　　遍歷剩下的n-1個元素，找到其中最小的元素放在首位;

　　重復(fù)上述步驟，直到數(shù)組有序。

　　算法實現(xiàn)

　　選擇排序的時間復(fù)雜度跟初始狀態(tài)無關(guān)，為O(n2)O(n^2)O(n2)。

　　def selectionSort(nums):

　　if len(nums) < 2:

　　return nums

　　for i in range(len(nums)-1):

　　min_index = i

　　for j in range(i+1,len(nums)):

　　if nums[j] < nums[min_index]:

　　min_index = j

　　nums[min_index], nums[i] = nums[i], nums[min_index]

　　return nums

　　插入排序

　　核心思想是在已經(jīng)部分有序的數(shù)組中，尋找合適的位置并插入新元素。

　　具體步驟如下：

　　從數(shù)組的第二個元素開時，判斷與前一個元素的大小，進行位置交換;

　　到第三個元素，前兩個元素已經(jīng)有序了，按大小尋找合適的位置，插入第三個元素;

　　如此類推，直到所有的元素都處于合適的位置。

　　算法實現(xiàn)

　　插入排序是一種穩(wěn)定排序，最優(yōu)情況下，數(shù)組都為正序，時間復(fù)雜度為O(n)O(n)O(n)。最壞情況為逆序，時間復(fù)雜度為O(n2)O(n^2)O(n2)。

　　def insertSort(nums):

　　if len(nums) < 2:

　　return nums

　　for i in range(1,len(nums)):

　　value = nums[i]

　　j = i - 1

　　while j >= 0 and nums[j] > value:

　　nums[j+1] = nums[j]

　　j -= 1

　　nums[j+1] = value

　　return nums

　　if __name__ == "__main__":

　　nums = [1,2,9,9,4,5,6,6,3,9,4]

　　print(insertSort(nums))

　　輸出：[1, 2, 3, 4, 4, 5, 6, 6, 9, 9, 9]

　　快速排序

　　核心思想是分而治之。具體步驟如下：

　　在數(shù)組中選擇一個元素作為基準，可以取任意值，但一般取中值幫助理解;

　　數(shù)組中所有的數(shù)組都與基準進行比較，比基準小就移動基準的左邊，比基準大就移動到基準右邊;

　　以基準兩邊的子數(shù)組作為新數(shù)組，重復(fù)第一二步，直到子數(shù)組剩下一個元素。

　　分治思想的排序在處理大數(shù)據(jù)集的效果比較好，小數(shù)據(jù)性能差一些，規(guī)模達到一定小時改用插入排序。

　　算法實現(xiàn)

　　快排是一種不穩(wěn)定排序，其期望時間復(fù)雜度為O(nlogn)O(nlogn)O(nlogn)，最壞情況時間復(fù)雜度為O(n2)O(n^2)O(n2)。

　　快排的實現(xiàn)多種多樣，選取一個最好理解的：分治+遞歸。

　　def quickSort(nums):

　　if len(nums) < 2:

　　return nums

　　mid = nums[len(nums)//2]

　　left, right = [], []

　　nums.remove(mid)

　　for num in nums:

　　if num >= mid:

　　right.append(num)

　　else:　無錫婦科醫(yī)院 http://www.bhnnk120.com/

　　left.append(num)

　　return quickSort(left) + [mid] + quickSort(right)

　　if __name__ == "__main__":

　　nums = [1,2,9,9,4,5,6,6,3,9,4]

　　print(quickSort(nums))

　　輸出：[1, 2, 3, 4, 4, 5, 6, 6, 9, 9, 9]

　　歸并排序

　　歸并排序也應(yīng)用了分治的思想，主要步驟如下：

　　把初始序列的n個元素都看作是有序的子序列;

　　進行兩兩歸并，有序序列的長度增加一倍;

　　重復(fù)上述步驟，直到得到一個長度為n的有序序列。

　　可以結(jié)合下圖觀察：

　　一開始將序列[38, 27, 43, 3, 9, 82, 10]分為7個長度為1的序列;

　　進行兩兩歸并，得到4個有序序列[27,38]，[3,43]，[9,82]，[10];

　　再次進行兩兩歸并，得到兩個有序序列[3,27,38,43]，[9,10,82];

　　直到最后歸并為一個長度為7的有序序列[3,9,10,27,38,43,82]

　　算法實現(xiàn)

　　歸并排序是一種穩(wěn)定排序，最好最差時間復(fù)雜度均為O(nlogn)O(nlogn)O(nlogn)，因此期望復(fù)雜度也為O(nlogn)O(nlogn)O(nlogn)。

　　def merge(left, right):

　　res = []

　　i, j = 0, 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

　　if i == len(left):

　　res += right[j:]

　　else:

　　res += left[i:]

　　return res

　　def mergeSort(nums):

　　if len(nums) <= 1: return nums

　　mid = len(nums)//2

　　left = mergeSort(nums[:mid])

　　right = mergeSort(nums[mid:])

　　return merge(left, right)

　　簡化寫法

　　以.pop代替兩個指針的操作(.pop時間復(fù)雜度為O(1)O(1)O(1));

　　返回不判斷 left 還是 right 為空，因為必然一個為空，另一個不為空;

　　left 和 right 有序，所以直接拼接起來即可。

　　def merge(left, right):

　　res = []

　　while left and right:

　　if left[0] <= right[0]:

　　res.append(left.pop(0))

　　else:

　　res.append(right.pop(0))

　　return res + left + right

　　def mergeSort(nums):

　　if len(nums) <= 1: return nums

　　mid = len(nums)//2

　　left = mergeSort(nums[:mid])

　　right = mergeSort(nums[mid:])

　　return merge(left, right)

　　2019.7.15 補充插入排序

　　2019.7.16 補充冒泡排序，選擇排序，增加對比表格

　　2019.7.30 補充歸并排序