# 演算法
### tree traversal

#include <iostream>
#include <vector>

using namespace std;



struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
		int n = inorder.size();
        int Idx = 0;
        return helper(preorder, inorder, Idx, 0, n-1);
    }
    
    TreeNode* helper(vector<int>& preorder, vector<int>& inorder, int& Idx, int left, int right) {
        if (left > right) return NULL;
        int pivot = left;  // find the root from inorder
        while(inorder[pivot] != preorder[Idx]) pivot++;
        
        Idx++;
        TreeNode* newNode = new TreeNode(inorder[pivot]);
        newNode->left = helper(preorder, inorder, Idx, left, pivot-1);
        newNode->right = helper(preorder, inorder, Idx, pivot+1, right);
        return newNode;
    }
};

void inorderTraversal(TreeNode* root)
{
    if (root == nullptr) {
        return;
    }
 
    inorderTraversal(root->left);
    cout << root->val << ' ';
    inorderTraversal(root->right);
}

void preorderTraversal(TreeNode* root)
{
    if (root == nullptr) {
        return;
    }
 
    cout << root->val << ' ';
    preorderTraversal(root->left);
    preorderTraversal(root->right);
}
 

int main(){
    vector<int> inorder = { 4, 2, 1, 7, 5, 8, 3, 6 };
    vector<int> preorder = { 1, 2, 4, 3, 5, 7, 8, 6 };
    Solution aSolution;
    TreeNode* root = aSolution.buildTree(preorder, inorder);

    cout << "The inorder traversal is "; inorderTraversal(root);
    cout << "\nThe preorder traversal is "; preorderTraversal(root);
}

## ***碎形***
### ***Koch Snowflake***
周長


### ***Sierpinski Triangle***

------------

## ***tree***
滿二元樹 ( Full Binary tree ) : 全滿
完全二元樹 ( Complete tree ) : 最後一層沒滿 ， 其他全滿



> 選擇排序不是一個穩定的排序演算法
> 序列5 8 5 2 9，我們知道第一遍選擇第1個元素5會和2交換，那麼原序列中2個5的相對前後順序就被破壞了

> （這裡的log是以2為底的)

::: info
## stable
(1)氣泡排序(bubblesort)

氣泡排序就是把小的元素往前調或者把大的元素往後調。比較是相鄰的兩個元素比較，交換也發生在這兩個元素之間。所以，如果兩個元素相等，我想你是不會再無聊地把他們倆交換一下的；如果兩個相等的元素沒有相鄰，那麼即使通過前面的兩兩交換把兩個相鄰起來，這時候也不會交換，所以相同元素的前後順序並沒有改變，所以==氣泡排序是一種穩定排序演算法==。

(2)選擇排序(selectionsort)

選擇排序是給每個位置選擇當前元素最小的，比如給第一個位置選擇最小的，在剩餘元素裡面給第二個元素選擇第二小的，依次類推，直到第n - 1個元素，第n個元素不用選擇了，因為只剩下它一個最大的元素了。那麼，在一趟選擇，如果當前元素比一個元素小，而該小的元素又出現在一個和當前元素相等的元素後面，那麼交換後穩定性就被破壞了。比較拗口，舉個例子，序列5 8 5 2 9，我們知道第一遍選擇第1個元素5會和2交換，那麼原序列中2個5的相對前後順序就被破壞了，所以==選擇排序不是一個穩定的排序演算法==。

(3)插入排序(insertionsort)
插入排序是在一個已經有序的小序列的基礎上，一次插入一個元素。當然，剛開始這個有序的小序列只有1個元素，就是第一個元素。比較是從有序序列的末尾開始，也就是想要插入的元素和已經有序的最大者開始比起，如果比它大則直接插入在其後面，否則一直往前找直到找到它該插入的位置。如果碰見一個和插入元素相等的，那麼插入元素把想插入的元素放在相等元素的後面。所以，相等元素的前後順序沒有改變，從原無序序列出去的順序就是排好序後的順序，所以==插入排序是穩定的==。

(4)快速排序(qicksort)
快速排序有兩個方向，左邊的i下標一直往右走，當a[i] <= a[center_index]，其中center_index是中樞元素的陣列下標，一般取為陣列第0個元素。而右邊的j下標一直往左走，當a[j] > a[center_index]。如果i和j都走不動了，i <= j，交換a[i]和a[j],重複上面的過程，直到i > j。 交換a[j]和a[center_index]，完成一趟快速排序。在中樞元素和a[j]交換的時候，很有可能把前面的元素的穩定性打亂，比如序列為5 3 3 4 3 8 9 10 11，現在中樞元素5和3（第5個元素，下標從1開始計）交換就會把元素3的穩定性打亂，所以==快速排序是一個不穩定的排序演算法==，不穩定發生在中樞元素和a[j] 交換的時刻。

