QuickSort-快速排序

---

具体C++代码如下

#include <iostream>
#include <vector> 
#include <cstdlib>
#include <ctime>
#include <sstream>
#define random(a,b) (rand()%(b-a)+a)
using namespace std;

//vector作为局部变量是不被允许返回的, 当需要处理一个vector并得到处理结果, 必须外部输入一个vector引用。
bool intRandomRange(vector<int>& res, int min, int max, int count) {
    srand((int)time(0));
    for (int i = 0; i < count; i++)
    {
        res.push_back((int)random(min, max));
    }
    return true;
}
//使用stringstream转换生成string, 用于测试
string vector2string(vector<int>& vec) {
    stringstream ss;
    for (int i = 0; i < vec.size(); ++i)
    {
        if (i != 0)
            ss << ",";
        ss << vec[i];
    }
    return ss.str();
}
bool contrastByOrder(int left, int right, bool bigger, bool equal) {
    if (equal)
        if (bigger)//升序比较
            return left >= right;
        else
            return left <= right;
    else
        if (bigger)
            return left > right;
        else
            return left < right;
    
}

//递归式快排_主体
int quickSort_main(vector<int>& vec, int left, int right, bool ascending) {
    int mid = left++;
    while (left <= right) {
        while (left <= right && contrastByOrder(vec[right], vec[mid], ascending, false))// vec[mid] < vec[right]|ascending = true;
            right--;
        if (left <= right) {
            swap(vec[mid], vec[right]);
            mid = right;//复位, 确保该轮中对比的数据仍不变
        }
        while (left <= right && contrastByOrder(vec[mid], vec[left], ascending, true))// vec[left] <= vec[mid]|ascending = true;
            left++;
        if (left <= right) {
            swap(vec[mid], vec[left]);
            mid = left;//复位
        }
    }
    return mid;
}
//递归式快排_递归体
void quickSort_Rp(vector<int>& vec, int left, int right, bool ascending) {
    if (left > right)//递归出口
        return;
    int mid = quickSort_main(vec, left, right, ascending);
    quickSort_Rp(vec, left, mid - 1, ascending);
    quickSort_Rp(vec, mid + 1, right, ascending);
}
//递归式快速排序_入口
bool quickSort(vector<int>& vec, bool ascending) {
    int count = vec.size();
    if (count <= 1)//无需排序的状态
        return false;
    quickSort_Rp(vec, 0, vec.size() - 1, ascending);
    return true;
}

int main()
{
    vector<int> test;
    intRandomRange(test, 0, 10, 10);
    cout << vector2string(test) << endl;
    if (quickSort(test, false))
        cout << vector2string(test) << endl;
    else
        cout << "No Need to Quick Sort" << endl;
}