發表新討論
#53668: 常見排序(我 quick_sort也過了)


11155088@gs.hs.ntnu.edu.tw (ace1110)

學校 : 不指定學校
編號 : 298370
來源 : [118.169.28.170]
最後登入時間 ：
2025-09-24 21:58:03
a233. 排序法~~~ 挑戰極限 -- 24TH 成功電研社內考
| From: [118.169.28.170] | 發表日期: 2025-09-24 22:20
#include <iostream>
#include <vector>
#include <cstddef>
#include <algorithm>

constexpr size_t npos = static_cast<size_t>(-1);

template<class T>
void print_data(const std::vector<T>& vec) {
    for (size_t i = 0; i < vec.size(); ++i) {
        std::cout << vec[i];
        if (i + 1 != vec.size()) std::cout << " ";
    }
    std::cout << std::endl;
}

template<class T>
bool bubble_once(std::vector<T>& vec, bool ascending, size_t right) {
    bool sorted = true;
    for (size_t index = 0; index < right; ++index) {
        if (ascending ? (vec[index] > vec[index+1]) : (vec[index] < vec[index+1])) {
            std::swap(vec[index], vec[index+1]);
            sorted = false;
        }
    }
    return sorted;
}

template<class T>
void bubble_sort(std::vector<T>& vec, bool ascending = true) {
    size_t n = vec.size();
    if (n <= 1) return;
    for (size_t right = n-1; right > 0; --right) {
        if (bubble_once(vec, ascending, right)) break;
    }
}

template<class T>
size_t max_index(const std::vector<T>& vec, size_t left) {
    size_t target_index = left;
    for (size_t i = left; i < vec.size(); ++i) {
        if (vec[i] > vec[target_index]) target_index = i;
    }
    return target_index;
}

template<class T>
size_t min_index(const std::vector<T>& vec, size_t left) {
    size_t target_index = left;
    for (size_t i = left; i < vec.size(); ++i) {
        if (vec[i] < vec[target_index]) target_index = i;
    }
    return target_index;
}

template<class T>
void selection_sort(std::vector<T>& vec, bool ascending = true) {
    size_t n = vec.size();
    if (n <= 1) return;
    for (size_t left = 0; left < n-1; ++left) {
        size_t target_index = ascending ? min_index(vec, left) : max_index(vec, left);
        if (target_index != left) std::swap(vec[left], vec[target_index]);
    }
}

template<class T>
void insertion_sort(std::vector<T>& vec, bool ascending = true) {
    for (size_t i = 1; i < vec.size(); ++i) {
        T value = vec[i];
        int j = i - 1;
        while (j >= 0 && (ascending ? (vec[j] > value) : (vec[j] < value))) {
            vec[j+1] = vec[j];
            --j;
        }
        vec[j+1] = value;
    }
}

template<class T>
size_t insertion_sort_subvector(std::vector<T>& vec, bool ascending = true, size_t start = 0, size_t end = npos) {
    if (end == npos)
        end = vec.size() - 1;
    for (size_t i = start + 1; i <= end; ++i) {
        T value = vec[i];
        int j = static_cast<int>(i) - 1;
        while (j >= static_cast<int>(start) && (ascending ? (vec[j] > value) : (vec[j] < value))) {
            vec[j + 1] = vec[j];
            --j;
        }
        vec[j + 1] = value;
    }
    return 0;
}

template<class T>
int partition(std::vector<T>& vec, bool ascending, int start, int end) {
    T pivot = vec[end];
    int i = start - 1;
    for (int j = start; j < end; ++j) {
        if (ascending ? (vec[j] <= pivot) : (vec[j] >= pivot)) {
            ++i;
            std::swap(vec[i], vec[j]);
        }
    }
    std::swap(vec[i + 1], vec[end]);
    return i + 1;
}

template<class T>
void quick_sort(std::vector<T>& vec, bool ascending = true, int start = 0, int end = -1) {
    if (vec.empty()) return;
    if (end == -1) end = static_cast<int>(vec.size() - 1);

    std::vector<std::pair<int, int>> stack = {{start, end}};
    while (!stack.empty()) {
        auto [left, right] = stack.back();
        stack.pop_back();

        if (left >= right) continue;

        // 小於 8 個元素使用 insertion sort
        if (right - left + 1 <= 8) {
            insertion_sort_subvector(vec, ascending, left, right);
            continue;
        }

        int pivot_index = left + rand() % (right - left + 1);
        std::swap(vec[pivot_index], vec[right]);
        pivot_index = partition(vec, ascending, left, right);

        stack.push_back({left, pivot_index - 1});
        stack.push_back({pivot_index + 1, right});
    }
}

