You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Background

快速排序的实现

Description

完成下述插入快速代码框架后提交，只需完成注释中的要求，无需输入输出

#include "QuickSort.h"

int QuickSort::partition(std::vector<int>& nums, int p, int q) {
    // 请在这里完成你的代码

    return 0;
}

void QuickSort::quick_sort(std::vector<int>& nums, int l, int r) {
    // 请在这里完成你的代码

}
void QuickSort::mysort(std::vector<int>& nums) {
    if(nums.size() == 0) 
      return;
    quick_sort(nums, 0, nums.size() - 1);
}

Samples

  提供一组样例用于自测

6
5 2 4 2 3 1

1 2 2 3 4 5

附QuickSort.h

#pragma once
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <functional>
using namespace std;

class MySort {
public:
	virtual void mysort(std::vector<int>& nums) = 0;
};

class QuickSort: public MySort {
public:
    // 通过快速排序对int数组nums进行升序排序
    // @param
    // nums: 完整的待排序队列，最终排序的结果应存放在nums中
    void mysort(std::vector<int>& nums);
    int partition(std::vector<int>& nums, int p, int q);
    void quick_sort(std::vector<int>& nums, int l, int r);
};