冒泡排序法：就是兩兩交換到最后
重復(fù)執(zhí)行n次冒泡，也就是?O(n^2)。 空間復(fù)雜度是O(n)。
選擇排序法：
這樣的過程要執(zhí)行n次，所以時(shí)間復(fù)雜度還是O(n^2)?？臻g復(fù)雜度是O(n)
堆排序：
1、概念
堆排序就是把最大堆堆頂?shù)淖畲髷?shù)取出，將剩余的堆繼續(xù)調(diào)整為最大堆，再次將堆頂?shù)淖畲髷?shù)取出，這個(gè)過程持續(xù)到剩余數(shù)只有一個(gè)時(shí)結(jié)束。
堆排序的時(shí)間復(fù)雜度是O(nlgN)，與快速排序達(dá)到相同的時(shí)間復(fù)雜度。但是在實(shí)際應(yīng)用中，我們往往采用快速排序而不是堆排序。這是因?yàn)榭焖倥判虻囊粋€(gè)好的實(shí)現(xiàn)，往往比堆排序具有更好的表現(xiàn)。堆排序的主要用途，是在形成和處理優(yōu)先級(jí)隊(duì)列方面。另外，如果計(jì)算要求是類優(yōu)先級(jí)隊(duì)列（比如，只要返回最大或者最小元素，只有有限的插入要求等），堆同樣是很適合的數(shù)據(jù)結(jié)構(gòu)。
2、基礎(chǔ)知識(shí)
堆一般用數(shù)組表示，比如數(shù)組A數(shù)組的長度Length(A)，堆在數(shù)組中的元素個(gè)數(shù)HeapSize(A)。一般說來，HeapSize(A) <= Length(A)，因?yàn)閿?shù)組A當(dāng)中可能有一些元素不在堆中。
假設(shè)節(jié)點(diǎn)I是數(shù)組A中下標(biāo)為i的節(jié)點(diǎn)。
Parent(i) : return Floor(i/2); //I的父節(jié)點(diǎn)下標(biāo)，F(xiàn)loor(i)表示比i小的最大整數(shù)。
Left(i) : return 2*i; //I的左子節(jié)點(diǎn)
Right(i) : return 2*i+1; //I的右子節(jié)點(diǎn)
含有n個(gè)元素的堆A的高度是: Floor(lgn)。
3、在堆中定義以下幾種操作：
最大堆調(diào)整（Max-Heapify）：將堆的末端子節(jié)點(diǎn)作調(diào)整，使得子節(jié)點(diǎn)永遠(yuǎn)小于父節(jié)點(diǎn)
創(chuàng)建最大堆（Build-Max-Heap）：將堆所有數(shù)據(jù)重新排序，使其成為最大堆
堆排序（Heap-Sort）：移除位在第一個(gè)數(shù)據(jù)的根節(jié)點(diǎn)，并做最大堆調(diào)整的遞歸運(yùn)算
遞歸：參考
特點(diǎn)1?它有一個(gè)基本部分，即直接滿足條件，輸出
?特點(diǎn)2?它有一個(gè)遞歸部分，即 通過改變基數(shù)（即n），來逐步使得n滿足基本部分的條件，從而輸出
?例子1： 全排列
? ? ? ?描述： 有n個(gè)數(shù)時(shí)， 輸出n個(gè)數(shù)的所有排列組合
? ? ? ?分析： ?
假設(shè)有 abc三個(gè)數(shù)，
? ? ? ? ? 特點(diǎn)3： 整體分割為局部，從基本部分開始輸出
? ? ? ? ? ? ?那么其輸出為 abc, acb, ? ? ?bac, bca, ? ? cba, cab。?
abc, bac, cba 三種情況下，都會(huì)從整體過度到 部分， 即 abc->bc, ? bac->ac, cba->ba, 而相應(yīng)的 bc, ac, ba, ?又會(huì)有cb, ca, ab的情況．即 perm(abc)-> ?a*perm(bc)+b*perm(ac)+c*perm(ba) ?。╬erm為排列的意思）
? ? ? ? ?特點(diǎn)1：
? ? ? ? ? ? 當(dāng)perm(bc)->b*perm(c)時(shí)，即perm的數(shù)目只有一個(gè)時(shí)，即為輸出
? ? ? ? ?特點(diǎn)2：
? ? ? ? ? ? perm(abc)->perm(bc)->perm(c)即 perm的數(shù)目遞減的過程，為遞歸部分
? ? ? ? ?特點(diǎn)4： 將遞歸的操作作為自操作，完成當(dāng)前整體的操作
? ? ? ? ? 一次，在一次整體的操作中， 需要abc, ?bac, cba三個(gè)，進(jìn)行整體到部分的操作（即遞歸操作）。 ?
? ? ? ? ? ?而abc, bac, cba 是a 與 b, 與c交換的結(jié)果，因此，答案就出來了：
//Implementation?Permutation?n?numbers??
//交換位置??
template??
void?swap(T?&a,?T?&b)??
{??
????T?temp?=?a;??
????a?=?b;??
????b?=?temp;??
}??
//全排列,??
//list為排列的數(shù)的數(shù)組，如{1,?2,?3}???
//int?k?為排列數(shù)組的起始點(diǎn)，int?m?為排列數(shù)組的終點(diǎn)??
//如k=0,m=2??將1,2,3進(jìn)行全排列，當(dāng)?k=1,??m=2,將2,3全排列??
template??
void?permulateNumber(T?list[],?int?k,?int?m)??
{??
if?(k?==?m)?//輸出條件，整體變部分，k?逐漸逼近?m直到=m??
????{??
//特點(diǎn)1?基本部分,?完成數(shù)組從第一個(gè)到最后一個(gè)數(shù)的輸出??
for?(int?i?=?0;?i?<=?m;?++i)??
????????{??
????????????std::cout?<<?list[i];??
????????}??
????????std::cout?<<?std::endl;??
????}??
else{//特點(diǎn)2?遞歸部分??
//以下為特點(diǎn)4??
for?(int?i?=?k;?i?<=?m;?++i)??
????????{??
swap(list[k],?list[i]);//?完成當(dāng)前排列部分中，第一個(gè)數(shù)，與后面數(shù)的交換??
permulateNumber(list,?k?+?1,?m);//特點(diǎn)3?整體到部分??
????????????swap(list[i],?list[k]);???
????????}??
????}??
}??
PS:遞歸算法可以理解為一種思想，還有一切其他例子的應(yīng)用可以參考鏈接