template<class T>
void merge(std::vector<T>& vec, bool ascending, std::pair<size_t, size_t> range0, std::pair<size_t, size_t> range1) {
    size_t left0 = range0.first, right0 = range0.second;
    size_t left1 = range1.first, right1 = range1.second;

    std::vector<T> merged;
    merged.reserve((right0 - left0 + 1) + (right1 - left1 + 1));

    size_t i = left0, j = left1;
    while (i <= right0 && j <= right1) {
        if (ascending ? (vec[i] <= vec[j]) : (vec[i] >= vec[j])) {
            merged.push_back(vec[i++]);
        } else {
            merged.push_back(vec[j++]);
        }
    }
    while (i <= right0) merged.push_back(vec[i++]);
    while (j <= right1) merged.push_back(vec[j++]);

    // 複製回 vec
    size_t k = left0;
    for (T val : merged) {
        vec[k++] = val;
    }
}

template<class T>
void merge_sort(std::vector<T>& vec, bool ascending = true) {
    size_t n = vec.size();
    if (n <= 1) return;

    // 將 8 個元素一組排序
    std::vector<std::pair<size_t, size_t>> stack;
    for (size_t i = 0; i < n; i += 8) {
        size_t end = std::min(i + 7, n - 1);
        insertion_sort_subvector(vec, ascending, i, end);
        stack.push_back({i, end});
    }

    // 兩兩合併直到只剩一個區間
    while (stack.size() > 1) {
        std::vector<std::pair<size_t, size_t>> new_stack;
        for (size_t i = 0; i < stack.size(); i += 2) {
            if (i + 1 < stack.size()) {
                merge(vec, ascending, stack[i], stack[i + 1]);
                new_stack.push_back({stack[i].first, stack[i + 1].second});
            } else {
                new_stack.push_back(stack[i]);
            }
        }
        stack = new_stack;
    }
}

int main() {
    int N;
    std::cin >> N;

    std::vector<int> vec(N);
    for (int i = 0; i < N; ++i) {
        std::cin >> vec[i];
    }

    quick_sort(vec); // quick_sort merge_sort 可以過
    print_data(vec);

    return 0;
}


#53669: Re: 常見排序(我 quick_sort也過了)


11155088@gs.hs.ntnu.edu.tw (ace1110)

學校 : 不指定學校
編號 : 298370
來源 : [118.169.28.170]
最後登入時間 ：
2025-09-24 21:58:03
a233. 排序法~~~ 挑戰極限 -- 24TH 成功電研社內考
| From: [118.169.28.170] | 發表日期: 2025-09-24 22:35
#include
#include
#include
#include

constexpr size_t npos = static_cast(-1);

template
void print_data(const std::vector& vec) {
    for (size_t i = 0; i < vec.size(); ++i) {
        std::cout << vec[i];
        if (i + 1 != vec.size()) std::cout << " ";
    }
    std::cout << std::endl;
}

template
bool bubble_once(std::vector& vec, bool ascending, size_t right) {
    bool sorted = true;
    for (size_t index = 0; index < right; ++index) {
        if (ascending ? (vec[index] > vec[index+1]) : (vec[index] < vec[index+1])) {
            std::swap(vec[index], vec[index+1]);
            sorted = false;
        }
    }
    return sorted;
}

template
void bubble_sort(std::vector& vec, bool ascending = true) {
    size_t n = vec.size();
    if (n <= 1) return;
    for (size_t right = n-1; right > 0; --right) {
        if (bubble_once(vec, ascending, right)) break;
    }
}

template
size_t max_index(const std::vector& vec, size_t left) {
    size_t target_index = left;
    for (size_t i = left; i < vec.size(); ++i) {
        if (vec[i] > vec[target_index]) target_index = i;
    }
    return target_index;
}

template
size_t min_index(const std::vector& vec, size_t left) {
    size_t target_index = left;
    for (size_t i = left; i < vec.size(); ++i) {
        if (vec[i] < vec[target_index]) target_index = i;
    }
    return target_index;
}

template
void selection_sort(std::vector& vec, bool ascending = true) {
    size_t n = vec.size();
    if (n <= 1) return;
    for (size_t left = 0; left < n-1; ++left) {
        size_t target_index = ascending ? min_index(vec, left) : max_index(vec, left);
        if (target_index != left) std::swap(vec[left], vec[target_index]);
    }
}

