排序算法总结

排序算法

快排

void quick_sort(vector<int> &nums, int l, int r) {
    if(l >= r) {
        return ;
    }
    
    int first = l, last = r;
    int key = nums[first];
    while(first < last) {
        // 从右往左找到第一个比key小的
        while(first < last && nums[last] >= key) {
            --last;
        }
        // 交换，将其放到左边
        nums[first] = nums[last];
        // 从左往右找到第一个比key大的
        while(first < last && nums[first] <= key) {
            ++first;
        }
        // 交换，将其放到右边
        nums[last] = nums[first];
    }
    nums[first] = key;
    quick_sort(nums, l, first);
    quick_sort(nums, first + 1, r);
}

归并排序

void merge_sort(vector<int>& nums, int lhs, int rhs) {
    if(lhs >= rhs) return;
    int mid = (lhs + rhs) / 2;
    merge_sort(nums, lhs, mid);
    merge_sort(nums, mid + 1, rhs);
    int l = lhs, r = mid + 1;
    int i = 0;
    vector<int> tmp(rhs - lhs + 1);
    while(l <= mid && r <= rhs) {
        if(nums[l] <= nums[r]) {
            tmp[i++] = nums[l++]; 
        } else {
            tmp[i++] = nums[r++];
        }
    }
    while(l <= mid) {
        tmp[i++] = nums[l++]; 
    }
    while(r <= rhs) {
        tmp[i++] = nums[r++];
    }
    for(int j = lhs; j <= rhs; ++j) {
        nums[j] = tmp[j-lhs]; 
    }
}

插入排序

void insertion_sort(vector<int>& nums, const int& n) {
    for(int i = 0; i < n; ++i) {
        for(int j = i; j > 0 && nums[j] < nums[j-1]; --j) {
            swap(nums[j-1], nums[j]);
        }
    }
}

冒泡排序

void bubble_sort(vector<int>& nums, const size_t& n) {
    for(size_t i = 0; i < n; ++i) {
        bool swapped = false;
        for(size_t j = 0; j < n - i - 1; ++j) {
            if(nums[j] > nums[j + 1]) {
                swap(nums[j], nums[j+1]);
                swapped = true;
            }
        }
        if(!swapped) return ; // 没有交换的话证明已经有序
    }
}

选择排序

void selection_sort(vector<int>& nums, const size_t& n) {
    for(size_t i = 0; i < n; ++i) {
        size_t min = i;
        for(size_t j = i + 1; j < n; ++j) {
            if(nums[j] < nums[min]) {
                min = j;
            }
        }
        swap(nums[i], nums[min]);
    }
}

堆排序

// 堆排序，大顶堆的实现
class BigHeap {
private:
    vector<int> heap;

public:
    void init() {
        heap.clear();
    }
    bool empty() {
        return heap.empty();
    }
    int top() {
        if(!heap.empty()) {
            return heap.front();
        }
        return -1;
    }

    void push(int x) {
        heap.emplace_back(std::move(x));
        swim(heap.size() - 1); // 插入元素后可能需要上浮
    }

    void pop() {
        heap[0] = heap.back();
        heap.pop_back();
        sink(0); // 通过交换弹出元素后可能需要下沉堆顶
    }

    vector<int> sort(vector<int>& nums) {
        for(const auto num : nums) {
            push(num);
        }

        vector<int> ans;
        while(!heap.empty()) {
            ans.push_back(top());
            pop();
        }
        return ans;
    }

    // 移出堆顶元素后需要将新的栈顶元素下沉
    void sink(int pos) {
        while(pos * 2 < heap.size()) {
            // 获取值更大的那个子节点的索引
            int i = pos * 2;
            if(heap[i] < heap[i+1]) {
                ++i;
            }
            if(heap[pos] >= heap[i]) {
                break;
            }

            swap(heap[pos], heap[i]);
            pos = i;
        }
    }

    // 在堆底添加新元素后需要将其上浮
    void swim(int pos) {
        while(pos > 1 && heap[pos/2] < heap[pos]) {
            swap(heap[pos], heap[pos/2]);
            pos = pos / 2;
        }
    }
};