(5)歸併排序(mergesort)
歸併排序是把序列遞迴地分成短序列，遞迴出口是短序列只有1個元素（認為直接有序）或者2個序列（1次比較和交換），然後把各個有序的段序列合併成一個有序的長序列，不斷合併直到原序列全部排好序。可以發現，在1個或2個元素時，1個元素不會交換，2個元素如果大小相等也沒有人故意交換，這不會破壞穩定性。那麼，在短的有序序列合併的過程中，穩定是是否受到破壞？沒有，合併過程中我們可以保證如果兩個當前元素相等時，我們把處在前面的序列的元素儲存在結果序列的前面，這樣就保證了穩定性。所以，==歸併排序也是穩定的排序演算法==。

(6)基數排序(redixsort)
基數排序是按照低位先排序，然後收集；再按照高位排序，然後再收集；依次類推，直到最高位。有時候有些屬性是有優先順序順序的，先按低優先順序排序，再按高優先順序排序，最後的次序就是高優先順序高的在前，高優先順序相同的低優先順序高的在前。基數排序基於分別排序，分別收集，所以==基數排序是穩定的排序演算法==。

(7)希爾排序(shell)
希爾排序是按照不同步長對元素進行插入排序，當剛開始元素很無序的時候，步長最大，所以插入排序的元素個數很少，速度很快；當元素基本有序了，步長很小， 插入排序對於有序的序列效率很高。所以，希爾排序的時間複雜度會比O(n^2)好一些。由於多次插入排序，我們知道一次插入排序是穩定的，不會改變相同元素的相對順序，但在不同的插入排序過程中，相同的元素可能在各自的插入排序中移動，最後其穩定性就會被打亂，==所以shell排序是不穩定的==。
:::
https://www.runoob.com/w3cnote/insertion-sort.html
https://web.ntnu.edu.tw/~algo/Sort.html
http://spaces.isu.edu.tw/upload/18833/3/web/sorting.htm

## radix sort

#include <iostream>
using namespace std;

void swap(int &a, int &b);
void serchigsort(int *arr, int n);
void selectionsort(int *arr, int n);
void bubblesort(int *arr, int n);
void insertionsort(int *arr, int n);
void shellsort(int *arr, int n);
void qicksort(int *arr, int left, int right);
void countingsort(int* arr,int n);


int main()
{
    int a[9] = {1, 4, 3, 5, 7, 6, 2, 1, 6};
    // serchigsort(a,sizeof(a)/sizeof(a[0]));
    // selectionsort(a,sizeof(a)/sizeof(a[0]));
    // bubblesort(a,sizeof(a)/sizeof(a[0]));
    // insertionsort(a,sizeof(a)/sizeof(a[0]));
    // shellsort(a, sizeof(a) / sizeof(a[0]));
    // qicksort(a, 0, 8);
    countingsort(a, sizeof(a) / sizeof(a[0]));


    for (int i = 0; i < 9; i++)
    {
        cout << a[i];
    }
}

void swap(int &a, int &b)
{
    int temp = a;
    a = b;
    b = temp;
}

// 先找到陣列中的最大最小直
// 要確定順序的位置為count
// 從最小值到最大值回圈，看陣列中有沒有一樣的
// 有的話就和 arr[count] 互換，arr[count] 就會是最小值
// count++
void serchigsort(int *arr, int n)
{
    int maxnum = INT_MIN;
    int mininum = INT_MAX;
    // 先找到陣列中的最大最小直
    for (int i = 0; i < n; i++)
    {
        if (arr[i] > maxnum)
            maxnum = arr[i];
        if (arr[i] < mininum)
            mininum = arr[i];
    }
    // 要確定順序的位置為count
    int count = 0;
    // 從最小值到最大值回圈，看陣列中有沒有一樣的
    for (int i = mininum; i <= maxnum; i++)
    {
        for (int j = 0; j < n; j++)
        {
            // 有的話就和 arr[count] 互換，arr[count] 就會是最小值
            if (arr[j] == i)
            {
                swap(arr[j], arr[count]);
                // count++
                count++;
            }
        }
    }
}

// https://www.runoob.com/w3cnote/selection-sort.html
// 設要確定排序的第i個位置的數 arr[i] 設為 minindex
// 從 i+1 利用 minindex 開始找最小值
// 最後再把最小值與 arr[i] 互換
// 第i個位置就確定了
void selectionsort(int *arr, int n)
{
    for (int i = 0; i < n - 1; i++)
    {
        // 設要確定排序的第i個位置 設為 minindex
        int minindex = i;
        // 從 i+1 利用 minindex 開始找最小值
        for (int j = i + 1; j < n; j++)
        {
            if (arr[j] < arr[minindex])
            {
                minindex = j;
            }
        }
        // 最後再把最小值與 arr[i] 互換
        swap(arr[i], arr[minindex]);
    }
}