template
void insertion_sort(std::vector& vec, bool ascending = true) {
    for (size_t i = 1; i < vec.size(); ++i) {
        T value = vec[i];
        int j = i - 1;
        while (j >= 0 && (ascending ? (vec[j] > value) : (vec[j] < value))) {
            vec[j+1] = vec[j];
            --j;
        }
        vec[j+1] = value;
    }
}

template
size_t insertion_sort_subvector(std::vector& vec, bool ascending = true, size_t start = 0, size_t end = npos) {
    if (end == npos)
        end = vec.size() - 1;
    for (size_t i = start + 1; i <= end; ++i) {
        T value = vec[i];
        int j = static_cast(i) - 1;
        while (j >= static_cast(start) && (ascending ? (vec[j] > value) : (vec[j] < value))) {
            vec[j + 1] = vec[j];
            --j;
        }
        vec[j + 1] = value;
    }
    return 0;
}

template
int partition(std::vector& vec, bool ascending, int start, int end) {
    T pivot = vec[end];
    int i = start - 1;
    for (int j = start; j < end; ++j) {
        if (ascending ? (vec[j] <= pivot) : (vec[j] >= pivot)) {
            ++i;
            std::swap(vec[i], vec[j]);
        }
    }
    std::swap(vec[i + 1], vec[end]);
    return i + 1;
}

template
void quick_sort(std::vector& vec, bool ascending = true, int start = 0, int end = -1) {
    if (vec.empty()) return;
    if (end == -1) end = static_cast(vec.size() - 1);

    std::vector> stack = {{start, end}};
    while (!stack.empty()) {
        auto [left, right] = stack.back();
        stack.pop_back();

        if (left >= right) continue;

        // 小於 8 個元素使用 insertion sort
        if (right - left + 1 <= 8) {
            insertion_sort_subvector(vec, ascending, left, right);
            continue;
        }

        int pivot_index = left + rand() % (right - left + 1);
        std::swap(vec[pivot_index], vec[right]);
        pivot_index = partition(vec, ascending, left, right);

        stack.push_back({left, pivot_index - 1});
        stack.push_back({pivot_index + 1, right});
    }
}

template
void merge(std::vector& vec, bool ascending, std::pair range0, std::pair range1) {
    size_t left0 = range0.first, right0 = range0.second;
    size_t left1 = range1.first, right1 = range1.second;

    std::vector merged;
    merged.reserve((right0 - left0 + 1) + (right1 - left1 + 1));

    size_t i = left0, j = left1;
    while (i <= right0 && j <= right1) {
        if (ascending ? (vec[i] <= vec[j]) : (vec[i] >= vec[j])) {
            merged.push_back(vec[i++]);
        } else {
            merged.push_back(vec[j++]);
        }
    }
    while (i <= right0) merged.push_back(vec[i++]);
    while (j <= right1) merged.push_back(vec[j++]);

    // 複製回 vec
    size_t k = left0;
    for (T val : merged) {
        vec[k++] = val;
    }
}

template
void merge_sort(std::vector& vec, bool ascending = true) {
    size_t n = vec.size();
    if (n <= 1) return;

    // 將 8 個元素一組排序
    std::vector> stack;
    for (size_t i = 0; i < n; i += 8) {
        size_t end = std::min(i + 7, n - 1);
        insertion_sort_subvector(vec, ascending, i, end);
        stack.push_back({i, end});
    }

    // 兩兩合併直到只剩一個區間
    while (stack.size() > 1) {
        std::vector> new_stack;
        for (size_t i = 0; i < stack.size(); i += 2) {
            if (i + 1 < stack.size()) {
                merge(vec, ascending, stack[i], stack[i + 1]);
                new_stack.push_back({stack[i].first, stack[i + 1].second});
            } else {
                new_stack.push_back(stack[i]);
            }
        }
        stack = new_stack;
    }
}

int main() {
    int N;
    std::cin >> N;

    std::vector vec(N);
    for (int i = 0; i < N; ++i) {
        std::cin >> vec[i];
    }

    quick_sort(vec); // quick_sort merge_sort 可以過
    print_data(vec);

    return 0;
}


以下更新

heap_sort也行

#include <iostream>
#include <vector>
#include <cstddef>
#include <algorithm>

