【排序演算法】之lowb三人組（冒泡、插入、選擇）
- 什么是lowb三人組
- 冒泡排序（bubble sort）
- 插入排序（insert sort）
- 選擇排序（select sort）
- 說明
排序演算法是大多數人入門演算法的基礎，這篇博文便介紹一下著名的lowb三人組及其代碼實作（基于c語言），
什么是lowb三人組
lowb三人組指的是排序演算法中的冒泡排序（bubble sort）插入排序（insert sort）查找排序（insert sort）這三種演算法理解和實作起來簡單，時間復雜度均為O（n^2），相比于一些牛B的演算法就 比較lowb，因此得名，
冒泡排序（bubble sort）
冒泡排序可以想象是在燒開水，開水沸騰的時候氣泡便會從底冒到頂，
以陣列{3，2，4，1，6，5}為例：
要想把它按升序排列，可采取以下方案：
3>2,交換3和2得到2，3，4，1，6，5
3<4,pass看下一組
4>1,交換4和1得到2，3，1，4，6，5
4<6,pass看下一組
6>5，交換6和5得到2，3，1，4，5，6
上述程序稱為冒泡排序的一趟，也就是一次冒泡，一次冒泡程序中，最大的“泡泡”會冒到頂端，也就是陣列的最后一個元素，我們將其定為有序區，前面的稱為，一次冒泡會導致有序區元素+1，無序區則-1，對無序區繼續進行一次冒泡，
2，1，3，4， （無序區）|（有序區）5 ，6
回圈下去直至無序區為空（冒泡n（陣列長度）趟）則排序完成，（無序區元素為1的時候，它一定是無序區最大的，直接放入有序區其實就可以完成排序了（即冒泡n-1趟便可）），
下面請觀看一段魔性舞蹈，幫助理解冒泡吧~
[bilibili]冒泡排序魔性舞蹈點此觀看
上述程序代碼實作如下：
void bubble_sort(int nums[],int size)
{
//進行第i趟,i從0開始計數，每一趟最大的“泡泡”會冒到陣列末尾
for (int i = 0; i < size-1; i++)
{
for (int j = 0; j<size-i-1; j++)//對無序區進行一趟冒泡的程序
{
//比后面的數大，交換
if (nums[j]>nums[j + 1])
{
int tmp = nums[j];
nums[j] = nums[j + 1];
nums[j + 1] = tmp;
}
}
}
}
其實對于上述代碼還可以進一步優化：
比如陣列{3，2，4，1，6，5}冒泡3次后便排好了，
之后的回圈啥都沒做，
故當出現有一趟完成后陣列沒有改變，就可以認為已經排好，
void bubble_sort(int nums[],int size)
{
//進行第i趟,i從0開始計數，每一趟最大的“泡泡”會冒到陣列末尾
for (int i = 0; i < size-1; i++)
{
int isSorted = 1;
for (int j = 0; j<size-i-1; j++)//對無序區進行一趟冒泡的程序
{
//比后面的數大，交換
if (nums[j]>nums[j + 1])
{
int tmp = nums[j];
nums[j] = nums[j + 1];
nums[j + 1] = tmp;
//陣列有改變將isSort賦值0
isSorted = 0;
}
}
if (isSorted == 1)
{
//陣列沒有改變，已經排好了
return;
}
}
}
插入排序（insert sort）
這個是我認為最好理解的演算法，相信大家一定斗過地主，大家一定會這樣理牌
摸到第一張牌，拿在手上，將它作為有序區，
摸第二張牌，與第一張比較，大就放在右邊，小就放左邊，然后它也加入了有序區，
摸第三張牌，它比有序區第二張小就放在第二張前面，成了第二張牌，第二張變成第三張，再與第一張比較一下，比第一張小再放前面.
…
摸到最后一張牌也放入有序區，就排好序啦~
[bilibili]插入排序魔性舞蹈
直接上代碼：
void insert_sort(int nums[], int size)
{
//從第1張開始，摸size-1張牌，每一張牌插入有序區
for (int i = 1; i < size;i++ )
{
int tmp_inx = i;
while (tmp_inx>0&&nums[tmp_inx] < nums[tmp_inx - 1])//只要這張牌不是第一張并且比前一張小就往前面放
{
//將第i張牌放到第i-1張牌前面
int tmp = nums[tmp_inx];
nums[tmp_inx] = nums[tmp_inx - 1];
nums[tmp_inx - 1] = tmp;
tmp_inx--;
}
}
}
選擇排序（select sort）
選擇排序的原理也很簡單，
我們將陣列遍歷一遍，能找到最小的數，
（先把第一個元素當成最小，回圈程序中遇到比它小的再把它當成最小，回圈結束后便能找到最小的了，）
然后再剩下的元素中繼續遍歷可以找到第二小的數，
…
容易想到再拿一個陣列來依次存放第幾小的數，但是再使用一個陣列又要開辟記憶體空間，一般不提倡，
想要原地排序，我們可以就最小的數與下標為0的數交換，然后作為有序區，對無序區再找出第二小的與下標為1的數交換…同樣等到無序區只剩最后一個數的時候便可結束，
[bilibili]選擇排序魔性舞蹈
void select_sort(int nums[], int size)
{
//尋找i次，最后只剩一個一定是最大的數
for (int i = 0; i < size - 1; i++)
{
//在無序區中找出最小的數
int tmp = nums[i];
int inx = i;
for (int j = i; j < size-1; j++)
{
if (nums[j + 1] < tmp)
{
tmp = nums[j + 1];
inx = j+1;
}
}
nums[inx] = nums[i];
nums[i] = tmp;
}
}
說明
博主初學編程，很多東西了解不夠，若文中有錯誤，敬請指出，
另外附上我的GitHub里面有一些自己寫的小程式
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/274771.html
標籤：其他
上一篇：C++ list類的模擬實作
下一篇：【C語言初階】初識c語言