images
插入排序
思路
- 從第一個(gè)元素開始胎源，該元素可以認(rèn)為已經(jīng)被排序耻卡；
- 取出下一個(gè)元素，在已經(jīng)排序的元素序列中從后向前掃描疯淫；
- 如果該元素（已排序）大于新元素地来，將該元素移到下一位置；
- 重復(fù)步驟3熙掺，直到找到已排序的元素小于或者等于新元素的位置未斑；
- 將新元素插入到該位置；
- 重復(fù)步驟2~5币绩。
代碼
def insertSort(arr):
length = len(arr)
for i in range(length-1):
for j in range(length-1-i):
if arr[j] > arr[j+1]:
temp = arr[j+1]
arr[j+1] = arr[j]
arr[j] = temp
return arr
圖示
images
平均時(shí)間復(fù)雜度
O(n^2)
希爾排序
前言
希爾排序是插排的升級(jí)蜡秽，先將待排序的元素進(jìn)行分組，在分組的基礎(chǔ)上進(jìn)行插排缆镣，從而降低整體上的時(shí)間復(fù)雜度芽突。
這里面設(shè)計(jì)到一個(gè)增量的概念，我們依據(jù)增量來決定分組的跨度董瞻。常用的增量有三種：
- 希爾增量 [1,2,4,8,...,2^(k-1)]
- 海巴德增量 [1,3,7,15,...,2^k-1]
- 塞基維克增量 [1,5,19,41,...,4k-3*2k+1]
一般情況下希爾增量帶來的時(shí)間復(fù)雜度小于O(n^2),但在極壞情況下可能效果不明顯甚至超過這個(gè)值寞蚌。海巴德增量可以將時(shí)間復(fù)雜控制在O(n^(3/2))以下，而塞基維克增量該項(xiàng)參數(shù)為O(n^(4/3))。
思路
- 擇定增量
- 分組
- 組內(nèi)比較
- 重復(fù)步驟2,3直到跨度為1
圖示
images
代碼
def shellSort(arr):
length=len(arr)
gap=int(length/2)
while gap>0:
for i in range(gap,length):
j=i
current=arr[i]
while(j-gap>=0 and current<arr[j-gap]):
arr[j]=arr[j-gap]
j=j-gap
arr[j]=current
gap=int(gap/2)
return arr
選擇排序
思路
- 選出數(shù)組中最大（最行印）的元素放到開頭
- 在剩下的元素中選中最大（最幸疾浮）元素放到上個(gè)被選元素之后
- 重復(fù)2步驟
圖示
images
代碼
def selectSort(arr):
length = len(arr)
minIndex, temp = 0, ""
for i in range(length-1):
minIndex = i
for j in range(i+1, length):
if arr[j] < arr[minIndex]:
minIndex = j
temp = arr[i]
arr[i] = arr[minIndex]
arr[minIndex] = temp
return arr
平均時(shí)間復(fù)雜度
O(2^n)
堆排序
前言
堆排序，顧名思義煞聪，就是基于堆斗躏。因此先來介紹一下堆的概念。
堆分為最大堆和最小堆昔脯，其實(shí)就是完全二叉樹啄糙。最大堆要求節(jié)點(diǎn)的元素都要大于其孩子，最小堆要求節(jié)點(diǎn)元素都小于其左右孩子云稚，兩者對(duì)左右孩子的大小關(guān)系不做任何要求隧饼，其實(shí)很好理解。有了上面的定義静陈，我們可以得知燕雁，處于最大堆的根節(jié)點(diǎn)的元素一定是這個(gè)堆中的最大值。其實(shí)我們的堆排序算法就是抓住了堆的這一特點(diǎn)鲸拥，每次都取堆頂?shù)脑毓崭瘢瑢⑵浞旁谛蛄凶詈竺妫缓髮⑹Ｓ嗟脑刂匦抡{(diào)整為最大堆刑赶，依次類推捏浊，最終得到排序的序列。
思路
- 把堆頂?shù)淖畲髷?shù)取出
- 將剩余的堆繼續(xù)調(diào)整為最大堆
- 重復(fù)步驟1,2
圖示
images
代碼
from collections import deque
def swap(L, i, j):
L[i], L[j] = L[j], L[i]
return L
def heap(L, start, end):
temp = L[start]
i = start
j = 2 * i
while j <= end:
if (j < end) and (L[j] < L[j + 1]):
j += 1
if temp < L[j]:
L[i] = L[j]
i = j
j = 2 * i
else:
break
L[i] = temp
def sort(L):
L_length = len(L) - 1
first_sort_count = int(L_length / 2)
for i in range(first_sort_count):
heap(L, first_sort_count - i, L_length)
for i in range(L_length - 1):
L = swap(L, 1, L_length - i)
heap(L, 1, L_length - i - 1)
return [L[i] for i in range(1, len(L))]
def heapSort(nums):
L = deque(nums)
L.appendleft(0)
return sort(L)
平均時(shí)間復(fù)雜度
O(n)
冒泡排序
思路
- 比較相鄰的元素撞叨。如果第一個(gè)比第二個(gè)大金踪，就交換他們兩個(gè)。
- 對(duì)每一對(duì)相鄰元素做同樣的工作牵敷，從開始第一對(duì)到結(jié)尾的最后一對(duì)胡岔。在這一點(diǎn)，最后的元素應(yīng)該會(huì)是最大的數(shù)枷餐。
- 針對(duì)所有的元素重復(fù)以上的步驟靶瘸，除了最后一個(gè)。
- 持續(xù)每次對(duì)越來越少的元素重復(fù)上面的步驟毛肋，直到?jīng)]有任何一對(duì)數(shù)字需要比較怨咪。
圖示
images
代碼
def bubbleSort(arr):
length=len(arr)
for i in range(length-1):
for j in range(length-1-i):
if arr[j]>arr[j+1]:
temp=arr[j+1]
arr[j+1]=arr[j]
arr[j]=temp
return arr
平均時(shí)間復(fù)雜度
O(n^2)
快速排序
思路
- 先從集合中取出一個(gè)數(shù)作為“哨兵”
- 將集合中比哨兵大的元素和比哨兵小的元素分列兩側(cè)
- 再對(duì)左右區(qū)間重復(fù)第二步，直到各區(qū)間只有一個(gè)數(shù)
圖示
images
代碼
def quickSort(nums):
return qSort(nums, 0, len(nums) - 1)
def qSort(nums, left, right):
if left < right:
pivot = partition(nums, left, right)
qSort(nums, left, pivot - 1)
qSort(nums, pivot + 1, right)
return nums
def partition(nums, left, right):
pivotkey = nums[left]
while left < right:
while left < right and nums[right] >= pivotkey:
right -= 1
nums[left] = nums[right]
while left < right and nums[left] <= pivotkey:
left += 1
nums[right] = nums[left]
nums[left] = pivotkey
return left
平均時(shí)間復(fù)雜度
O(nlogn)
歸并排序
思路
- 將列表拆分成兩個(gè)有序子模塊
- 遞歸拆分
- 子模塊內(nèi)部進(jìn)行排序并合并成大的模塊
- 遞歸合并
圖示
images
代碼
def mergeSort(elements):
if len(elements) <= 1: # 子序列
return elements
mid = int(len(elements) / 2)
left = mergeSort(elements[:mid]) # 遞歸的切片操作
right = mergeSort(elements[mid:len(elements)])
result = []
while len(left) > 0 and len(right) > 0:
if (left[0] <= right[0]):
result.append(left.pop(0))
else:
result.append(right.pop(0))
if (len(left) > 0):
result.extend(mergeSort(left))
else:
result.extend(mergeSort(right))
return result
平均時(shí)間復(fù)雜度
O(nlogn)
計(jì)數(shù)排序
思路
- 找出集合中最小數(shù)m和最大數(shù)n
- 建一個(gè)長(zhǎng)為(m-n+1)的列表count_list村生，所有元素初始化為0
- 遍歷集合惊暴，元素減去n得到的結(jié)果作為index，將count_list該位上的元素加1趁桃。
- 初始化空列表result辽话。
- 將count_list序列化肄鸽，用索引值減去n,得到的結(jié)果追加到result中,索引值對(duì)應(yīng)的位元素值減1，直到它為0油啤。
- 重復(fù)步驟5典徘。
圖示
images
代碼
def countSort(nums):
min_num = min(nums)
max_num = max(nums)
count_list = [0]*(max_num-min_num+1)
for i in nums:
count_list[i-min_num] += 1
result=[]
for ind,i in enumerate(count_list):
while i != 0:
result.append(ind + min_num)
i -= 1
return result
平均時(shí)間復(fù)雜度
O(n)
桶排序
前言
桶排序是將待排序集合中處于同一個(gè)值域的元素存入同一個(gè)桶中，也就是根據(jù)元素值特性將集合拆分為多個(gè)區(qū)域益咬，則拆分后形成的多個(gè)桶逮诲，從值域上看是處于有序狀態(tài)的。對(duì)每個(gè)桶中元素進(jìn)行排序幽告，則所有桶中元素構(gòu)成的集合是已排序的梅鹦。
思路
- 根據(jù)待排序集合中最大元素和最小元素的差值范圍和映射規(guī)則，確定申請(qǐng)的桶個(gè)數(shù)冗锁；
- 遍歷待排序集合齐唆，將每一個(gè)元素移動(dòng)到對(duì)應(yīng)的桶中；
- 對(duì)每一個(gè)桶中元素進(jìn)行排序冻河，并移動(dòng)到已排序集合中箍邮。
圖示
images
代碼
def bucketSort(elements):
mex_element = max(elements)
bucket = [0]*(mex_element+1)
for i in elements:
bucket[i] += 1
result = []
for j in range(len(bucket)):
if bucket[j] != 0:
for count in range(bucket[j]):
result.append(j)
return result
平均時(shí)間復(fù)雜度
O(n^2)
基數(shù)排序
思路
- 首先根據(jù)個(gè)位數(shù)的數(shù)值，在走訪數(shù)值時(shí)將它們分配至編號(hào)0到9的桶中;
- 接下來將這些桶中的數(shù)值重新串接起來叨叙，成為以下的數(shù)列锭弊。接著再進(jìn)行一次分配，這次是根據(jù)十位數(shù)來分配擂错；
- 接下來將這些桶中的數(shù)值重新串接起來味滞，持續(xù)進(jìn)行以上的動(dòng)作直至最高位數(shù)為止。
圖示
images
代碼
def RadixSort(arr):
begin = 0
min_num = 1
max_num = max(arr)
while max_num > 10**min_num:
min_num += 1
while begin < min_num:
bucket = {}
for x in range(10):
bucket.setdefault(x, [])
for x in arr:
radix =int((x / (10**begin)) % 10)
bucket[radix].append(x)
j = 0
for k in range(10):
if len(bucket[k]) != 0:
for y in bucket[k]:
arr[j] = y
j += 1
begin += 1
return arr
平均時(shí)間復(fù)雜度
O(d*2*n)
這里的d是數(shù)值位數(shù)
