簡單來說辅柴，時間復雜度指的是語句執(zhí)行次數(shù)倒戏，空間復雜度指的是算法所占的存儲空間
時間復雜度
計算時間復雜度的方法：
- 用常數(shù)1代替運行時間中的所有加法常數(shù)
- 修改后的運行次數(shù)函數(shù)中怠噪，只保留最高階項
- 去除最高階項的系數(shù)
即O(4n^2+2n)只保留O(n^2)
那么nlog(n)是什么情況呢, 看下面這個例子:
for（int i=1;i<=n;i++）
{
for(int j=1;j<=n;j+=i)
{
..... //復雜度為O(1);
}
}
求該程序段的時間復雜度。
可以看出: (1) 當i=1時峭梳，需要執(zhí)行n次舰绘；
(2) 當i=2時，需要執(zhí)行n/2次葱椭；
(3) 當i=3時捂寿，需要執(zhí)行n/3次；
.............
(4) 當i=n-1時孵运，需要執(zhí)行n/n-1次秦陋；
(5) 當i=n時，需要執(zhí)行n/n次治笨；
每次的時間復雜度為O（1）驳概，則總共的時間復雜度為n(1 +1/2+1/3 +1/4 + 1/5+ 1/6+1/7+1/8 +...1/n), 經(jīng)過歐拉證明, 得到:
1+1/2+1/3+1/4+...+1/n= ln(n+1)+r(r為常量)
則總共的時間復雜度為：
n(1 +1/2+1/3 +1/4 + 1/5+ 1/6+1/7+1/8 +...1/n)
=n(ln(n+1) + r)
=nln(n+1)+r*n
即復雜度為nlog(n)
同理, 一個數(shù)的二分查找的時間復雜度是O(log2(N))
那么O(n2)是什么情況呢, 看下面這個例子:
(1) 當i=1時，需要執(zhí)行n次旷赖；
(2) 當i=2時顺又，需要執(zhí)行2次；
(3) 當i=3時等孵，需要執(zhí)行3次稚照；
.............
(4) 當i=n-1時，需要執(zhí)行n-1次俯萌；
(5) 當i=n時果录，需要執(zhí)行n次；
那么總的次數(shù)就是
1+2+3+…+n-2+n-1+n
根據(jù)等差數(shù)列求和得到 N2/2+N+1 , 省略低階項省略系數(shù)后即可得 O(N2)
根據(jù)排序過程中元素是否完全保存在內(nèi)存中咐熙，可以將算法分為 內(nèi)部排序（internal sort） 和 外部排序（external sort）弱恒。
下圖是各個排序算法的復雜度:
1. 冒泡排序
冒泡排序算法的基本思想為：假如待排序線性表的長度為 nn，從前往后兩兩比較相鄰元素的關(guān)鍵字棋恼，若 a_{i-1}>a_iai?1?>ai?返弹，則交換它們锈玉，直到線性表比較完成。每趟交換以后最后一個元素一定是最大的琉苇，不再參與下一趟交換已烤。也就是對于第 ii 趟交換凤壁，只需要比較到 a_{n-i}an?i? 即可淋纲。直到一趟比較內(nèi)沒有進行交換痛侍，算法結(jié)束固灵。時間復雜度和插入排序一樣炕桨，也為 偶惠。
冒泡排序算法的運作如下：
- 比較相鄰的元素煤蹭，如果前一個比后一個大昼汗，就把它們兩個調(diào)換位置肴熏。
- 對每一對相鄰元素作同樣的工作，從開始第一對到結(jié)尾的最后一對顷窒⊥芾簦看下面動圖, 最大的元素會被一次一次往后移動, 這步做完后，最后的元素會是最大的數(shù)鞋吉。
- 針對所有的元素重復以上的步驟鸦做，除了最后一個。
- 持續(xù)每次對越來越少的元素重復上面的步驟谓着，直到?jīng)]有任何一對數(shù)字需要比較泼诱。
#這個冒泡排序法實現(xiàn)的很凝練, 用了倒數(shù)的range的方式, 并且用len(chaos_list)-1避免了之后判斷chaos_list[i+1]是否超出范圍的麻煩
def bubble_sort(chaos_list):
for cur_len in range(len(chaos_list)-1,0,-1):
for i in range(cur_len):
if chaos_list[i]>chaos_list[i+1]:
chaos_list[i],chaos_list[i+1]=chaos_list[i+1],chaos_list[i]
return chaos_list
//這個是正序版的
void sort() {
for(int i=0;i<length-1;i++){
bool swapped=false;
for(int j=0;j<length-i-1;j++){
if(data[j]>data[j+1]){
swap(data[j],data[j+1]);
swapped=true;
}
}
if(swapped==false){//過程中一次都沒交換說明之前的每個數(shù)字的順序都是對的
break;
}
}
}
//這是帶模板倒序版的, 接收兩個迭代器, 一個是begin一個是end
template<typename T>
void BubbleSort(T first, T last)
{
/* 如果在迭代器的范圍里面沒有至少兩個數(shù)字的話，那可以直接返回赊锚，不需要排序 */
if (first == last || next(first) == last) return;
for(auto i=first;i!=prev(last);i++){
for(auto j=prev(last);j!=i;j--){
auto k=prev(j);
if(*j<*k){
auto t=*j;
*j=*k;
*k=t;
}
}
}
}
//這個是倒序版的
void bubble_sort() {
for(int i=length-1;i>0;i--){//此處選擇i>0, 當i=0時沒有排序的意義了
bool swapped=false;
for(int j=0;j<i;j++){
if(data[j]>data[j+1]){
swap(data[j],data[j+1]);
swapped=true;
}
}
if(!swapped){
break;
}
}
}
2. 雞尾酒排序
雞尾酒排序治筒，也叫定向冒泡排序，是冒泡排序的一種改進舷蒲。此算法與冒泡排序的不同處在于從低到高然后從高到低耸袜，而冒泡排序則僅從低到高去比較序列里的每個元素。他可以得到比冒泡排序稍微好一點的效能牲平。
3. 選擇排序
選擇排序的思想是堤框，每趟從線性表的待排序區(qū)域選取關(guān)鍵字最小的元素，將其放到已排序區(qū)域的最后欠拾。因為每趟可以讓待排序區(qū)域的元素數(shù)量減少一個胰锌，所以總共需要 n-1n?1 趟操作就可以將整個線性表排序完成。很顯然藐窄，選擇排序的時間復雜度也是 资昧。
在每次查找關(guān)鍵字最小的元素時，可以使用堆對效率進行優(yōu)化荆忍，使用堆來優(yōu)化的選擇排序就是堆排序格带。由于一共要查找 nn 次最小值撤缴，每次查找的時間為O(logn)，所以堆排序的時間復雜度為 O(nlogn)叽唱。
選擇排序也是一種簡單直觀的排序算法屈呕。它的工作原理很容易理解：初始時在序列中找到最小（大）元素棺亭，放到序列的起始位置作為已排序序列虎眨；然后，再從剩余未排序元素中繼續(xù)尋找最邢庹（大）元素嗽桩，放到已排序序列的末尾。以此類推凄敢，直到所有元素均排序完畢碌冶。
注意選擇排序與冒泡排序的區(qū)別：冒泡排序通過依次交換相鄰兩個順序不合法的元素位置，從而將當前最欣苑臁（大）元素放到合適的位置扑庞；而選擇排序每遍歷一次都記住了當前最小（大）元素的位置拒逮，最后僅需一次交換操作即可將其放到合適的位置罐氨。
選擇排序是不穩(wěn)定的排序算法，不穩(wěn)定發(fā)生在最小元素與A[i]交換的時刻消恍。
比如序列：{ 5, 8, 5, 2, 9 }岂昭，一次選擇的最小元素是2，然后把2和第一個5進行交換狠怨，從而改變了兩個元素5的相對次序约啊。
其中穩(wěn)定性指的是: 假定在待排序的記錄序列中，存在多個具有相同的關(guān)鍵字的記錄佣赖，若經(jīng)過排序恰矩，這些記錄的相對次序保持不變，即在原序列中憎蛤，r[i]=r[j]外傅，且r[i]在r[j]之前，而在排序后的序列中俩檬，r[i]仍在r[j]之前萎胰，則稱這種排序算法是穩(wěn)定的；否則稱為不穩(wěn)定的棚辽。
穩(wěn)定性的意義:
1技竟、如果只是簡單的進行數(shù)字的排序，那么穩(wěn)定性將毫無意義屈藐。
2榔组、如果排序的內(nèi)容僅僅是一個復雜對象的某一個數(shù)字屬性熙尉，那么穩(wěn)定性依舊將毫無意義（所謂的交換操作的開銷已經(jīng)算在算法的開銷內(nèi)了，如果嫌棄這種開銷搓扯，不如換算法好了检痰？）
3、如果要排序的內(nèi)容是一個復雜對象的多個數(shù)字屬性锨推，但是其原本的初始順序毫無意義铅歼，那么穩(wěn)定性依舊將毫無意義。
4爱态、除非要排序的內(nèi)容是一個復雜對象的多個數(shù)字屬性谭贪，且其原本的初始順序存在意義，那么我們需要在二次排序的基礎(chǔ)上保持原有排序的意義锦担，才需要使用到穩(wěn)定性的算法，例如要排序的內(nèi)容是一組原本按照價格高低排序的對象慨削，如今需要按照銷量高低排序洞渔，使用穩(wěn)定性算法，可以使得想同銷量的對象依舊保持著價格高低的排序展現(xiàn)缚态，只有銷量不同的才會重新排序磁椒。（當然，如果需求不需要保持初始的排序意義玫芦，那么使用穩(wěn)定性算法依舊將毫無意義）浆熔。
void sort() {
int temp;
for(int i=0;i<length-1;i++){
temp=i;
for(int j=i+1;j<length;j++){ //此處選擇i+1就可以了, 因為一開始將temp初始化為i, 所以其實i已經(jīng)比過了
if(data[temp]>data[j]){
temp=j;
}
}
if(temp!=i){
swap(data[i],data[temp]);
}
}
}
def choice_sort(chaos_list):
length=len(chaos_list)
for i in range(length):
cur_min_ind,cur_min_value=i,chaos_list[i]
for j in range(i,length):
if chaos_list[j]<cur_min_value:
cur_min_ind,cur_min_value=j,chaos_list[j]
chaos_list[i],chaos_list[cur_min_ind]=chaos_list[cur_min_ind],chaos_list[i]
return chaos_list
#另一種寫法
def choice(chaos_list):
for i in range(len(chaos_list)):
index=min(range(i,len(chaos_list)),key=lambda x:chaos_list[x])
chaos_list[index],chaos_list[i]=chaos_list[i],chaos_list[index]
return chaos_list
4. 插入排序
插入排序每次插入的時間復雜度為 O(n)，一共執(zhí)行 n-1次桥帆，因此總體時間復雜度為医增。在插入時查找插入位置的過程可以使用折半查找算法將查找位置的復雜度優(yōu)化到
，但因為還需要
的時間復雜度來在順序表上執(zhí)行移動操作老虫，所以總體時間復雜度依然是
叶骨。
對于未排序數(shù)據(jù)，在已排序序列(左手已經(jīng)排好序的手牌)中從后向前掃描祈匙，找到相應位置并插入忽刽。
插入排序在實現(xiàn)上，通常采用in-place排序（即只需用到O(1)的額外空間的排序）夺欲，因而在從后向前掃描過程中跪帝，需要反復把已排序元素逐步向后挪位，為最新元素提供插入空間些阅。
具體算法描述如下：
- 從第一個元素開始伞剑，該元素可以認為已經(jīng)被排序
- 取出下一個元素，在已經(jīng)排序的元素序列中從后向前掃描
- 如果該元素（已排序）大于新元素扑眉，將該元素移到下一位置
- 重復步驟3纸泄，直到找到已排序的元素小于或者等于新元素的位置
- 將新元素插入到該位置后
- 重復步驟2~5
對序列{ 6, 5, 3, 1, 8, 7, 2, 4 }進行插入排序的實現(xiàn)過程如下:
插入排序不適合對于數(shù)據(jù)量比較大的排序應用赖钞。但是，如果需要排序的數(shù)據(jù)量很小聘裁，比如量級小于千雪营，那么插入排序還是一個不錯的選擇。 插入排序在工業(yè)級庫中也有著廣泛的應用衡便，在STL的sort算法和stdlib的qsort算法中献起，都將插入排序作為快速排序的補充，用于少量元素的排序（通常為8個或以下）镣陕。
對于插入排序谴餐，如果比較操作的代價比交換操作大的話，可以采用二分查找法來減少比較操作的次數(shù)呆抑，我們稱為二分插入排序岂嗓。
當n較大時，二分插入排序的比較次數(shù)比直接插入排序的最差情況好得多鹊碍，但比直接插入排序的最好情況要差厌殉，所當以元素初始序列已經(jīng)接近升序時，直接插入排序比二分插入排序比較次數(shù)少侈咕。二分插入排序元素移動次數(shù)與直接插入排序相同公罕，依賴于元素初始序列。
void sort(int data[],int length){
for(int i=0;i<length;i++){
for(int j=i-1;j>=0;j--){
if(data[j]>data[j+1]){
swap(data[j],data[j+1]);
}
else{
break;
}
}
}
}
#這是最優(yōu)的插入排序!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
def insert_sort(chaos_list):
for i in range(1,len(chaos_list)):
j=i
temp=chaos_list[i]
while j-1>=0 and temp<chaos_list[j-1]:
chaos_list[j]=chaos_list[j-1]
j-=1
chaos_list[j]=temp
return chaos_list
#這里實現(xiàn)的是穩(wěn)定的, 如果把第七行改為小于等于就是不穩(wěn)定的
#這種插入排序效率太低, 因為如果往list中間插入元素的話, 插入位置的后續(xù)元素都需要挪動, 所以不好
def insert_sort(chaos_list):
sorted_list=[chaos_list.pop(0)]
for c in chaos_list:
flag=True
for ind,s in enumerate(sorted_list):
if c<s:
sorted_list.insert(ind,c)
flag=False
break
if flag:
sorted_list.append(c)
return sorted_list
#或者完全按照圖中的順序
def insert_sort(chaos_list):
sorted_list=[chaos_list.pop(0)]
for c in chaos_list:
ind=len(sorted_list)-1
while ind>=0 and c<sorted_list[ind]:
ind-=1
if ind==len(sorted_list)-1:
sorted_list.append(c)
else:
sorted_list.insert(ind+1,c)
return sorted_list
5. 希爾排序
希爾排序耀销，也叫遞減增量排序楼眷，是插入排序的一種更高效的改進版本。希爾排序是不穩(wěn)定的排序算法熊尉。
希爾排序是基于插入排序的以下兩點性質(zhì)而提出改進方法的：
- 插入排序在對幾乎已經(jīng)排好序的數(shù)據(jù)操作時罐柳，效率高，即可以達到線性排序的效率
- 但插入排序一般來說是低效的帽揪，因為插入排序每次只能將數(shù)據(jù)移動一位
希爾排序通過將比較的全部元素分為幾個區(qū)域來提升插入排序的性能硝清。這樣可以讓一個元素可以一次性地朝最終位置前進一大步。然后算法再取越來越小的步長進行排序转晰，算法的最后一步就是普通的插入排序芦拿，但是到了這步，需排序的數(shù)據(jù)幾乎是已排好的了（此時插入排序較快）查邢。
假設(shè)有一個很小的數(shù)據(jù)在一個已按升序排好序的數(shù)組的末端蔗崎。如果用復雜度為O(n^2)的排序（冒泡排序或直接插入排序），可能會進行n次的比較和交換才能將該數(shù)據(jù)移至正確位置扰藕。而希爾排序會用較大的步長移動數(shù)據(jù)缓苛，所以小數(shù)據(jù)只需進行少數(shù)比較和交換即可到正確位置。
我們來看下希爾排序的基本步驟，在此我們選擇增量gap=length/2未桥，縮小增量繼續(xù)以gap = gap/2的方式笔刹，這種增量選擇我們可以用一個序列來表示，{n/2,(n/2)/2...1}冬耿，稱為增量序列舌菜。希爾排序的增量序列的選擇與證明是個數(shù)學難題，我們選擇的這個增量序列是比較常用的亦镶，也是希爾建議的增量日月，稱為希爾增量，但其實這個增量序列不是最優(yōu)的缤骨。此處我們做示例使用希爾增量爱咬。
def shell_sort(chaos_list):
n = len(chaos_list)
gap = n/2
while gap > 0:
for i in range(gap,n):
temp = chaos_list[i]
j = i
print(temp)
#當gap=n/2時, 此時就相當于每次for循環(huán)往后挪一位就比較兩個數(shù)chaos_list[j-gap]和chaos_list[j]的大小
#當gap=n/4時, 因為前面的都排好序了, 所以將后面的調(diào)換位置就行, 具體請看print出來的結(jié)果
#原版此處是while而不是if, 不過看起來while跟if功能差不多, while每次也只循環(huán)一次
while j >= gap and chaos_list[j-gap] >temp:
#當gap=n/2時, 這一步只是將較大的那個值復制給了后邊, 并沒有交換兩個值, 較小的那個值在后面會被復制到前面
#當gap小于n/2時, 這個while是逐個向前替換, chaos_list[i]經(jīng)過最初的替換后之后就不變了， 之后變得都是其前面的元素
#前面的元素一個接一個被不斷的替換, 最后到了一個chaos[j-list]<temp的位置后把temp的值換上去
#此處用的算法完全就是選擇排序那一部分的那個動圖, 是從后往前的順序
#假設(shè)現(xiàn)在當前序列為2413, 那么首先在對4排序, i-gap得到2, 4比2大所以不換位置, 接著對1排序, i-gap是4, 那么序列變?yōu)?143, 再i-gap得到2, 那么序列變?yōu)?243, 依次類推, 在這種情況下, 如果用if, 序列變?yōu)?143的時候就不會接著往下變了
#此處就相當于插入排序
chaos_list[j] = chaos_list[j-gap]
j -= gap
# 當gap=n/2時, 較小的那個值被放在了前面
chaos_list[j] = temp
print(chaos_list)
print('########')
gap /= 2
return chaos_list
#注意第13行的while不能改成if, 否則對[ 12, 34, 54, 2, 3,-5,192,0,0,0,-0,13] 的排序結(jié)果就是:
>>> 0 -5 0 0 0 2 3 12 13 34 54 192
6. 堆排序
堆排序是指利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計的一種選擇排序算法绊起。堆是一種近似完全二叉樹的結(jié)構(gòu)（通常堆是通過一維數(shù)組來實現(xiàn)的）精拟，并滿足性質(zhì)：以最大堆(也叫大根堆、大頂堆) 為例勒庄，其中父結(jié)點的值總是大于它的孩子節(jié)點串前。
我們可以很容易的定義堆排序的過程：
- 由輸入的無序數(shù)組構(gòu)造一個最大堆，作為初始的無序區(qū)
- 把堆頂元素（最大值）和堆尾元素互換
- 把堆（無序區(qū)）的尺寸縮小1实蔽，并調(diào)用heapify(A, 0)從新的堆頂元素開始進行堆調(diào)整
- 重復步驟2，直到堆的尺寸為1
堆排序是不穩(wěn)定的排序算法谨读，不穩(wěn)定發(fā)生在堆頂元素與A[i]交換的時刻局装。
比如序列：{ 9, 5, 7, 5 }，堆頂元素是9劳殖，堆排序下一步將9和第二個5進行交換铐尚，得到序列 { 5, 5, 7, 9 }，再進行堆調(diào)整得到{ 7, 5, 5, 9 }哆姻，重復之前的操作最后得到{ 5, 5, 7, 9 }從而改變了兩個5的相對次序宣增。
下圖為怎么把一個無序的數(shù)組構(gòu)造成一個大堆頂結(jié)構(gòu)的數(shù)組的過程，注意其是從下到上矛缨，從右到左爹脾，從右邊第一個非葉子節(jié)點開始構(gòu)建的。(即將列表按順序畫出一棵樹狀圖)
其中堆的每次創(chuàng)建重構(gòu)花費箕昭，需要創(chuàng)建n次, 最差灵妨、最優(yōu)平均時間復雜度都為
步驟一 構(gòu)造初始堆。將給定無序序列構(gòu)造成一個大頂堆（一般升序采用大頂堆落竹，降序采用小頂堆)泌霍。
a.假設(shè)給定無序序列結(jié)構(gòu)如下
2.此時我們從最后一個非葉子結(jié)點開始（葉結(jié)點自然不用調(diào)整，第一個非葉子結(jié)點 arr.length/2-1=5/2-1=1述召，也就是下面的6結(jié)點）朱转，從左至右蟹地，從下至上進行調(diào)整。
4.找到第二個非葉節(jié)點4藤为，由于[4,9,8]中9元素最大怪与，4和9交換。
這時凉蜂，交換導致了子根[4,5,6]結(jié)構(gòu)混亂琼梆，繼續(xù)調(diào)整，[4,5,6]中6最大窿吩，交換4和6茎杂。
此時，我們就將一個無需序列構(gòu)造成了一個大頂堆纫雁。
步驟二 將堆頂元素與末尾元素進行交換煌往，使末尾元素最大。然后繼續(xù)調(diào)整堆轧邪，再將堆頂元素與末尾元素交換刽脖，得到第二大元素。如此反復進行交換忌愚、重建曲管、交換。
a.將堆頂元素9和末尾元素4進行交換
b.重新調(diào)整結(jié)構(gòu)硕糊，使其繼續(xù)滿足堆定義
c.再將堆頂元素8與末尾元素5進行交換院水，得到第二大元素8.
后續(xù)過程，繼續(xù)進行調(diào)整简十，交換檬某，如此反復進行，最終使得整個序列有序
def heap_sort(chaos_list):
#heapify是對一個小的二叉樹, 即包含一個父節(jié)點和一個或兩個子節(jié)點的樹, 對其構(gòu)造大頂堆模型
#后來一次階一次調(diào)用這個heapify函數(shù)來對一個一個小的二叉樹進行構(gòu)建
#注意每個節(jié)點的值都是chaos_list中的下標, 而不是具體需要排序的數(shù)
#注意這個n很重要
def heapify(chaos_list, n, i):
largest = i # Initialize largest as root
l = 2 * i + 1 # left = 2*i + 1
r = 2 * i + 2 # right = 2*i + 2
#找出兩個子節(jié)點中的最大值
if l < n and chaos_list[i] < chaos_list[l]:
largest = l
if r < n and chaos_list[largest] < chaos_list[r]:
largest = r
#如果找出的最大值不是當前父節(jié)點所對應的值, 那么將父節(jié)點和最大值所對應的下標交換
if largest != i:
chaos_list[i],chaos_list[largest] = chaos_list[largest],chaos_list[i] # swap
#遞歸調(diào)用一次是確保置換后, 子樹的子樹能滿足大頂堆的要求, 所以又把當前子樹作為父節(jié)點, 重新調(diào)用heapify, 確保子樹的子樹經(jīng)過置換后依然滿足要求
#這么一層一層迭代下去, 每置換一次就往下迭代一次
heapify(chaos_list, n, largest)
#下面是主函數(shù), 負責調(diào)用heapify的
n = len(chaos_list)
#首先將整個chaos_list中的一個一個子二叉樹輸入到heapify中, range選擇從后往前是確保從樹的底部開始構(gòu)造
#這樣最終的結(jié)果才是滿足大頂堆的要求
#其中i可以從n取起而不會報list out of range的錯是因為在heapify中當i=n時, 無論l和r都是不滿足小于n的條件的, 所以根本不會調(diào)用chaos_list[i]
#當然此處的n改為n-1也完全沒關(guān)系
for i in range(n, -1, -1):
heapify(chaos_list, n, i)
#此時從底部開始,將序列的最大值放到最后, 即chaos_list[i]的位置, 隨著i--, 最大值一個接一個被拍到了最后
for i in range(n-1, 0, -1):
#由于是大頂堆, 所以每次交換并經(jīng)過heapify后chaos_list[0]都是在0到i這個范圍內(nèi)的序列中的最大的數(shù)
#如動圖一樣, 將最大的這個數(shù)放到最后
chaos_list[i], chaos_list[0] = chaos_list[0], chaos_list[i] # swap
print(chaos_list)
#將其調(diào)整為大頂堆模式, 確保chaos_list[0]是[0,i]范圍的序列中的最大值
#注意此處一定要將大頂堆限制在[0,i]的范圍內(nèi), 不然剛抽取出來的最大值又被放到大頂堆的起始了!!!!!!!
heapify(chaos_list, i, 0)
print(chaos_list)
print('#####################')
return chaos_list
7. 歸并排序
對于歸并排序螟蝙，若當前要排序的區(qū)間為 ?恢恼，則首先讓
?? 和
這兩個區(qū)間內(nèi)的元素有序，再將這兩個區(qū)間合并成一個更大的有序區(qū)間胰默，直到整個線性表都被排序完成场斑。
歸并排序一共需要進行 層歸并操作，每層歸并操作的總時間復雜度為
初坠，因此總體的時間復雜度為
和簸。和其他排序有所不同，為了實現(xiàn)歸并操作碟刺，每次合并都需要開辟額外的空間來臨時保存合并后的排序結(jié)果锁保，總共需要開辟 nn 個元素的空間，所以歸并排序的空間復雜度為
。
歸并排序是創(chuàng)建在歸并操作上的一種有效的排序算法爽柒，效率為吴菠，1945年由馮·諾伊曼首次提出。
歸并排序的實現(xiàn)分為遞歸實現(xiàn)與非遞歸(迭代)實現(xiàn)浩村。遞歸實現(xiàn)的歸并排序是算法設(shè)計中分治策略的典型應用做葵，我們將一個大問題分割成小問題分別解決，然后用所有小問題的答案來解決整個大問題心墅。非遞歸(迭代)實現(xiàn)的歸并排序首先進行是兩兩歸并酿矢，然后四四歸并，然后是八八歸并怎燥，一直下去直到歸并了整個數(shù)組瘫筐。
歸并排序算法主要依賴歸并(Merge)操作。歸并操作指的是將兩個已經(jīng)排序的序列合并成一個序列的操作铐姚，歸并操作步驟如下：
- 申請空間策肝，使其大小為兩個已經(jīng)排序序列之和，該空間用來存放合并后的序列
- 設(shè)定兩個指針隐绵，最初位置分別為兩個已經(jīng)排序序列的起始位置
- 比較兩個指針所指向的元素之众，選擇相對小的元素放入到合并空間，并移動指針到下一位置
- 重復步驟3直到某一指針到達序列尾
- 將另一序列剩下的所有元素直接復制到合并序列尾
對序列{ 6, 5, 3, 1, 8, 7, 2, 4 }進行歸并排序的實例如下
#include <iostream>
#include <cstring>
using std::cin;
using std::cout;
using std::endl;
class Vector {
private:
int size, length;
int *data, *temp;
void merge_sort(int l,int r){
if(l==r){
return;
}
int mid=(l+r)/2;
merge_sort(l,mid);
merge_sort(mid+1,r);
//經(jīng)過上面兩個merge后默認區(qū)間[l,mid]和[mid,r]內(nèi)部元素的順序都已經(jīng)整理好了
int x=l,y=mid+1,loc=l;
while(x<=mid||y<=r){ //此處解決的是two pointer問題
if(x<=mid&&(y>r||data[x]<=data[y])){//當y>r的時候, 就不用判斷后面的data[x]<=data[y]了, (y>r||data[x]<=data[y])這部分直接輸出true, 這樣防止了溢出的可能, 即不會嘗試訪問data[y],而當y>時直接令temp[loc]=data[x];
temp[loc]=data[x];
x++;
}
else{//因為while循環(huán)判斷的是x和y中間有一個在界內(nèi), 所以當x>mid時肯定y<=r, 或者就是x<=mid, 但是data[x]>data[y];所以無論哪種情況此處都應該是temp[loc]=data[y];
temp[loc]=data[y];
y++;
}
loc++;
}
for(int i=l;i<=r;i++){
data[i]=temp[i];
}
}
public:
Vector(int input_size) {
size = input_size;
length = 0;
data = new int[size];
temp = new int[size];
}
~Vector() {
delete[] data;
delete[] temp;
}
bool insert(int loc, int value) {
if (loc < 0 || loc > length) {
return false;
}
if (length >= size) {
return false;
}
for (int i = length; i > loc; --i) {
data[i] = data[i - 1];
}
data[loc] = value;
length++;
return true;
}
void print() {
for (int i = 0; i < length; ++i) {
if (i > 0) {
cout << " ";
}
cout << data[i];
}
cout << endl;
}
void sort() {
merge_sort(0,length-1);
}
};
int main() {
int n;
cin >> n;
Vector arr(n);
for (int i = 0; i < n; ++i) {
int x;
cin >> x;
arr.insert(i, x);
}
arr.sort();
arr.print();
return 0;
}
#首先定義將兩個序列聚合成一個的函數(shù)
def merge(chaos_list, l, m, r):
n1 = m - l + 1
n2 = r- m
#此處是m+1的原因是recursion_helper中m是等于(l+(r-1))/2, 其中r減去了1
#注意, 此處的切片賦值不是將列表的ref賦值過去, 而是將列表中的元素賦值過去
L=chaos_list[l:m+1]
#此處的是r+1是因為從最初調(diào)用的時候就用的len(chaos_list)-1
R=chaos_list[m+1:r+1]
i = 0
j = 0
#因為i和j相當于兩個移動的pointer, 此時需要另外一個index指向安放兩個array中當前最大值的位置
k = l
#因為兩個需要合并的array內(nèi)部都是升序, 所以只需要比較兩個array中第一個元素的大小, 小的那個放到k所在的位置
#正常來說應該把兩個array中第一個元素較小的那個pop出來, 下一次接著比較兩個arrya中第一個元素的大小即可
#但此處沒有pop, 而是用的two pointer方法, 往后移一位, 將pointer所指的位置當做新的第一個元素
while i < n1 and j < n2 :
if L[i] <= R[j]:
#因為L和R用的是切片賦值, 所以改變chaos_list中元素的值不會影響到L和R中的值
chaos_list[k] = L[i]
i += 1
else:
chaos_list[k] = R[j]
j += 1
k += 1
#當一個array已經(jīng)用完了, 另外一個array剩下的值全部都拼接到輸出結(jié)果的末尾
while i < n1:
chaos_list[k] = L[i]
i += 1
k += 1
while j < n2:
chaos_list[k] = R[j]
j += 1
k += 1
def merge_sort(chaos_list):
def recursion_helper(l,r):
if l < r:
# Same as (l+r)/2, but avoids overflow for large l and h
#將待排序的列表一分為二, 得到中間點
m = (l+(r-1))/2
#將一分為二的列表前后兩半分別再次各自一分為二
recursion_helper( l, m)
recursion_helper( m+1, r)
merge(chaos_list, l, m, r)
recursion_helper(0,len(chaos_list)-1)
return chaos_list
8. 快速排序
快速排序是目前應用最廣泛的排序算法之一依许。它的基本思想是棺禾，每次從待排序區(qū)間選取一個元素（我們在后面的課程中都是選取第一個）作為基準記錄，所有比基準記錄小的元素都在基準記錄的左邊峭跳，而所有比基準記錄大的元素都在基準記錄的右邊帘睦。之后分別對基準記錄的左邊和右邊兩個區(qū)間進行快速排序，直至將整個線性表排序完成坦康。
快速排序的時間復雜度不是穩(wěn)定的，可以證明快速排序的平均時間復雜度為诡延，最壞情況為
滞欠，可以通過隨機選擇基準記錄來盡可能避免最壞情況的出現(xiàn)。
有沒有既不浪費空間又可以快一點的排序算法呢肆良？那就是“快速排序”筛璧。
下面大部分內(nèi)容轉(zhuǎn)載自 https://www.cnblogs.com/ahalei/p/3568434.html
假設(shè)我們現(xiàn)在對“6 1 2 7 9 3 4 5 10 8”這個10個數(shù)進行排序。首先在這個序列中隨便找一個數(shù)作為基準數(shù)（不要被這個名詞嚇到了惹恃，就是一個用來參照的數(shù)夭谤，待會你就知道它用來做啥的了）。為了方便巫糙，就讓第一個數(shù)6作為基準數(shù)吧朗儒。接下來，需要將這個序列中所有比基準數(shù)大的數(shù)放在6的右邊，比基準數(shù)小的數(shù)放在6的左邊醉锄，類似下面這種排列：
3 1 2 5 4 6 9 7 10 8
在初始狀態(tài)下乏悄，數(shù)字6在序列的第1位。我們的目標是將6挪到序列中間的某個位置恳不，假設(shè)這個位置是k￠菪。現(xiàn)在就需要尋找這個k，并且以第k位為分界點烟勋，左邊的數(shù)都小于等于6规求，右邊的數(shù)都大于等于6。想一想卵惦，你有辦法可以做到這點嗎阻肿？
方法其實很簡單：分別從初始序列“6 1 2 7 9 3 4 5 10 8”兩端開始“探測”。先從右往左找一個小于6的數(shù)鸵荠，再從左往右找一個大于6的數(shù)冕茅，然后交換他們。這里可以用兩個變量i和j蛹找，分別指向序列最左邊和最右邊姨伤。我們?yōu)檫@兩個變量起個好聽的名字“哨兵i”和“哨兵j”。剛開始的時候讓哨兵i指向序列的最左邊（即i=1）庸疾，指向數(shù)字6乍楚。讓哨兵j指向序列的最右邊（即=10），指向數(shù)字届慈。
首先哨兵j開始出動徒溪。因為此處設(shè)置的基準數(shù)是最左邊的數(shù)，所以需要讓哨兵j先出動金顿，這一點非常重要（請自己想一想為什么）臊泌。哨兵j一步一步地向左挪動（即j--），直到找到一個小于6的數(shù)停下來揍拆。接下來哨兵i再一步一步向右挪動（即i++）渠概，直到找到一個數(shù)大于6的數(shù)停下來。最后哨兵j停在了數(shù)字5面前嫂拴，哨兵i停在了數(shù)字7面前播揪。
現(xiàn)在交換哨兵i和哨兵j所指向的元素的值。交換之后的序列如下：
6 1 2 5 9 3 4 7 10 8
到此筒狠，第一次交換結(jié)束猪狈。接下來開始哨兵j繼續(xù)向左挪動（再友情提醒，每次必須是哨兵j先出發(fā)）辩恼。他發(fā)現(xiàn)了4（比基準數(shù)6要小雇庙，滿足要求）之后停了下來谓形。哨兵i也繼續(xù)向右挪動的，他發(fā)現(xiàn)了9（比基準數(shù)6要大状共，滿足要求）之后停了下來套耕。此時再次進行交換，交換之后的序列如下：
6 1 2 5 4 3 9 7 10 8
第二次交換結(jié)束峡继，“探測”繼續(xù)冯袍。哨兵j繼續(xù)向左挪動，他發(fā)現(xiàn)了3（比基準數(shù)6要小碾牌，滿足要求）之后又停了下來康愤。哨兵i繼續(xù)向右移動，糟啦舶吗！此時哨兵i和哨兵j相遇了征冷，哨兵i和哨兵j都走到3面前。說明此時“探測”結(jié)束誓琼。我們將基準數(shù)6和3進行交換检激。交換之后的序列如下：
3 1 2 5 4 6 9 7 10 8
到此第一輪“探測”真正結(jié)束。此時以基準數(shù)6為分界點腹侣，6左邊的數(shù)都小于等于6叔收，6右邊的數(shù)都大于等于6“亮ィ回顧一下剛才的過程饺律，其實哨兵j的使命就是要找小于基準數(shù)的數(shù)，而哨兵i的使命就是要找大于基準數(shù)的數(shù)跺株，直到i和j碰頭為止复濒。
OK，解釋完畢∑故。現(xiàn)在基準數(shù)6已經(jīng)歸位巧颈，它正好處在序列的第6位。此時我們已經(jīng)將原來的序列袖扛，以6為分界點拆分成了兩個序列洛二，左邊的序列是“3 1 2 5 4”，右邊的序列是“9 7 10 8”攻锰。接下來還需要分別處理這兩個序列。因為6左邊和右邊的序列目前都還是很混亂的妓雾。不過不要緊娶吞，我們已經(jīng)掌握了方法，接下來只要模擬剛才的方法分別處理6左邊和右邊的序列即可⌒狄觯現(xiàn)在先來處理6左邊的序列現(xiàn)吧妒蛇。
左邊的序列是“3 1 2 5 4”机断。請將這個序列以3為基準數(shù)進行調(diào)整，使得3左邊的數(shù)都小于等于3绣夺，3右邊的數(shù)都大于等于3吏奸。好了開始動筆吧
如果你模擬的沒有錯，調(diào)整完畢之后的序列的順序應該是：
2 1 3 5 4
OK陶耍，現(xiàn)在3已經(jīng)歸位奋蔚。接下來需要處理3左邊的序列“2 1”和右邊的序列“5 4”。對序列“2 1”以2為基準數(shù)進行調(diào)整烈钞，處理完畢之后的序列為“1 2”泊碑，到此2已經(jīng)歸位。序列“1”只有一個數(shù)毯欣，也不需要進行任何處理馒过。至此我們對序列“2 1”已全部處理完畢，得到序列是“1 2”酗钞。序列“5 4”的處理也仿照此方法腹忽，最后得到的序列如下：
1 2 3 4 5 6 9 7 10 8
對于序列“9 7 10 8”也模擬剛才的過程，直到不可拆分出新的子序列為止砚作。最終將會得到這樣的序列窘奏，如下
1 2 3 4 5 6 7 8 9 10
到此，排序完全結(jié)束偎巢。細心的同學可能已經(jīng)發(fā)現(xiàn)厨喂，快速排序的每一輪處理其實就是將這一輪的基準數(shù)歸位，直到所有的數(shù)都歸位為止磁浇，排序就結(jié)束了钧大。
#是two_pointer的理念
def two_pointer(chaos_list,start,end):
#將第一個元素作為基準點
benchmark=start
while start!=end:
#注意此處必須是while不能是if, 因為要確保右pointer要一直往左走直到遇到了比benchmark小的
#而且此處要加上start!=end, 雖然在上面已經(jīng)判斷了一遍了, 但隨著while都走動說不定會end<start
while not chaos_list[end]<chaos_list[benchmark] and start!=end:
end-=1
while not chaos_list[start]>chaos_list[benchmark] and start!=end:
start+=1
if chaos_list[end]<chaos_list[benchmark] and chaos_list[start]>chaos_list[benchmark]:
chaos_list[start],chaos_list[end]=chaos_list[end],chaos_list[start]
#將第一個元素即作為基準的元素與兩個pointer相遇點上的元素交換
chaos_list[benchmark],chaos_list[start]=chaos_list[start],chaos_list[benchmark]
return start
def quick_sort(chaos_list):
if not chaos_list:return []
def helper(start,end):
#每次返回index的位置, 然后基于index將其分為兩半, 不把index包進去
#針對分開的兩半分別調(diào)用遞歸
index=two_pointer(chaos_list,start,end)
if index>start+1:
helper(start,index)
if index<end-1:
helper(index+1,end)
start,end=0,len(chaos_list)-1
helper(start,end)
return chaos_list
#簡易版寫法
def quick_sort(chaos_list):
length=len(chaos_list)
def helper(l,r):
ptr1,ptr2=l,r
while ptr1<ptr2:
#注意此處一定是要大于等于號, 如果是大于號的話會陷入死循環(huán), 譬如假如輸入為[5,3,1,6,7,8,2,5], 其中l(wèi)的值等于r的值,這時如果是小于號ptr2就不會移動
while ptr1<ptr2 and chaos_list[ptr2]>=chaos_list[l]:
ptr2-=1
#同理此處一定要是小于等于
while ptr1<ptr2 and chaos_list[ptr1]<=chaos_list[l]:
ptr1+=1
if chaos_list[ptr1]>chaos_list[l] and chaos_list[ptr2]<chaos_list[l]:
chaos_list[ptr1],chaos_list[ptr2]=chaos_list[ptr2],chaos_list[ptr1]
chaos_list[l],chaos_list[ptr1]=chaos_list[ptr1],chaos_list[l]
return ptr1
def recursion_helper(l,r):
index=helper(l,r)
if index>l+1:
helper(l,index)
if index<r-1:
helper(index+1,r)
recursion_helper(0,len(chaos_list)-1)
return chaos_list
除此之外, 另一種快速排序是每次跟基準線所在位置互換元素, 即:
#include <iostream>
#include <cstring>
using std::cin;
using std::cout;
using std::endl;
using std::swap;
class Vector {
private:
int size, length;
int *data;
void quick_sort(int left,int right){
if(left>right){
return;
}
int pivot=data[left],low=left,high=right;
while(low<high){
while(low<high&&data[high]>=pivot){//此處必須包含等于號, 要不不會移動
high--;
}
data[low]=data[high];//如果沒找到比pivot小的, 此時經(jīng)過上面的循環(huán)后, high=low, 所以此步無傷大雅
while(low<high&&data[low]<=pivot){
low++;
}
data[high]=data[low];
}
data[low]=pivot;//基準數(shù)應該放在左標記low對應的位置上，當然也是右標記high對應的位置上窍霞，因為此時low等于high匠题。
quick_sort(left,low-1);
quick_sort(low+1,right);
}
public:
Vector(int input_size) {
size = input_size;
length = 0;
data = new int[size];
}
~Vector() {
delete[] data;
}
bool insert(int loc, int value) {
if (loc < 0 || loc > length) {
return false;
}
if (length >= size) {
return false;
}
for (int i = length; i > loc; --i) {
data[i] = data[i - 1];
}
data[loc] = value;
length++;
return true;
}
void print() {
for (int i = 0; i < length; ++i) {
if (i > 0) {
cout << " ";
}
cout << data[i];
}
cout << endl;
}
void sort() {
quick_sort(0,length-1);
}
};
int main() {
int n;
cin >> n;
Vector arr(n);
for (int i = 0; i < n; ++i) {
int x;
cin >> x;
arr.insert(i, x);
}
arr.sort();
arr.print();
return 0;
}
此文與于一年前所寫, 文中很多文字引用的出處嘗試找卻沒找到, 若發(fā)現(xiàn)我哪部分引用了卻未注明來源, 懇請告知我即刻修改。
