merge_sort使用向量 [英] merge_sort using vectors

问题描述

不知怎的，我使用向量实现了Merge排序，问题是：

它可以正常使用少于9个输入，但是有9个或更多输入它可以我不明白的东西，如下：

Hi,
Somehow I implemented Merge sort using vectors, the problem is:
It works correctly with less than 9 inputs, but with 9 or more inputs it does something which I don't understand, such as below:

Input:
5-4-3-2-1   ---   6-5-4-3-2-1   ---   9-8-7-6-5-4-3-2-1
Output:
1-2-3-4-5   ---   1-2-3-4-5-6   ---   1-2-3-4-5-7-6-8-9

以下是代码：

Here is the code:

#include "stdafx.h"
#include <vector>
#include <iostream>
using namespace std;
void showvector(vector<int> numbers){
	for (vector<int>::iterator i = numbers.begin(); i != numbers.end(); i++)
	{
		cout << *i;
		if (i != numbers.end() - 1)cout << " - ";
	}
}

vector<int> getvector(){
	vector<int> numbers(0);
	cout << "please enter you numbers :::\n''entering any characters but numbers is the end of entry''\n";
	int counter = 0;
	do{
		int newnumber = 0;
		cout << "element(" << counter << ") = ";
		counter++;		
		cin >> newnumber; getchar();
		if (cin.good())
			numbers.push_back(newnumber);
		if (cin.fail()){
			cout << "numbers are :";
			showvector(numbers);
		}
	} while (cin.good()); getchar();
	return numbers;
}

void mergesort(vector<int>& numbers);

vector<int> merge(vector<int>& one, vector<int>& two){
	cout << "\ncomparing vector one with "; showvector(one); cout << " element(s) with vector two with "; showvector(two); cout << " element(s)\n";
	vector<int>::iterator j = two.begin();
	vector<int>::iterator i;
	for (i = one.begin(); i != one.end(); i++){
		cout << "comparing " << *i << " with " << *j<<endl;
		if (*i > *j){
			cout << "exchanging " << *i << " with " << *j << endl;;
			int c = *i;
			*i = *j;
			*j = c;
			j++;
		}
	}
	if (j != two.end() && i==one.end())
		mergesort(two);	
	cout << "\npushing vector two with "; showvector(two); cout << " element(s) back to vector one with "; showvector(one); cout << " element(s)\n";	
	for (j=two.begin(); j != two.end();j++)
			one.push_back(*j);
	cout << "returning sorted vector as\n";
	showvector(one);
	return one;
}

void mergesort(vector<int>& numbers){
	if (numbers.size() > 1){		
		vector<int> halfone(numbers.begin(), numbers.begin() + numbers.size() / 2);
		mergesort(halfone);
		vector<int> halftwo(numbers.begin() + numbers.size() / 2, numbers.end());		
		mergesort(halftwo);
		numbers = merge(halfone, halftwo);
	}				
}

int main(){
	vector<int> numbers(getvector());	
	mergesort(numbers);
	cout << "\nnumbers are :";
	showvector(numbers);
	getchar();
}

推荐答案

您无法就地实施合并排序。如果交换或覆盖某些元素，则它不再是合并排序。在这种情况下，将一个元素从一个序列移动到另一个序列可能会破坏另一个序列（例如，它不再被命令）。

You can't implement merge sort "in place". If you swap or overwrite some of the elements, it isn't a merge sort anymore. In this case, moving an element from one sequence to other potentially breaks the other sequence (eg. it is no longer ordered).

static std::vector<int> merge(const std::vector<int>& one, const std::vector<int>& two)
{
	std::vector<int>::const_iterator i = one.begin();
	std::vector<int>::const_iterator j = two.begin();
	std::vector<int> result;
	while (i != one.end() && j != two.end())
	{
		if (*i < *j)
			result.push_back(*i++);
		else
			result.push_back(*j++);
	}
	while (i != one.end())
		result.push_back(*i++);
	while (j != two.end())
		result.push_back(*j++);

	return result;
}

请考虑将showvector的参数作为const引用。

Please consider making the parameter to showvector a const reference.

这篇关于merge_sort使用向量的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！