weixin_47375012
weixin_47375012
采纳率80%
2021-04-19 09:33

c++模板排序问题项目,求大佬怎么搞

50
已结题

这是连接(里面包含课本,附加代码和题目),麻烦按照要求模板完成在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

  • 点赞
  • 收藏
  • 复制链接分享

3条回答

  • bosaidongmomo bosaidongmomo 13天前
    // 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
    
    点赞 评论 复制链接分享
  • VisualEleven Eleven 16天前

    https://blog.csdn.net/stary_yan/article/details/51198663
    可以参考一下,看看有没有帮助~

    点赞 评论 复制链接分享
  • soar3033 soar3033 17天前

    建议下次你不要这种没有换行的直接粘贴,这样字都黏在一起,看着就头大,不利于有人回答你的问题

    点赞 评论 复制链接分享

相关推荐