经典算法实现之快速排序

算法

快速排序采用的是分治思想，即在一个无序的序列中选取一个任意的基准元素pivot，利用pivot将待排序的序列分成两部分，前面部分元素均小于或等于基准元素，后面部分均大于或等于基准元素，然后采用递归的方法分别对前后两部分重复上述操作，直到将无序序列排列成有序序列。

流程：

1. 首先设定一个分界值，通过该分界值将数组分成左右两部分。

2. 将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于分界值，而右边部分中各元素都大于或等于分界值。

3. 然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。
4. 重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。

实现

#include<algorithm>
#include<cassert>
#include<iostream>
#include<vector>

namespace quick_sort{
    template <typename T>
    int partition(std::vector<T> *arr, const int &low, const int &high) {
        T pivot = (*arr)[high];  // taking the last element as pivot
        int i = (low - 1);       // Index of smaller element

        for (int j = low; j < high; j++) {
            // If current element is smaller than or
            // equal to pivot
            if ((*arr)[j] <= pivot) {
                i++;  // increment index of smaller element
                std::swap((*arr)[i], (*arr)[j]);
            }
        }

        std::swap((*arr)[i + 1], (*arr)[high]);
        return (i + 1);
    }

    template <typename T>
    void quick_sort(std::vector<T> *arr, const int &low, const int &high) {
        if (low < high) {
            int p = partition(arr, low, high);

            quick_sort(arr, low, p - 1);
            quick_sort(arr, p + 1, high);
        }
    }

    template <typename T>
    std::vector<T> quick_sort(std::vector<T> arr, const int &low, const int &high) {
        if (low < high) {
            int p = partition(&arr, low, high);

            quick_sort(&arr, low, p - 1);
            quick_sort(&arr, p + 1, high);
        }
        return arr;
    }

    template <typename T>
    void show(const std::vector<T> &arr, const int &size) {
        for (int i = 0; i < size; i++) std::cout << arr[i] << " ";
        std::cout << "\n";
    }
}

int main(){
    std::vector<uint64_t> arr = {5, 3, 8, 12, 14, 16, 28, 96, 2, 5977};
    std::vector<uint64_t> arr_sorted = quick_sort::quick_sort(
        arr, 0, int(std::end(arr) - std::begin(arr)) - 1);

    assert(std::is_sorted(std::begin(arr_sorted), std::end(arr_sorted)));
    std::cout << "\n1st test: passed!\n";

    std::cout << "1st array:\n";
    ::quick_sort::show(arr_sorted, std::end(arr) - std::begin(arr));
    std::cout << std::endl;
}