constexpr size_t npos = static_cast<size_t>(-1);

template<class T>
void print_data(const std::vector<T>& vec) {
    for (size_t i = 0; i < vec.size(); ++i) {
        std::cout << vec[i];
        if (i + 1 != vec.size()) std::cout << " ";
    }
    std::cout << std::endl;
}

template<class T>
bool bubble_once(std::vector<T>& vec, bool ascending, size_t right) {
    bool sorted = true;
    for (size_t index = 0; index < right; ++index) {
        if (ascending ? (vec[index] > vec[index+1]) : (vec[index] < vec[index+1])) {
            std::swap(vec[index], vec[index+1]);
            sorted = false;
        }
    }
    return sorted;
}

template<class T>
void bubble_sort(std::vector<T>& vec, bool ascending = true) {
    size_t n = vec.size();
    if (n <= 1) return;
    for (size_t right = n-1; right > 0; --right) {
        if (bubble_once(vec, ascending, right)) break;
    }
}

template<class T>
size_t max_index(const std::vector<T>& vec, size_t left) {
    size_t target_index = left;
    for (size_t i = left; i < vec.size(); ++i) {
        if (vec[i] > vec[target_index]) target_index = i;
    }
    return target_index;
}

template<class T>
size_t min_index(const std::vector<T>& vec, size_t left) {
    size_t target_index = left;
    for (size_t i = left; i < vec.size(); ++i) {
        if (vec[i] < vec[target_index]) target_index = i;
    }
    return target_index;
}

template<class T>
void selection_sort(std::vector<T>& vec, bool ascending = true) {
    size_t n = vec.size();
    if (n <= 1) return;
    for (size_t left = 0; left < n-1; ++left) {
        size_t target_index = ascending ? min_index(vec, left) : max_index(vec, left);
        if (target_index != left) std::swap(vec[left], vec[target_index]);
    }
}

template<class T>
void insertion_sort(std::vector<T>& vec, bool ascending = true) {
    for (size_t i = 1; i < vec.size(); ++i) {
        T value = vec[i];
        int j = i - 1;
        while (j >= 0 && (ascending ? (vec[j] > value) : (vec[j] < value))) {
            vec[j+1] = vec[j];
            --j;
        }
        vec[j+1] = value;
    }
}

template<class T>
size_t insertion_sort_subvector(std::vector<T>& vec, bool ascending = true, size_t start = 0, size_t end = npos) {
    if (end == npos)
        end = vec.size() - 1;
    for (size_t i = start + 1; i <= end; ++i) {
        T value = vec[i];
        int j = static_cast<int>(i) - 1;
        while (j >= static_cast<int>(start) && (ascending ? (vec[j] > value) : (vec[j] < value))) {
            vec[j + 1] = vec[j];
            --j;
        }
        vec[j + 1] = value;
    }
    return 0;
}

template<class T>
size_t partition(std::vector<T>& vec, bool ascending, size_t start, size_t end) {
    T pivot = vec[end];
    if (start >= end) return start;
    size_t left = start, right = end;

    while (true) {
        while (left < right && (ascending ? (vec[left] < pivot) : (vec[left] > pivot))) ++left;
        while (right > left && (ascending ? (vec[right] > pivot) : (vec[right] < pivot))) --right;
        if (left < right) {
            std::swap(vec[left], vec[right]);
            ++left;
            if (right > 0) --right;
        } else {
            break;
        }
    }
    std::swap(vec[left], vec[end]);
    return left;
}

template<class T>
void quick_sort(std::vector<T>& vec, bool ascending = true, int start = 0, int end = -1) {
    if (vec.empty()) return;
    if (end == -1) end = static_cast<int>(vec.size() - 1);

    std::vector<std::pair<int, int>> stack = {{start, end}};
    while (!stack.empty()) {
        auto [left, right] = stack.back();
        stack.pop_back();

        if (left >= right) continue;

        // 小於 8 個元素使用 insertion sort
        if (right - left + 1 <= 8) {
            insertion_sort_subvector(vec, ascending, left, right);
            continue;
        }

        int pivot_index = left + rand() % (right - left + 1);
        std::swap(vec[pivot_index], vec[right]);
        pivot_index = partition(vec, ascending, left, right);

        stack.push_back({left, pivot_index - 1});
        stack.push_back({pivot_index + 1, right});
    }
}

