几种内排序算法#

[MyLinChi]

堆排序算法

class Solution {
private:
    int size;
    void ajustDown(vector<int>& nums, int k,int s) {
        nums[0] = nums[k];
        for (int i = 2 * k; i <= s;i*=2) {
            if (i < s && nums[i] < nums[i + 1])++i;
            if (nums[0] >= nums[i])break;
            else {
                nums[k] = nums[i];
                k = i;
            }
        }
        nums[k] = nums[0];
    }

    void buildHeap(vector<int>& nums) {
        for (int i = size / 2; i > 0; --i)ajustDown(nums, i,size);
    }

    void heapSort(vector<int>& nums) {
        for (int i = size; i > 1; --i) {
            nums[0] = nums[1];
            nums[1] = nums[i];
            nums[i] = nums[0];
            ajustDown(nums, 1, i - 1);
        }
    }
public:
    void fun() {
        vector<int> data;
        int num;
        for (; cin >> num;)data.push_back(num);
        size = data.size();
        data.insert(data.begin(), 0);
        buildHeap(data);
        heapSort(data);
        for (int i = 1; i <=  size; ++i)
            cout << data[i] << " ";
        cout << endl;
    }
};

归并排序算法

#include<iostream>
#include<vector>
#include<unordered_set>
#include<unordered_map>
#include<string>
#include<stack>
#include<algorithm>
using namespace std;

class Solution {
private:
    vector<int> B;
    void Merge(vector<int>& nums,int low,int mid,int high) {
        for (int i = low; i <= high; ++i)B[i] = nums[i];
        int i = low, j = mid + 1,k=low;
        for (; i <= mid && j <= high;) {
            if (B[i] < B[j]) {
                nums[k++] = B[i++];
            }
            else {
                nums[k++] = B[j++];
            }
        }
        for(;i<=mid;)nums[k++] = B[i++];
        for(;j<=high;)nums[k++] = B[j++];
    }
    void MergeSort(vector<int>& nums,int low,int high) {
        if (low < high) {
            int mid = low + ((high - low) >> 1);
            MergeSort(nums, low, mid);
            MergeSort(nums, mid+1, high);
            Merge(nums,low, mid, high);
        }
    }
public:
    void fun() {
        vector<int> nums;
        int num;
        for (; cin >> num; nums.push_back(num));
        B = vector<int>(nums.size());
        MergeSort(nums,0,nums.size()-1);
        for (int i = 0; i < nums.size(); ++i) {
            if (i)cout << " ";
            cout << nums[i];
        }
        cout << endl;
    }
};

int main() {
    Solution sol;
    sol.fun();
    return 0;
}

基数排序

list是一个类，里面有头结点，指向头结点的指针，尾结点指针。

#include<iostream>
#include<vector>
#include<unordered_set>
#include<unordered_map>
#include<string>
#include<stack>
#include<algorithm>
using namespace std;

class Solution {
private:
    vector<int> nums;
    struct node
    {
        int val;
        node* next;
        node(int val):val(val),next(nullptr) {}
    };

    class list
    {
    public:
        node* head;
        node* tail;
        list() {
            node* t = new node(0);
            head = t;
            tail = t;
        }
        void put(node* d) {
            tail->next = d;
            tail = d;
            tail->next = nullptr;
        }
        void output() {
            for (node* p = head->next; p != nullptr; p = p->next)
                cout << p->val << " ";
            cout << endl;
        }
    };

    vector<list> buck;
    list allnum;
    int valIn(int num,int pos) {
        for (int i = 0; i < pos;++i, num /= 10);
        return num % 10;
    }

    void allocate(node* p, int pos) {
        int index = valIn(p->val, pos);
        buck[index].put(p);
    }

    void BaseNuMSort(vector<int>& nums) {
        for (int i = 0; i < 32; ++i) {
            for (node* p = allnum.head->next; p != nullptr;) {
                node* t = p->next;
                allocate(p,i);
                p = t;
            }
            allnum.head->next = nullptr;
            allnum.tail = allnum.head;
            for (int j = 0; j < 10; ++j) {
                if (buck[j].head->next != nullptr) {
                    allnum.tail->next = buck[j].head->next;
                    allnum.tail = buck[j].tail;
                    buck[j].head->next = nullptr;
                    buck[j].tail = buck[j].head;
                }
            }
        }
    }
public:
    void fun() {
        int num;
        buck = vector<list>(10);
        for (; cin >> num; nums.push_back(num));
        for (int i = 0; i < nums.size(); ++i) {
            allnum.put(new node(nums[i]));
        }
        BaseNuMSort(nums);
        allnum.output();
    }
};

int main() {
    Solution sol;
    sol.fun();
    return 0;
}