最近在學習算法與數據結構，算法是一個程序員的基本功富拗，但是我不是科班出身，所以這方面的知識有所欠缺鸣戴。在慕課網上找到一套對應的課程啃沪，主講老師是liuyubobobo,從我學習的感受和體驗來看，bobo老師對一個問題講解的相當清晰和透徹窄锅，普通話說的也好创千，適合初學者理解和學習。大家如果想學習算法與數據結構的知識入偷，我推薦這一套教程追驴。地址鏈接：https://coding.imooc.com/class/71.html。 這一系列文章主要是對這套課程的內容以文字的形式展示盯串。做這個事情一是想對視頻上的知識點在通過形成文字的過程中氯檐，加深自己的理解。二是想加強自己的表達能力体捏。
這篇文章主要講解3個基礎的排序算法，選擇排序糯崎，插入排序几缭，以及冒泡排序，其時間復雜度都是0(n^2)級別的沃呢，實現代碼使用c++語言年栓。
選擇排序
首先給定一個元素是無序的整數數組：
需要對這個數組中的8個整數進行從小到大的排序。
選擇排序的基本思路
首先從起始位置index = 0開始薄霜，遍歷一遍數組某抓，獲取到最小的元素值index = 4 的元素纸兔，元素值為1，然后將index = 0與index = 4 上的兩個元素交換位置否副，此時index = 0 上的元素值1汉矿。index = 4上的元素值為5。紅色為已排序完成的有序區(qū)域备禀。
找到了最小的元素放在數組的第一位后洲拇，接著從index = 1開始往后遍歷數組。找到第二小的元素后再與index = 1的位置交換元素曲尸，此時赋续，index = 1上的元素值為2，index = 2 上的元素為4.
接著再從index = 2的位置往后遍歷數組另患，找到第三小的元素后再與index = 2上的元素交換位置纽乱，交換后，index = 2上的元素為3昆箕，index = 5 上的元素為4鸦列。
然后依此遍歷的方法，直到數組的最后一個位置存放的是最大的元素为严。選擇排序的整體思想不難理解敛熬，就是循環(huán)一遍數組找到循環(huán)元素中最小的元素，再與已排好序的下一個索引上的元素交換位置第股。
代碼實現
我寫成一個函數应民，傳入一個數組以及元素的個數：
template <typename T>
void selectionSort(T arr[],int n){
for (int i = 0; i < n; i++) {
int minIndex = i; // minIndex保存內層循環(huán)中最小值的索引
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
swap(arr[i], arr[minIndex]);
}
}
插入排序
插入排序的基本思路
bobo老師打個這樣一個比方，我覺得用來理解插入排序非常合適：就好像有一副牌夕吻，三個人用這副牌來斗地主诲锹，分牌階段，你需要將你摸到的牌放在手中的牌中的合適位置涉馅，手中的牌是整理好的归园，是有序的，放入后稚矿，使其整體依舊有序庸诱。我們來模擬一下這個過程。首先固定手中有一張牌晤揣，用紅色標記為手中已整理好的牌桥爽。
接著摸第二張牌，為4昧识，比5小钠四，所以放在5的前面，4與5交換位置跪楞。
接著摸第三張牌缀去，為2侣灶，2比5小，所以先放在5的前面缕碎，4的后面褥影。
此時這里并不是2合適的位置，繼續(xù)和前面的元素比較阎曹，2比4小伪阶，所以要放到4的前面。此時變成有序了处嫌。
[圖片上傳失敗...(image-231474-1535017882614)]
接著再摸第四張牌栅贴，為7，7比5小熏迹，發(fā)現不用交換位置檐薯，放在原地就好了。
就這樣注暗，按照這個方法坛缕，將摸到的牌與整理好的牌依次做比較，使其放在合適的位置捆昏，直到摸完最后一張牌赚楚。
代碼實現
template <typename T>
void insertionSort(T arr[],int n){
for (int i = 1; i < n; i++) {
for (int j = i; j > 0; j--) {
if (arr[j-1] > arr[j]) {
swap(arr[j - 1],arr[j]);
} else {
break;
}
}
}
}
注意：第一層for循環(huán)時 i = 1，i不是從零開始骗卜。因為第一張牌不需要排序宠页，從第二張牌開始。所以設置i = 1寇仓。
在[0 i) 前閉后開這個區(qū)間中為已排好序的元素举户，i為待排序的元素的索引，第二層for循環(huán)是從待整理的元素索引i開始遍烦。在已排好序的區(qū)間[0,i)中俭嘁，從后往前遍歷。 如果發(fā)現前面的元素比它大服猪，則兩個元素交換位置供填。當發(fā)現前面的元素比它小的時候，此時它就找到了合適的位置罢猪。就不需要再遍歷了捕虽，直接結束這一層循環(huán)。
插入排序優(yōu)化
在交換兩個元素位置的時候,調用了swap(arr[j - 1],arr[j])坡脐，而一次交換其實是三次賦值，這句代碼其實也可以改寫為：
int temp = arr[j-1];
arr[j-1] = arr[j];
arr[j] = temp;
如果一個較小的元素要插入到合適的位置房揭，肯定要一路交換很多次备闲。這無形中就增加了排序時間晌端。優(yōu)化思路就是只進行賦值操作而不進行交換操作，先保存一份待排序的元素恬砂，然后遍歷已排好序的元素咧纠，從后往前進行逐一比較，如果當遍歷到index = j的元素時泻骤，j - 1索引上的元素要比j位置上的元素大漆羔，則將j - 1索引位置的元素往后挪，往后挪也就是將j索引位置的元素賦值為j-1索引位置的元素狱掂，當遍歷到j-1索引上的元素比元素j位置上的元素小或相等時演痒，就說明上一次循環(huán)往后挪而騰出來的位置為待排序的合適位置，在將該位置的值賦值為待排序的值就好了趋惨。
假定現在按照優(yōu)化的思路對1進行排序鸟顺，紅色為已排好序的部分。
首先先復制一份待排序的元素1
然后將待排序的元素與已排好序的index = 3位置器虾，值為7的元素比較讯嫂，如果這個元素比待排序的元素要大，則直接將待排序的值復制為這個元素兆沙。7 比 1 大欧芽，7往后挪，所以待排序位置上的元素值賦值為7葛圃，而index = 3位置就騰出來了千扔。
然后依次往前與帶排序的元素比較。這次是index = 2 時的 5 與 1比較装悲， 5比1大昏鹃，5往后挪，將index = 3 位置上的元素賦值為5诀诊，index = 2這個位置就騰出來了洞渤。
再將index = 1 時的4 與 待排序的元素1比較，4 還是比1 大属瓣，4往后挪载迄，將 index = 2位置賦值為4，index = 1這個位置就騰出來了抡蛙。
繼續(xù)护昧。再將index = 0時的2, 與待排序的元素1比較，2還是比1大粗截，2往后挪惋耙，將index = 1位置賦值為2，index = 0這個位置騰出來了。
那么騰出來的位置上為元素的前面已沒有元素可以比較了绽榛。所以此時在index = 0的位置上放置上待排序的元素湿酸。
元素1經過一番波折，塵埃落定灭美，終于找到了他合適的位置推溃，元素1排序完畢
然后index = 5上的元素3按照上述方法找到合適的位置，index = 6 上的元素按照上述方法找到合適的位置届腐，接著是index = 7上的元素铁坎。將所有的元素都按照上述方法找到自己合適的位置。
代碼實現
template <typename T>
void insertionSort(T arr[],int n){
for (int i = 1; i < n; i++) {
T e = arr[i]; // 保存待插入索引為i時的元素e
int j = i; // j保存元素e應該插入的位置
for (j = i; j > 0; j--) {
if (arr[j-1] > e) {
arr[j] = arr[j-1];
}
}
arr[j] = e;
}
}
冒泡排序
冒泡排序實現思路
首先還是這一個由8個數組成的一個無序的數組
冒泡排序的核心思想就是將相鄰的兩個元素兩兩比較犁苏，根據大小來交換元素的位置
首先硬萍，5與4比較，5比4大傀顾，我們的需求是從小到達排列襟铭，4需要在5的前面，所以4與5交換位置短曾，紅色表示兩個要交換位置的元素寒砖。
交換后
然后, 5與2開始比較，5比2大嫉拐，交換位置
交換后
繼續(xù)哩都， 5和7比較，5比7小婉徘，位置保持不變
go on漠嵌， 7與1比較，7比1大盖呼，交換位置
交換后
不要停儒鹿，7與3比較，7比3大几晤，交換位置
交換后
繼續(xù)深入约炎， 7與8比較，7比8小蟹瘾，保持不變
還有最后一個圾浅，8與6比，8比6大憾朴，交換位置
交換后
這樣一輪下來狸捕，元素8排到了最右側，此時紅色代表?已排好序的區(qū)域
接著按照上述方法众雷，重新重頭開始相鄰元素兩兩遍歷灸拍，前一個元素比后一個元素大則交換位置做祝，小則保持位置不變，一路比較下來株搔。找到第二大的元素放到元素8的左側剖淀。
然后是
然后是
給定的一組無序的整數數組，按照排序的思路來講纤房，藍色區(qū)域屬于無序的區(qū)域，還需要比較翻诉，但是上面圖片中藍色部分已經是有序的了炮姨，這可以作為一個優(yōu)化的方面，就是當發(fā)現代排區(qū)域中的元素已經是有序了的時候碰煌，排序完成舒岸，結束排序，下面的代碼中不涉及這部分的優(yōu)化芦圾。
實現代碼
template <typename T>
void BubbleSort(T arr[],int n){
for (int i = 0; i < n; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j+1]) {
swap(arr[j],arr[j+1]);
}
}
}
}
代碼不難理解蛾派，雙層循環(huán)，外層每一次循環(huán)確定一個最大值放在數組的右側个少，內層尋找這個最大值洪乍。先進行元素比較，滿足則交換夜焦。
冒泡排序的優(yōu)化
剛剛在逐步比較的時候壳澳，出現了這樣一種情況：藍色的無序區(qū)域中的元素已經是有序的了。
但是上面的冒泡排序的代碼還會繼續(xù)的比較下去茫经。每一個元素都會參與外層循環(huán)巷波，直到循環(huán)結束。所以優(yōu)化方向是在無序區(qū)域中的元素已經有序了的情況下結束循環(huán)卸伞。
優(yōu)化后的代碼,部分解釋見注釋抹镊。
void BubbleSort(T arr[],int n){
for (int i = 0; i < n; i++) {
bool isSorted = true; // 用一個bool值來標記每一層是否是有序的，默認為true.
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j+1]) {
swap(arr[j],arr[j+1]);
isSorted = false; // 如果有交換元素荤傲，那么不是有序垮耳，該bool值改為false.
}
}
if (isSorted) { // 在內層中，如果該bool值沒有被改為false,那么就說明內層沒有元素交換弃酌，那么該數列排序完成了氨菇，直接結束循環(huán)。
break;
}
}
}
這個優(yōu)化主要是用一個bool值做標記妓湘，來確定是否有序查蓉。在內層循環(huán)中如果沒有元素交換，那么這個數列肯定就是有序的了榜贴，那么外層就無需在循環(huán)了豌研。
下次學習內容：歸并排序
