<style>
html, body, .ui-content {
background: #222222;
color: #00BFFF;
}
::-webkit-scrollbar {
width: 10px;
}
::-webkit-scrollbar-track {
background: transparent;
}
::-webkit-scrollbar-thumb {
background: linear-gradient(180deg, #2BE8CF60 0%, #2B83E860 100%);
border-radius: 3px;
}
::-webkit-scrollbar-thumb:hover {
background: linear-gradient(180deg, #2BE8CF95 0%, #2B83E895 100%);
}
/* 設定 code 模板 */
.markdown-body:not(.next-editor) pre {
padding: 16px;
background-color: #404040;
}
.markdown-body code,
.markdown-body tt {
background-color: #ffffff36;
}
.markdown-body .highlight pre,
.markdown-body pre {
color: #ddd;
background-color: #00000080;
}
.token.operator {
background-color: transparent;
}

</style>
###### tags: `Algorithm_Lab`

# Non Comparison Sort 結報
## OJ AC截圖
## Code

#include <bits/stdc++.h>
#define dataRange 101
using namespace std;

inline void countingSort(vector<int> &nums, int exp, int radix) {
    vector<int> count(radix, 0), result(nums.size());
    for (auto &num : nums)
        ++count[(num / exp) % radix];
    for (int i = 1; i < radix; ++i) {
        count[i] = count[i] + count[i - 1];
    }
    for (int i = nums.size() - 1; i >= 0; --i) {
        count[(nums[i] / exp) % radix]--;
        result[count[(nums[i] / exp) % radix]] = nums[i];
    }
    for (int i = 0; i < nums.size(); ++i) {
        nums[i] = result[i];
    }
    return;
}
void RadixSort(vector<int> &nums, int radix) {
    int exp = 1, Max = INT_MIN;
    for (auto &num : nums)
        Max = max(num, Max);
    while (Max / exp > 0) {
        countingSort(nums, exp, radix);
        exp *= radix;
    }
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    while (cin >> n && n != 0) {
        vector<int> nums(n);
        for (int i = 0; i < n; ++i)
            cin >> nums[i];

        RadixSort(nums, 20);
        for (int i = 0; i < n - 1; ++i)
            cout << nums[i] << " ";
        cout << nums.back() << endl;
    }
}

### $Assume$ $nums' size = n, radix = r, d = ceil(\log_r maxElement) + 1$
## 空間複雜度分析

1. 變數：i(6), exp, Max, num, n
2. 陣列：count \(r\), result(n)
total: r + n + 10
**O(n + r)**

## 時間複雜度分析

### Best Case && Worst Case
* RadixSort 找最大值(n)，while迴圈(d)
* CountintSort 計算數字出現次數(n)，計算答案位置\(r\)，放入result(n)，複製回nums(n)
* = n + d * (4 * n + r)
* **O(d * (n + r))**

## DATE

2023/03/14