// https://www.runoob.com/w3cnote/bubble-sort.html
// 要確定排序的是倒數第i個
// 比較左右兩數，如果第一個比第二個大，就交換他們兩個
// 針對所有元素重複這個動作，除了排好序的，與扣掉排好序的後最後一個
void bubblesort(int *arr, int n)
{
    // 要確定排序的是倒數第i個
    for (int i = 0; i < n - 1; i++)
    {
        // 針對所有元素重複這個動作，除了排好序的，與扣掉排好序的後最後一個
        for (int j = 0; j < n - i - 1; j++)
        {
            // 比較左右兩數，如果第一個比第二個大，就交換他們兩個
            if (arr[j] > arr[j + 1])
            {
                swap(arr[j], arr[j + 1]);
            }
        }
    }
}

// 把第一個元素當作已知有序序列，從第二個元素開始做
// 把要做插入的元素設為flag
// 從flag開始往前找，當flag小於前面有序陣列的元素，把該元素往右移一格
// 檢查下一個元素
// 當flag大於檢查的元素，放在上次被移走的元素原本的位置，等於現在檢查的元素的右邊
void insertionsort(int *arr, int n)
{
    // 把第一個元素當作已知有序序列，從第二個元素開始做
    for (int i = 1; i < n; i++)
    {
        // 把要做插入的元素設為flag
        int flag = arr[i];
        // 從flag開始往前找，當flag小於前面有序陣列的元素，把該元素往右移一格
        int j = i - 1;
        while (j >= 0 && flag < arr[j])
        {
            arr[j + 1] = arr[j];
            // 檢查下一個元素
            j--;
        }
        // 當flag大於檢查的元素，放在上次被移走的元素原本的位置，等於現在檢查的元素的右邊
        arr[j + 1] = flag;
    }
}

// https://ithelp.ithome.com.tw/articles/10277847
// 由大到小定數個 gap ，最後 gap 一定要是一
// 利用 gap 分組做 insertion sort 跨gap為一組
// 例如
// 14276389
// gap 4
// 組別分別為 1,6。4,7。2,8。7,9。
// 做 insertion sort
void shellsort(int *arr, int n)
{
    for (int gap = n / 2; gap > 0; gap /= 2)
    {
        // 把第一個 gap 的元素當已知有序序列
        // 從後面一個個一gap分的組別做 insertion sort
        for (int i = gap; i < n; i++)
        {
            int temp = arr[i];
            int j;
            for (j = i - gap; j >= 0 && arr[j] > arr[i]; j -= gap)
            {
                arr[j + gap] = arr[j];
            }
            arr[j + gap] = temp;
        }
    }
}

// 以最右邊基準點
// 分別從左右開始找
// 左邊要放小於等於 flag 的，所以找比 flag 大的 ， 找到時 i 指在上面
// 右邊要放大於 flag 的，所以找比 flag 小的 ， 找到時 j 指在上面
// 交換 i j 
// 重複直到 i j 重合
// i j 重合後與 flag 位置互換，這時flag左邊都是比她小的，右邊都是比他大的
// 遞迴處理左右兩邊
void qicksort(int *arr, int left, int right)
{
    // 只有一個不用排序
    if (left < right)
    {
        // 以最右邊基準點
        int flag = arr[right];
        int i = left;
        int j = right - 1;
        // 分別從左右開始找
        // 重複直到 i j 重合
        while(i!=j){
            // 左邊要放小於等於 flag 的，所以找比 flag 大的 ， 找到時 i 指在上面
            while(arr[i]<=flag&&i<j){
                i++;
            }
            while(arr[j]>flag&&i<j){
                // 右邊要放大於 flag 的，所以找比 flag 小的 ， 找到時 j 指在上面
                j--;
            }
            // 交換 i j
            swap(arr[i],arr[j]);
        }
        // i j 重合後與 flag 位置互換，這時flag左邊都是比她小的，右邊都是比他大的
        swap(arr[i],arr[right]);
        // 遞迴處理左右兩邊
        qicksort(arr,left,i-1);
        qicksort(arr,i+1,right);

    }
}

void countingsort(int* arr,int n){
    int count[100000]={0};
    for(int i=0;i<n;i++){
        count[arr[i]]++;
    }
    for(int i=0,k=0;k<n;i++){
        while(count[i]--){
            arr[k++]=i;
        }
    }
}