# [資料結構] CH13. Bubble, Insertion, Selection & Tree Sorts

* 學完搜尋之後，接下來要教的是排序。
* 本章節中教的排序是演算法較為簡單的排序，耗費的時間通常也相較地多。

## Bubble Sort
* 泡沫排序法算是初學者最常接觸、使用的一種排序法。
* 概念是不停地將相鄰的元素做比較，較大者較往後推，藉此找到最大的元素並將其放置最後面的位置。
* 由於較大的值會一直往上浮，就像氣泡一樣，故名泡沫排序法（也有翻譯叫氣泡排序法）。
* 示意圖：</br>
* 第一次會把最大值推到A[n-1]的位置(紅色鍵號)；第二次會將次大值推到A[n-2]的位置(藍色鍵號)...
* 
* Code:

void bubble_sort(int arr[], int len) {
	int i, j;
	for (i = 0; i < len - 1; i++)
		for (j = 0; j < len - 1 - i; j++)
			if (arr[j] > arr[j + 1])
				swap(arr[j], arr[j + 1]);
}

## Insertion Sort
* 插入排序法將陣列分為兩個部分，前段為整理過的、後段為沒有整理過的原始資料。
* 不停地將原始資料中的元素拿起來，插入進已排序資料中正確的位置。
* 示意圖：</br>
* 範例：假設現有一堆未排序資料：

digraph insert {
	node[shape=record]
	
    array [label="<f0>39|<f1>9|<f2>45|<f3>63|<f4>18|<f5>81"];
    
}

* 我們先假設`39`為已排序資料，然後我們要拿起`9`找到它該在的位置放進去。

digraph structs {
    node [shape=plaintext];

    struct1 [label=<<TABLE>
	<TR>
	    <TD BGCOLOR="cornflowerblue">39</TD>
        <TD><FONT COLOR="red">9</FONT></TD>
        <TD>45</TD>
        <TD>63</TD>
        <TD>18</TD>
        <TD>81</TD>
	</TR>
    </TABLE>>];
}

* 我們知道`9`應該要放在`39`前面，如此一來就完成`9`的排序了；接著要拿起`45`。

digraph structs {
    node [shape=plaintext];

    struct1 [label=<<TABLE>
	<TR>
	    <TD BGCOLOR="cornflowerblue">9</TD>
        <TD BGCOLOR="cornflowerblue">39</TD>
        <TD><FONT COLOR="red">45</FONT></TD>
        <TD>63</TD>
        <TD>18</TD>
        <TD>81</TD>
	</TR>
    </TABLE>>];
}

* `45`和`63`都不用動即完成，接著要排`18`。

digraph structs {
    node [shape=plaintext];

    struct1 [label=<<TABLE>
	<TR>
	    <TD BGCOLOR="cornflowerblue">9</TD>
        <TD BGCOLOR="cornflowerblue">39</TD>
        <TD BGCOLOR="cornflowerblue">45</TD>
        <TD BGCOLOR="cornflowerblue">63</TD>
        <TD><FONT COLOR="red">18</FONT></TD>
        <TD>81</TD>
	</TR>
    </TABLE>>];
}

* `18`排進去之後，81也不用動，完成插入排序法。

digraph structs {
    node [shape=plaintext];

    struct1 [label=<<TABLE>
	<TR>
	    <TD BGCOLOR="cornflowerblue">9</TD>
        <TD BGCOLOR="cornflowerblue">18</TD>
        <TD BGCOLOR="cornflowerblue">39</TD>
        <TD BGCOLOR="cornflowerblue">45</TD>
        <TD BGCOLOR="cornflowerblue">63</TD>
        <TD BGCOLOR="cornflowerblue">81</TD>
	</TR>
    </TABLE>>];
}

* Code:

void InsertSort(int arr[], int len)
{
    for (int i = 1; i < len; i++)
    {
        int temp = arr[i];
        int j;
        for (j = i - 1; j >= 0; j--)
        {
            if (arr[j] > temp)
                arr[j + 1] = arr[j];
            else
            {
                break;
            }
        }
        arr[j + 1] = temp;
    }
}

## Selection Sort
* 選擇排序法和剛剛的插入排序法一樣，將陣列分為已整理和未整理兩個部分。
* 不同的地方在於，選擇排序法不是將拿起來的資料和已整理的地方做比較，而是和後面所有未整理的部分做比較，找到最小值後與其交換。
* 示意圖：</br>
* 一樣拿剛剛例子來做一次：

digraph selection {
	node[shape=record]
	
    array [label="<f0>39|<f1>9|<f2>45|<f3>63|<f4>18|<f5>81"];
    
}

* 拿起`39`，和後面最小值交換。

digraph structs {
    node [shape=plaintext];

    struct1 [label=<<TABLE>
	<TR>
        <TD><FONT COLOR="red">39</FONT></TD>
        <TD>9</TD>
        <TD>45</TD>
        <TD>63</TD>
        <TD>18</TD>
        <TD>81</TD>
	</TR>
    </TABLE>>];
}

* 最小值為`9`，交換完畢後，`9`成為已排序資料；接著拿起第二格資料`39`。

digraph structs {
    node [shape=plaintext];

    struct1 [label=<<TABLE>
	<TR>
        <TD BGCOLOR="cornflowerblue">9</TD>
        <TD><FONT COLOR="red">39</FONT></TD>
        <TD>45</TD>
        <TD>63</TD>
        <TD>18</TD>
        <TD>81</TD>
	</TR>
    </TABLE>>];
}

* 最小值為`18`，交換完畢後，`18`成為已排序資料；接著拿起第三格資料`45`。
* 注意到`39`的位置，那是原本`18`的位置。

digraph structs {
    node [shape=plaintext];

    struct1 [label=<<TABLE>
	<TR>
        <TD BGCOLOR="cornflowerblue">9</TD>
        <TD BGCOLOR="cornflowerblue">18</TD>
        <TD><FONT COLOR="red">45</FONT></TD>
        <TD>63</TD>
        <TD>39</TD>
        <TD>81</TD>
	</TR>
    </TABLE>>];
}

* 有點懶的每個都做，反正就`45`和`39`換；`63`和`45`換。

* Code：

void SelectionSort(int arr[], int len)
{
	for (int i = 0; i < len; i++)
	{
		int min = i;
		for (int j = i+1; j < len; j++)
		{
			if (arr[j] < arr[min])min = j;
		}
		Swap(arr[i],arr[min]);
	}
}

## Tree Sort
* 二元樹排序法其實你早就學過了。
* 不相信？[點我！](https://hackmd.io/s/SJGdGV_27)
* 簡單來說，你建一棵二元搜索樹，把資料丟進去，然後用**中序**輸出該樹，你就得到答案了。
* [如何得到樹的中序？](https://hackmd.io/s/rJC1NiQRX#%E5%89%8D%E5%BA%8F%E4%B8%AD%E5%BA%8F%E5%BE%8C%E5%BA%8F)

###### tags: `DS` `note`