template<class T>
void merge(std::vector<T>& vec, bool ascending, std::pair<size_t, size_t> range0, std::pair<size_t, size_t> range1) {
    size_t left0 = range0.first, right0 = range0.second;
    size_t left1 = range1.first, right1 = range1.second;

    std::vector<T> merged;
    merged.reserve((right0 - left0 + 1) + (right1 - left1 + 1));

    size_t i = left0, j = left1;
    while (i <= right0 && j <= right1) {
        if (ascending ? (vec[i] <= vec[j]) : (vec[i] >= vec[j])) {
            merged.push_back(vec[i++]);
        } else {
            merged.push_back(vec[j++]);
        }
    }
    while (i <= right0) merged.push_back(vec[i++]);
    while (j <= right1) merged.push_back(vec[j++]);

    // 複製回 vec
    size_t k = left0;
    for (T val : merged) {
        vec[k++] = val;
    }
}

template<class T>
void merge_sort(std::vector<T>& vec, bool ascending = true) {
    size_t n = vec.size();
    if (n <= 1) return;

    // 將 8 個元素一組排序
    std::vector<std::pair<size_t, size_t>> stack;
    for (size_t i = 0; i < n; i += 8) {
        size_t end = std::min(i + 7, n - 1);
        insertion_sort_subvector(vec, ascending, i, end);
        stack.push_back({i, end});
    }

    // 兩兩合併直到只剩一個區間
    while (stack.size() > 1) {
        std::vector<std::pair<size_t, size_t>> new_stack;
        for (size_t i = 0; i < stack.size(); i += 2) {
            if (i + 1 < stack.size()) {
                merge(vec, ascending, stack[i], stack[i + 1]);
                new_stack.push_back({stack[i].first, stack[i + 1].second});
            } else {
                new_stack.push_back(stack[i]);
            }
        }
        stack = new_stack;
    }
}

template<class T>
T min(const std::vector<T>& vec) {
    if (vec.empty()) throw std::invalid_argument("vec is empty");
    T min_element = vec[0];
    for (T element : vec) {
        if (element < min_element) min_element = element;
    }
    return min_element;
}

template<class T>
T max(const std::vector<T>& vec) {
    if (vec.empty()) throw std::invalid_argument("vec is empty");
    T max_element = vec[0];
    for (T element : vec) {
        if (element > max_element) max_element = element;
    }
    return max_element;
}

template<class T>
void count_sort(std::vector<T>& vec, bool ascending = true) {
    if (vec.empty()) return;

    T min_val = min(vec);
    T max_val = max(vec);

    size_t range = static_cast<size_t>(max_val - min_val + 1);
    std::vector<size_t> count_list(range, 0);

    // 計數
    for (T element : vec) {
        count_list[static_cast<size_t>(element - min_val)]++;
    }

    // 修改原 vector
    size_t index = 0;
    for (size_t count_index = 0; count_index < range; count_index++) {
        for (size_t c = 0; c < count_list[count_index]; c++) {
            vec[index++] = ascending ? (min_val + static_cast<T>(count_index)) : (max_val - static_cast<T>(count_index));
        }
    }
}

template<class T>
void heapify_down(std::vector<T>& vec, size_t start, size_t end, bool min_heap) {
    size_t root = start;
    while (true) {
        size_t child = 2*root + 1;
        if (child >= end) break;

        // 選擇左右子節點
        if (child + 1 < end && ((min_heap ? vec[child+1] < vec[child] : vec[child+1] > vec[child])))
            child++;

        // 判斷是否需要下沉
        if ((min_heap && vec[root] <= vec[child]) || (!min_heap && vec[root] >= vec[child]))
            break;

        std::swap(vec[root], vec[child]);
        root = child;
    }
}

template<class T>
void in_place_heap_sort(std::vector<T>& vec, bool ascending = true) {
    // ascending → 建 max heap
    bool min_heap = !ascending;
    size_t n = vec.size();

    // 建立 heap
    for (int i = static_cast<int>(n/2) - 1; i >= 0; --i)
        heapify_down(vec, i, n, min_heap);

    // 排序
    for (int i = static_cast<int>(n) - 1; i > 0; --i) {
        std::swap(vec[0], vec[i]);
        heapify_down(vec, 0, i, min_heap);
    }
}

int main() {
    int N;
    std::cin >> N;

    std::vector<int> vec(N);
    for (int i = 0; i < N; ++i) {
        std::cin >> vec[i];
    }

    in_place_heap_sort(vec);
    print_data(vec);

    return 0;
}


ZeroJudge Forum