这是连接（里面包含课本，附加代码和题目），麻烦按照要求模板完成在linux跑，谢谢
链接: https://pan.baidu.com/s/1XS8wB-8vT0rOcKqU6iZpWw 提取码: 7i3x
下面是翻译，附加有原文，谢谢
学习成果：这项作业的目的是使用和比较各种 排序算法。 在本作业中，您将比较各种排序算法。您还将 修改算法，以便将Comparator类用于比较。你会 然后进一步尝试算法变化。 提供的代码文件： 1. Sort.h（第7章） 2. test_sorting_algorithms.cc 问题1（65分） ***步骤1 ***（10分） 您应该编写一个小的函数来验证集合是否已排序。 template <类型名可比较，类型名比较器> bool VerifyOrder（const vector <Comparable>＆input，Comparator less_than） 当且仅当输入按以下顺序排序时，上述函数才应返回true： 比较器。例如，为了检查整数向量（vector <int> input_vector）按从小到大的顺序排序，您需要调用： VerifyOrder（input_vector，less <int> {}）; 如果要检查向量是否从大到小排序，则需要调用 VerifyOrder（input_vector，更大的<int> {}）; 此函数应放在test_sorting_algorithms.cc中 2个 所有可交付成果均在文件末尾进行了描述。 接下来，您应该编写两个函数，一个函数生成一个随机向量，另一个函数 生成排序的向量。排序后的向量应生成一个递增或递增的向量 根据布尔的small_to_larger减小值。您将同时使用这两种方式 自己的测试目的。 功能签名应如下。 1）vector <int> GenerateRandomVector（size_t size_of_vector） 2）vector <int> GenerateSortedVector（size_t size_of_vector，布尔 small_to_larger） 接下来，编写一个函数来计算给定开始时间和停止时间的持续时间 纳秒。提示：看看在中提供给您的TestTiming函数 test_sorting_algorithms.cc： 功能签名应如下。 自动ComputeDuration（chrono :: high_resolution_clock :: time_point start_time， chrono :: high_resolution_clock :: time_point end_time） 这些函数应该放在test_sorting_algorithms.cc中 本文档末尾介绍了所有可交付成果。 ***步骤2 ***（55分） 现在，您将修改Sort.h中提供的几种排序算法。您将修改： heapsort，quicksort和mergesort。 您应该修改这些算法，以便它们各自使用比较器。 输入。 这些种类的签名应为： 模板<类型名可比，类型名比较器> void HeapSort（vector <Comparable>＆a，比较器less_than） 模板<类型名可比，类型名比较器> 无效的QuickSort（vector <Comparable>＆a，比较器less_than） 模板<类型名可比，类型名比较器> MergeSort（vector <Comparable>＆a，比较器less_than） 您将必须修改多个功能，辅助程序和包装器才能完全做到这一点 运行无误。 这些函数应修改并保留在Sort.h中 3 本文档末尾介绍了所有可交付成果。 ***步骤3 ***（点数将从步骤2中得出） 现在，完成了这两个步骤，您将继续进行测试。 现在，您应该在test_sorting_algorithms.cc中创建一个驱动程序，它将 使用不同的输入来测试每个修改后的排序。 该程序将按以下方式执行： ./test_sorting_algorithms <输入类型> <输入大小> <比较类型> 其中<input_type>可以是随机的，sorted_small_to_large或 sorted_large_to_small，<input_size>是输入的元素数，并且 <comparison_type>小于或大于。 例如，您应该能够运行 ./test_sorting_algorithms随机数减少20000 上面应该产生一个20000整数的随机向量，并应用所有三种算法 使用less <int> {}比较器。 您还可以运行： ./test_sorting_algorithms排序大10000 上面的代码将按此顺序产生包含1到10000的整数的向量，并且 将使用Greater <int> {}比较器测试这三种算法。 该驱动程序应在testSortingWrapper（）函数内部实现。 驱动程序输出的格式显示在文件底部。 注意：呈现的格式是应如何测试功能的示例。它服务 作为理解不同类别在运行时如何变化的良好基础 输入类型。实施此方法不会受到约束（或对方法的评分准确） 步骤，但这样做可以帮助您和我们验证工作的准确性。 （您仍然必须 创建一个驱动程序，其功能类似于所述驱动程序，但不会自动进行分级 格式，将对其进行手动查看。） 4 问题2（20分） 在这个问题中，您将实现快速排序算法的变体。你会 研究以下枢轴选择程序。 1. a）中位数三个（已在第2部分中实现） 2. b）中间枢轴（总是选择数组中的中间项） 3. c）第一个枢轴（始终选择数组中的第一个项目）尽管文件中已经实现了三位数的中值，但是您将使用它进行比较 在这个问题上更进一步。 以下两个快速排序实现，中间枢轴和第一个枢轴，应具有 具有以下签名的包装，然后调用完整的实现。 //中间枢轴包装器 模板<类型名可比，类型名比较器> 无效的QuickSort2（vector <Comparable>＆a，比较器less_than） //第一个枢轴包装器 模板<类型名可比，类型名比较器> void QuickSort3（vector <Comparable>＆a，比较器less_than） 注意：这些只是包装器，您必须编写实际的quicksort 这些函数调用的另一个函数中的功能（类似于原始quicksort 假如）。 为了测试这些功能，您将添加到驱动程序的输出中 在步骤3中进行了说明。完整格式如下所示。 可交付成果：您应提交以下文件： ●README.SORTING文件 ●Sort.h（已修改） ○所有种类的修改和添加都应保留在此文件中。 ●test_sorting_algorithms.cc（已修改） ○VerifyOrder（） ○GenerateRandomVector（） ○GenerateSortedVector（） ○ComputeDuration（） ○sortTestingWrapper（） 注意：大量的这项作业将手动检查和评分。我们将奔跑 您在自动分级机中的排序和实现的功能，但排序修改将是 手动验证。 5 驱动程式格式化 完整的驱动程序格式应如下：（示例显示为函数调用 ./test_sorting_algorithms随机数少20000）注意：数字输出 “ Verified”旁边是函数VerifyOrder（）的布尔输出。如果说 值为0，您的排序未按预期工作。 运行排序算法：随机数减少20000 堆排序 运行时：<X> ns 已验证：1 合并排序 运行时：<X> ns 已验证：1 快速排序 运行时：<X> ns 已验证：1 测试Quicksort Pivot实施 中位数三 运行时：<X> ns 已验证：1 中间 运行时：<X> ns 已验证：1 第一的 运行时：<X> ns 已验证：1
// main.cpp
#include "Sort.h"
#include <chrono>
#include <iostream>
#include <fstream>
#include <functional>
#include <string>
#include <vector>
#include <algorithm>
//////////////////////
// the limits of type
#include <limits>
namespace tools {
bool less(int left, int right){
return left <= right;
}
bool greater(int left, int right){
return left >= right;
}
}
namespace judge{
bool less(const vector<int> &input){
int judge = numeric_limits<int>::min();
for (size_t i = 0; i < input.size(); i++){
if (judge <= input[i]){
judge = input[i];
continue;
}
else{
return false;
}
}
return true;
}
bool greater(const vector<int> &input){
int judge = numeric_limits<int>::max();
for (size_t i = 0; i < input.size(); i++){
if (judge >= input[i]){
judge = input[i];
continue;
}
else{
return false;
}
}
return true;
}
}
using namespace std;
// Test function that shows how you can time a piece of code.
// Just times a simple loop.
void TestingTiming() {
cout << "Testing Timing" << endl;
const auto begin = chrono::high_resolution_clock::now();
// Time this piece of code.
int sum = 0;
for (int i = 1; i < 10000; ++i) sum++;
// End of piece of code to time.
const auto end = chrono::high_resolution_clock::now();
cout << chrono::duration_cast<chrono::nanoseconds>(end - begin).count() << "ns" << endl;
cout << chrono::duration_cast<chrono::milliseconds>(end - begin).count() << "ms" << endl;
}
// Generates and returns random vector of size @size_of_vector.
vector<int> GenerateRandomVector(size_t size_of_vector) {
// Use rand() to generate random integer
// Add code
srand(time(0));
vector<int> res;
for (size_t i = 0; i < size_of_vector; i++){
res.push_back(rand() % numeric_limits < int > ::max() + 1);
}
return res;
}
// Generate and returns sorted vector of size @size_of_vector
// If smaller_to_larger is true, returns vector sorted from small to large
// Otherwise returns vector sorted from large to small
vector<int> GenerateSortedVector(size_t size_of_vector, bool smaller_to_larger) {
// Add code
vector<int> res;
if (smaller_to_larger){
for (size_t i = 0; i < size_of_vector; i++){
res.push_back(i);
}
}
else{
for (size_t i = size_of_vector; i > 0; i--){
res.push_back(i);
}
}
return res;
}
// Verifies that a vector is sorted given a comparator
template <typename Comparable, typename Comparator>
bool VerifyOrder(const vector<Comparable> &input, Comparator less_than) {
// Add code
// to judge if the input is order by asc or desc
bool flag = less_than(input);
cout << "Verified:" << flag << endl;
return flag;
}
// Computes duration given a start time and a stop time in nano seconds
long long ComputeDuration(chrono::high_resolution_clock::time_point start_time, chrono::high_resolution_clock::time_point end_time) {
// Add code
long long res = 0;
res = chrono::duration_cast<chrono::nanoseconds>(end_time - start_time).count();
return res;
}
// Wrapper function to test the different sorting algorithms
int testSortingWrapper(int argc, char **argv) {
//const string input_type = string(argv[1]);
//const int input_size = stoi(string(argv[2]));
//const string comparison_type = string(argv[3]);
string input_type = "random";
int input_size = stoi("25");
string comparison_type = "less";
if (input_type != "random" && input_type != "sorted_small_to_large" && input_type != "sorted_large_to_small") {
cout << "Invalid input type" << endl;
return 0;
}
if (input_size <= 0) {
cout << "Invalid size" << endl;
return 0;
}
if (comparison_type != "less" && comparison_type != "greater") {
cout << "Invalid comparison type" << endl;
return 0;
}
// This block of code to be removed for your final submission.
// removed
// TestingTiming();
//sort();
cout << "Running sorting algorithms: " << input_type << " " << input_size << " numbers " << comparison_type << endl;
vector<int> input_vector;
if (input_type == "random") {
// Generate random vector
input_vector = GenerateRandomVector(input_size);
}
else {
// Generate sorted vector.
if (input_type == "sorted_small_to_large"){
input_vector = GenerateSortedVector(input_size, true);
}
else{
input_vector = GenerateSortedVector(input_size, false);
}
}
// Call quicksort / heapsort / mergesort using appropriate input.
// ...
// if comparison type is "less" then call
// MergeSort(input_vector, less<int>{})
// otherwise call
// MergeSort(input_vector, greater<int>{})
// ...
if (comparison_type == "less"){
cout << "HeapSort" << endl;
auto begin = chrono::high_resolution_clock::now();
// Time this piece of code.
heapsort(input_vector, tools::less);
// End of piece of code to time.
auto end = chrono::high_resolution_clock::now();
VerifyOrder(input_vector, judge::less);
cout << "Runtime: <" << ComputeDuration(begin, end) << "> ns" << endl;
cout << "MergeSort" << endl;
begin = chrono::high_resolution_clock::now();
// Time this piece of code.
mergeSort(input_vector, tools::less);
VerifyOrder(input_vector, judge::less);
// End of piece of code to time.
end = chrono::high_resolution_clock::now();
cout << "Runtime: <" << ComputeDuration(begin, end) << "> ns" << endl;
cout << "QuickSort" << endl;
begin = chrono::high_resolution_clock::now();
// Time this piece of code.
quicksort(input_vector, tools::less);
VerifyOrder(input_vector, judge::less);
// End of piece of code to time.
end = chrono::high_resolution_clock::now();
cout << "Runtime: <" << ComputeDuration(begin, end) << "> ns" << endl;
input_vector = GenerateSortedVector(input_size, true);
cout << "QuickSort2" << endl;
begin = chrono::high_resolution_clock::now();
// Time this piece of code.
quickSort2(input_vector, tools::less);
VerifyOrder(input_vector, judge::less);
// End of piece of code to time.
end = chrono::high_resolution_clock::now();
cout << "Runtime: <" << ComputeDuration(begin, end) << "> ns" << endl;
input_vector = GenerateSortedVector(input_size, true);
cout << "QuickSort3" << endl;
begin = chrono::high_resolution_clock::now();
// Time this piece of code.
quicksort3(input_vector, tools::less);
VerifyOrder(input_vector, judge::less);
// End of piece of code to time.
end = chrono::high_resolution_clock::now();
cout << "Runtime: <" << ComputeDuration(begin, end) << "> ns" << endl;
}else{
cout << "HeapSort" << endl << endl;;
auto begin = chrono::high_resolution_clock::now();
// Time this piece of code.
heapsort(input_vector, tools::greater);
VerifyOrder(input_vector, judge::greater);
// End of piece of code to time.
auto end = chrono::high_resolution_clock::now();
cout << "Runtime: <" << ComputeDuration(begin, end) << "> ns" << endl;
cout << "MergeSort" << endl << endl;;
begin = chrono::high_resolution_clock::now();
// Time this piece of code.
mergeSort(input_vector, tools::greater);
VerifyOrder(input_vector, judge::greater);
// End of piece of code to time.
end = chrono::high_resolution_clock::now();
cout << "Runtime: <" << ComputeDuration(begin, end) << "> ns" << endl;
cout << "QuickSort" << endl << endl;
begin = chrono::high_resolution_clock::now();
// Time this piece of code.
quicksort(input_vector, tools::greater);
VerifyOrder(input_vector, judge::greater);
// End of piece of code to time.
end = chrono::high_resolution_clock::now();
cout << "Runtime: <" << ComputeDuration(begin, end) << "> ns" << endl;
input_vector = GenerateSortedVector(input_size, false);
cout << "QuickSort2" << endl;
begin = chrono::high_resolution_clock::now();
// Time this piece of code.
quickSort2(input_vector, tools::less);
VerifyOrder(input_vector, judge::less);
// End of piece of code to time.
end = chrono::high_resolution_clock::now();
cout << "Runtime: <" << ComputeDuration(begin, end) << "> ns" << endl;
input_vector = GenerateSortedVector(input_size, false);
cout << "QuickSort3" << endl;
begin = chrono::high_resolution_clock::now();
// Time this piece of code.
quicksort3(input_vector, tools::less);
VerifyOrder(input_vector, judge::less);
// End of piece of code to time.
end = chrono::high_resolution_clock::now();
cout << "Runtime: <" << ComputeDuration(begin, end) << "> ns" << endl;
}
// Call quicksort with median of three as pivot / middle as pivot / first as pivot using appropriate input.
// ...
// if comparison type is "less" then call
// QuickSort(input_vector, less<int>{})
// otherwise call
// QuickSort(input_vector, greater<int>{})
// ...
return 0;
}
// Do not change anything below
int main(int argc, char **argv) {
if (argc != 4) {
cout << "Usage: " << argv[0] << "<input_type> <input_size> <comparison_type>" << endl;
return 0;
}
testSortingWrapper(argc, argv);
return 0;
}
//int main(int argc) {
// /*if (argc != 4) {
// cout << "Usage: " << argv[0] << "<input_type> <input_size> <comparison_type>" << endl;
// return 0;
// }*/
// testSortingWrapper(argc, NULL);
// return 0;
//}
// sort.h
#ifndef SORT_H
#define SORT_H
/**
* Several sorting routines.
* Arrays are rearranged with smallest item first.
*/
#include <vector>
#include <functional>
using namespace std;
/**
* Simple insertion sort.
*/
template <typename Comparable, typename Comparator>
void insertionSort(vector<Comparable> & a, Comparator less_than)
{
for (int p = 1; p < a.size(); ++p)
{
Comparable tmp = std::move(a[p]);
int j;
for (j = p; j > 0 && less_than(tmp,a[j - 1]); --j)
a[j] = std::move(a[j - 1]);
a[j] = std::move(tmp);
}
}
/**
* Internal insertion sort routine for subarrays
* that is used by quicksort.
* a is an array of Comparable items.
* left is the left-most index of the subarray.
* right is the right-most index of the subarray.
*/
template <typename Comparable, typename Comparator>
void insertionSort(vector<Comparable> & a, int left, int right, Comparator less_than)
{
for (int p = left + 1; p <= right; ++p)
{
Comparable tmp = std::move(a[p]);
int j;
for (j = p; j > left && less_than(tmp, a[j - 1]); --j)
a[j] = std::move(a[j - 1]);
a[j] = std::move(tmp);
}
}
/**
* Shellsort, using Shell's (poor) increments.
*/
template <typename Comparable>
void shellsort(vector<Comparable> & a)
{
for (int gap = a.size() / 2; gap > 0; gap /= 2)
for (int i = gap; i < a.size(); ++i)
{
Comparable tmp = std::move(a[i]);
int j = i;
for (; j >= gap && tmp < a[j - gap]; j -= gap)
a[j] = std::move(a[j - gap]);
a[j] = std::move(tmp);
}
}
/**
* Standard heapsort.
*/
template <typename Comparable, typename Comparator>
void heapsort(vector<Comparable> & a, Comparator less_than)
{
for (int i = a.size() / 2 - 1; i >= 0; --i) /* buildHeap */
percDown(a, i, a.size(), less_than);
for (int j = a.size() - 1; j > 0; --j)
{
std::swap(a[0], a[j]); /* deleteMax */
percDown(a, 0, j, less_than);
}
}
/**
* Internal method for heapsort.
* i is the index of an item in the heap.
* Returns the index of the left child.
*/
inline int leftChild(int i)
{
return 2 * i + 1;
}
/**
* Internal method for heapsort that is used in
* deleteMax and buildHeap.
* i is the position from which to percolate down.
* n is the logical size of the binary heap.
*/
template <typename Comparable, typename Comparator>
void percDown(vector<Comparable> & a, int i, int n, Comparator less_than)
{
int child;
Comparable tmp;
for (tmp = std::move(a[i]); leftChild(i) < n; i = child)
{
child = leftChild(i);
if (child != n - 1 && less_than(a[child] , a[child + 1]))
++child;
if (less_than(tmp , a[child]))
a[i] = std::move(a[child]);
else
break;
}
a[i] = std::move(tmp);
}
/**
* Internal method that makes recursive calls.
* a is an array of Comparable items.
* tmpArray is an array to place the merged result.
* left is the left-most index of the subarray.
* right is the right-most index of the subarray.
*/
template <typename Comparable, typename Comparator>
void mergeSort(vector<Comparable> & a,
vector<Comparable> & tmpArray, int left, int right, Comparator less_than)
{
if (left < right)
{
int center = (left + right) / 2;
mergeSort(a, tmpArray, left, center, less_than);
mergeSort(a, tmpArray, center + 1, right, less_than);
merge(a, tmpArray, left, center + 1, right, less_than);
}
}
/**
* Mergesort algorithm (driver).
*/
template <typename Comparable, typename Comparator>
void mergeSort(vector<Comparable> & a, Comparator less_than)
{
vector<Comparable> tmpArray(a.size());
mergeSort(a, tmpArray, 0, a.size() - 1, less_than);
}
/**
* Internal method that merges two sorted halves of a subarray.
* a is an array of Comparable items.
* tmpArray is an array to place the merged result.
* leftPos is the left-most index of the subarray.
* rightPos is the index of the start of the second half.
* rightEnd is the right-most index of the subarray.
*/
template <typename Comparable, typename Comparator>
void merge(vector<Comparable> & a, vector<Comparable> & tmpArray,
int leftPos, int rightPos, int rightEnd, Comparator less_than)
{
int leftEnd = rightPos - 1;
int tmpPos = leftPos;
int numElements = rightEnd - leftPos + 1;
// Main loop
while (leftPos <= leftEnd && rightPos <= rightEnd)
/////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////
if (less_than(a[leftPos], a[rightPos]))
tmpArray[tmpPos++] = std::move(a[leftPos++]);
else
tmpArray[tmpPos++] = std::move(a[rightPos++]);
while (leftPos <= leftEnd) // Copy rest of first half
tmpArray[tmpPos++] = std::move(a[leftPos++]);
while (rightPos <= rightEnd) // Copy rest of right half
tmpArray[tmpPos++] = std::move(a[rightPos++]);
// Copy tmpArray back
for (int i = 0; i < numElements; ++i, --rightEnd)
a[rightEnd] = std::move(tmpArray[rightEnd]);
}
/**
* Return median of left, center, and right.
* Order these and hide the pivot.
*/
template <typename Comparable, typename Comparator>
const Comparable & median3(vector<Comparable> & a, int left, int right, Comparator less_than)
{
int center = (left + right) / 2;
if (less_than(a[center], a[left]))
std::swap(a[left], a[center]);
if (less_than(a[right], a[left]))
std::swap(a[left], a[right]);
if (less_than(a[right], a[center]))
std::swap(a[center], a[right]);
// Place pivot at position right - 1
std::swap(a[center], a[right - 1]);
return a[right - 1];
}
//template <typename Comparable, typename Comparator>
// partition the array using last element as pivot
//int partition(vector<Comparable> & a, int left, int right, Comparator less_than)
//{
// int pivot = a[right]; // pivot
// int i = (left - 1);
//
// for (int j = left; j <= right - 1; j++)
// {
// //if current element is smaller than pivot, increment the low element
// //swap elements at i and j
// if (less_than(a[j], pivot))
// {
// i++; // increment index of smaller element
// std::swap(a[i], a[j]);
// }
// }
// std::swap(a[i + 1], a[right]);
// return (i + 1);
//}
template <typename Comparable, typename Comparator>
// partition the array using first element as pivot
int partition(vector<Comparable> & a, int left, int right, Comparator less_than)
{
int pivot = a[left]; // pivot
int i = left + 1;
for (int j = left + 1; j <= right ; j++)
{
//if current element is smaller than pivot, increment the low element
//swap elements at i and j
if (less_than(a[j], pivot))
{
i++; // increment index of smaller element
std::swap(a[i], a[j]);
}
}
std::swap(a[i - 1], a[left]);
return (i - 1);
}
template <typename Comparable, typename Comparator>
//quicksort algorithm
void quickSort2(vector<Comparable> & a, int left, int right, Comparator less_than)
{
if (left < right)
{
//partition the array
int pivot = partition(a, left, right, less_than);
//sort the sub arrays independently
quickSort2(a, left, pivot - 1, less_than);
quickSort2(a, pivot + 1, right, less_than);
}
}
template <typename Comparable, typename Comparator>
void quickSort2(vector<Comparable> & a, Comparator less_than)
{
quickSort2(a, 0, a.size() - 1, less_than);
}
template <typename Comparable, typename Comparator>
void quicksort3(vector<Comparable> & a, Comparator less_than)
{
quicksort3(a, 0, a.size() - 1, less_than);
}
template <typename Comparable, typename Comparator>
void quicksort3(vector<Comparable> & a, int left, int right, Comparator less_than)
{
if (left + 10 <= right)
{
const Comparable & pivot = median3(a, left, right, less_than);
// Begin partitioning
int i = left, j = right - 1;
for (;;)
{
while (less_than(a[++i], pivot)) {}
while (less_than(pivot, a[--j])) {}
if (i < j)
std::swap(a[i], a[j]);
else
break;
}
std::swap(a[i], a[right - 1]); // Restore pivot
quicksort3(a, left, i - 1, less_than); // Sort small elements
quicksort3(a, i + 1, right, less_than); // Sort large elements
}
else // Do an insertion sort on the subarray
insertionSort(a, left, right, less_than);
}
/**
* Internal quicksort method that makes recursive calls.
* Uses median-of-three partitioning and a cutoff of 10.
* a is an array of Comparable items.
* left is the left-most index of the subarray.
* right is the right-most index of the subarray.
*/
template <typename Comparable, typename Comparator>
void quicksort(vector<Comparable> & a, int left, int right, Comparator less_than)
{
if (left + 10 <= right)
{
const Comparable & pivot = median3(a, left, right, less_than);
// Begin partitioning
int i = left, j = right - 1;
for (;;)
{
while (less_than(a[++i], pivot)) {}
while (less_than(pivot, a[--j])) {}
if (i < j)
std::swap(a[i], a[j]);
else
break;
}
std::swap(a[i], a[right - 1]); // Restore pivot
quicksort(a, left, i - 1, less_than); // Sort small elements
quicksort(a, i + 1, right, less_than); // Sort large elements
}
else // Do an insertion sort on the subarray
insertionSort(a, left, right,less_than);
}
/**
* Quicksort algorithm (driver).
*/
template <typename Comparable, typename Comparator>
void quicksort2(vector<Comparable> & a, Comparator less_than)
{
quicksort2(a, 0, a.size() - 1, less_than);
}
/**
* Quicksort algorithm (driver).
*/
template <typename Comparable, typename Comparator>
void quicksort(vector<Comparable> & a, Comparator less_than)
{
quicksort(a, 0, a.size() - 1, less_than);
}
/**
* Internal selection method that makes recursive calls.
* Uses median-of-three partitioning and a cutoff of 10.
* Places the kth smallest item in a[k-1].
* a is an array of Comparable items.
* left is the left-most index of the subarray.
* right is the right-most index of the subarray.
* k is the desired rank (1 is minimum) in the entire array.
*/
template <typename Comparable>
void quickSelect(vector<Comparable> & a, int left, int right, int k)
{
if (left + 10 <= right)
{
const Comparable & pivot = median3(a, left, right);
// Begin partitioning
int i = left, j = right - 1;
for (;;)
{
while (a[++i] < pivot) {}
while (pivot < a[--j]) {}
if (i < j)
std::swap(a[i], a[j]);
else
break;
}
std::swap(a[i], a[right - 1]); // Restore pivot
// Recurse; only this part changes
if (k <= i)
quickSelect(a, left, i - 1, k);
else if (k > i + 1)
quickSelect(a, i + 1, right, k);
}
else // Do an insertion sort on the subarray
insertionSort(a, left, right);
}
/**
* Quick selection algorithm.
* Places the kth smallest item in a[k-1].
* a is an array of Comparable items.
* k is the desired rank (1 is minimum) in the entire array.
*/
template <typename Comparable>
void quickSelect(vector<Comparable> & a, int k)
{
quickSelect(a, 0, a.size() - 1, k);
}
template <typename Comparable>
void SORT(vector<Comparable> & items)
{
if (items.size() > 1)
{
vector<Comparable> smaller;
vector<Comparable> same;
vector<Comparable> larger;
auto chosenItem = items[items.size() / 2];
for (auto & i : items)
{
if (i < chosenItem)
smaller.push_back(std::move(i));
else if (chosenItem < i)
larger.push_back(std::move(i));
else
same.push_back(std::move(i));
}
SORT(smaller); // Recursive call!
SORT(larger); // Recursive call!
std::move(begin(smaller), end(smaller), begin(items));
std::move(begin(same), end(same), begin(items) + smaller.size());
std::move(begin(larger), end(larger), end(items) - larger.size());
/*
items.clear( );
items.insert( end( items ), begin( smaller ), end( smaller ) );
items.insert( end( items ), begin( same ), end( same ) );
items.insert( end( items ), begin( larger ), end( larger ) );
*/
}
}
/*
* This is the more public version of insertion sort.
* It requires a pair of iterators and a comparison
* function object.
*/
template <typename RandomIterator, typename Comparator>
void insertionSort(const RandomIterator & begin,
const RandomIterator & end,
Comparator lessThan)
{
if (begin == end)
return;
RandomIterator j;
for (RandomIterator p = begin + 1; p != end; ++p)
{
auto tmp = std::move(*p);
for (j = p; j != begin && lessThan(tmp, *(j - 1)); --j)
*j = std::move(*(j - 1));
*j = std::move(tmp);
}
}
/*
* The two-parameter version calls the three parameter version, using C++11 decltype
*/
template <typename RandomIterator>
void insertionSort(const RandomIterator & begin,
const RandomIterator & end)
{
insertionSort(begin, end, less<decltype(*begin)>{ });
}
#endif
https://blog.csdn.net/stary_yan/article/details/51198663
可以参考一下，看看有没有帮助~