關于Python的排序算法

　　各類排序對比

　　排序方法　　穩定性　　最好復雜度　　最壞復雜度　　期望復雜度

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

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

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

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

　　歸并排序　　穩定　　O(nlogn)O(nlogn)O(nlogn)　　O(nlogn)O(nlogn)O(nlogn)　　O(nlogn)O(nlogn)O(nlogn)

　　冒泡排序

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

　　具體步驟可分為外循環和內循環：

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

　　內循環每一步按照大小交換相鄰元素的位置。

　　原數組： [1,2,9,9,4,5,6,6,3,9,4]

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

　　內循環第二步：將元素2與元素9進行比較，不交換位置;

　　內循環第三步：將元素9與元素9進行比較，不交換位置;

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

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

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

　　...

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

　　外循環第一步即為內循環的結果，將元素9沉到末尾，為[1,2,9,4,5,6,6,3,9,4,9];

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

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

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

　　...

　　外循環最后一步：得到最終結果[1,2,3,4,4,5,6,6,9,9,9]。

　　算法實現

　　冒泡排序是一種穩定排序;

　　最優情況下，數組都為正序，時間復雜度為O(n)O(n)O(n);

　　最壞情況為逆序，時間復雜度為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是已經將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個元素，找到其中最小的元素放在首位;

　　重復上述步驟，直到數組有序。

　　算法實現

　　選擇排序的時間復雜度跟初始狀態無關，為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

　　插入排序

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

　　具體步驟如下：

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

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

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

　　算法實現

　　插入排序是一種穩定排序，最優情況下，數組都為正序，時間復雜度為O(n)O(n)O(n)。最壞情況為逆序，時間復雜度為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]

　　快速排序

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

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

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

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

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

　　算法實現

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

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

　　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:　無錫婦科醫院 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]

　　歸并排序

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

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

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

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

　　可以結合下圖觀察：

　　一開始將序列[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]

　　算法實現

　　歸并排序是一種穩定排序，最好最差時間復雜度均為O(nlogn)O(nlogn)O(nlogn)，因此期望復雜度也為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時間復雜度為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 補充歸并排序