1. 插入排序
- 時(shí)間復(fù)雜度：最好是n-1屯阀，最壞是n(n-1)/2宪巨，平均為O(n^2)。
- 空間復(fù)雜度： O(1)
- 多作為快排的補(bǔ)充对竣，適用于少量的數(shù)據(jù)排序庇楞。
- 該算法是穩(wěn)定的，依賴初始排序順序柏肪。
過程：
- 以第一個(gè)數(shù)為已經(jīng)排好的隊(duì)列姐刁，將第二個(gè)數(shù)從隊(duì)列的右向左比較。
- 如果比它大烦味，那么聂使，該隊(duì)列里的元素就往右邊移動(dòng)一位壁拉，接著比較該元素左邊的元素；比它小柏靶，那么弃理，就把他存入該隊(duì)列里的元素的右邊一位。
- 形成一個(gè)新的隊(duì)列屎蜓，再走1痘昌，2。
更多
# 插入排序
def insert(nums):
for i in range(1, len(nums)):
temp = nums[i]
# 是否找到一個(gè)合適的位置插入
label = False
for j in range(i-1,-1,-1):
# 找到位置了炬转，插入
if nums[j] < temp:
nums[j+1] = temp
label = True
break
else:
# 右移一位
nums[j+1] = nums[j]
if not label:
nums[0] = temp
nums = [2,3,4,5,1,9,3,0,2,1]
insert(nums)
print(nums)
感覺上面這個(gè)方法有些復(fù)雜了辆苔，改進(jìn)了一下：
def insert(nums):
for i in range(1, len(nums)):
j = i
while j > 0:
if nums[j] < nums[j - 1]:
nums[j], nums[j - 1] = nums[j - 1], nums[j]
j -= 1
else:
break
2. 二分插入排序
- 時(shí)間復(fù)雜度：最好情況下：O(nlogn)；最壞情況下：O(n^2)
分析：最外層有n次循環(huán)扼劈；最內(nèi)側(cè)分為兩個(gè)部分驻啤，一個(gè)是二叉搜索（logn），一個(gè)是for循環(huán)（n）荐吵；所以骑冗，最好的情況是元素所在的位置就是插入位置（nlogn）；最壞情況和平均的情況就是不斷在查找先煎，即為：n(logn+n)->n^2贼涩。 - 空間復(fù)雜度維O(1)。
- 是穩(wěn)定的薯蝎， 依賴初始排序順序遥倦。
過程：
- 在插入第i個(gè)元素時(shí)，對(duì)前面的0～i-1元素進(jìn)行折半占锯，
- 先跟他們中間的那個(gè)元素比谊迄，如果小，則對(duì)前半再進(jìn)行折半烟央。
- 否則對(duì)后半進(jìn)行折半⊥嵩啵回歸2
- 直到left(左邊緣)>right(右邊緣)疑俭，再把第i個(gè)元素前1位與目標(biāo)位置之間的所有元素后移。
- 最后婿失，把第i個(gè)元素放在目標(biāo)位置上钞艇。
def insert_2_sort(nums):
for i in range(1, len(nums)):
left = 0
right = i - 1
key = nums[i]
while left <= right:
middle = (left+right)//2
if key > nums[middle]:
left = middle + 1
else:
right = middle - 1
for j in range(i, left, -1):
nums[j] = nums[j-1]
nums[left] = key
a = [2,3,4,5,1,9,7,6,2,0,6]
insert_2_sort(a)
3. 希爾排序
- 空間復(fù)雜度為O(1)
- 時(shí)間復(fù)雜度則由增量（步長(zhǎng)）而定。
只要最終步長(zhǎng)為1任何步長(zhǎng)序列都可以工作豪硅。
一個(gè)好的步長(zhǎng)序列評(píng)價(jià)時(shí)間復(fù)雜度可以達(dá)到O(n^1.5) - shell排序是非穩(wěn)定排序
- 提高效率的思想：
因?yàn)椴迦肱判虻臅r(shí)間復(fù)雜度依賴初始序列的順序哩照，所以通過大步長(zhǎng)的排序（時(shí)間復(fù)雜度低），使序列部分有序懒浮，這樣當(dāng)進(jìn)行小步長(zhǎng)排序時(shí)飘弧，時(shí)間復(fù)雜度也低识藤。
過程
- 把記錄按下標(biāo)的一定增量分組
- 對(duì)每組使用直接插入排序算法排序。
- 減小增量n次伶，若n > 0,進(jìn)入1痴昧；反之，算法終止
def shell(nums):
gaps = 3
for gap in range(1, gaps+1):
for i in range(gap, len(nums)):
key = nums[i]
pointer = i - gap
while key < nums[pointer] and pointer >= 0:
nums[pointer+gap] = nums[pointer]
pointer -= gap
nums[pointer+gap] = key
4. 選擇排序
- 空間復(fù)雜度為O(1)
- 時(shí)間復(fù)雜度為O(n^2)
- 對(duì)比冒泡排序冠王，它少了很多的交換步驟赶撰。
- 不穩(wěn)定的排序方式
過程：
- 從待排序的數(shù)據(jù)元素中選出最小（或最大）的一個(gè)元素柱彻。
- 存放在序列的起始位置豪娜，直到全部待排序的數(shù)據(jù)元素排完。
類似冒泡排序哟楷。
def selection_sort(nums):
for i in range(0, len(nums)):
lowest = i
for j in range(i, len(nums)):
if nums[j] < nums[lowest]:
lowest = j
nums[lowest], nums[i] = nums[i], nums[lowest]
5. 冒泡排序
- 時(shí)間復(fù)雜度為O(n^2)
- 空間復(fù)雜度為O(1)
- 穩(wěn)定的排序方法
- 優(yōu)化：
如果一個(gè)forloop沒有發(fā)生一次交換瘤载，說明已經(jīng)排好了，可以停止了后面的循環(huán)了吓蘑。
在一次loop中記錄最后一次交換的位置惕虑，那么該位置后面數(shù)一定都是排好了的。所以這一部分就不用參與下面的比較了磨镶。
過程：
- 比較相鄰的元素溃蔫。如果第一個(gè)比第二個(gè)大，就交換他們兩個(gè)琳猫。
- 對(duì)每一對(duì)相鄰元素作同樣的工作伟叛，從開始第一對(duì)到結(jié)尾的最后一對(duì)。在這一點(diǎn)脐嫂，最后的元素應(yīng)該會(huì)是最大的數(shù)统刮。
- 針對(duì)所有的元素重復(fù)以上的步驟，除了最后一個(gè)账千。
- 持續(xù)每次對(duì)越來越少的元素重復(fù)上面的步驟侥蒙，直到?jīng)]有任何一對(duì)數(shù)字需要比較
------百度百科
def bubble_sort(nums):
for i in range(1, len(nums)):
for j in range(0, len(nums)-i):
if nums[j+1] < nums[j]:
nums[j+1], nums[j] = nums[j], nums[j+1]
a = [9,3,2,7,1,8,0,4,10,6]
bubble_sort(a)
print(a)
6. 雞尾酒排序/雙向冒泡排序
- 空間復(fù)雜度為：O(1)
- 平均和最差的時(shí)間復(fù)雜度為O(n^2)，但如果序列在一開始已經(jīng)大部分排序過的話匀奏，趨近于O(n)鞭衩。
原因：雙向排序可以避免大量小的數(shù)在最右邊而小數(shù)移動(dòng)緩慢的情況（升序）
過程：
- 傳統(tǒng)冒泡氣泡排序的雙向進(jìn)行，先讓氣泡排序由左向右進(jìn)行
- 再來讓氣泡排序由右往左進(jìn)行娃善，如此完成一次排序的動(dòng)作
- 使用left與right兩個(gè)旗標(biāo)來記錄左右兩端已排序的元素位置：
當(dāng)left = right時(shí)：結(jié)束
否則：繼續(xù)1
def bubble_sort(nums):
left = 1
right = len(nums)
while left < right:
for i in range(0, len(nums)-left):
if nums[i+1] < nums[i]:
nums[i+1], nums[i] = nums[i], nums[i+1]
left += 1
for j in range(len(nums)-1, len(nums)-right, -1):
if nums[j] < nums[j-1]:
nums[j], nums[j-1] = nums[j-1], nums[j]
right -= 1
