merge_sort使用的载体可以很好地低于9的输入 [英] merge_sort using vectors works well with less than 9 inputs
本文介绍了merge_sort使用的载体可以很好地低于9的输入的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
不知怎的，我实现了归并排序使用载体，问题是： 它的工作原理正确地小于9的投入，但与9个或多个输入它的东西我不理解，比如如下：
输入：
5-4-3-2-1 --- 6-5-4-3-2-1 --- 9-8-7-6-5-4-3-2-1
输出：
1-2-3-4-5 --- 1-2-3-4-5-6 --- 1-2-3-4-5-7-6-8-9
下面是code：
的#includestdafx.h中
＃包括＆LT;载体＆GT;
＃包括＆LT;的iostream＆GT;
使用名字空间std;
空隙showvector（矢量＆lt; INT＆GT;数字）{
对于（矢量＆lt; INT＆GT; ::迭代器I = numbers.begin（！）; I = numbers.end（）;我++）
{
COUT＆LT;＆LT; *一世;
如果（我= numbers.end（） - 1！）COUT＆LT;＆LT; - ;
}
}
矢量＆lt; int的＆GT; getvector（）{
矢量＆lt; int的＆GT;数字（0）;
COUT＆LT;＆LT; 请输入您的数字::: \ n''entering任何字符，但数字是进入''\ n的结束;
INT计数器= 0;
做{
INT newnumber = 0;
COUT＆LT;＆LT; 元素（＆其中;＆lt;反向＆其中;＆所述;）=;
反++;
CIN＆GT;＆GT; newnumber;的getchar（）;
如果（cin.good（））
numbers.push_back（newnumber）;
如果（cin.fail（））{
COUT＆LT;＆LT; 编号是 ：;
showvector（数字）;
}
}而（cin.good（））;的getchar（）;
返回的数字;
}
空隙归并（矢量＆lt; INT＆GT;＆安培;数字）;
矢量＆lt; int的＆GT;合并（矢量＆lt; INT＆GT;＆安培; 1，矢量＆lt; INT＆GT;＆安培; 2）{
COUT＆LT;＆LT; \ ncomparing载体之一，; showvector（之一）; COUT＆LT;＆LT; 元件（多个）与向量2使用; showvector（二）; COUT＆LT;＆LT; 元素（S）\ N的;
矢量＆lt; INT＆GT;：迭代J = two.begin（）;
矢量＆lt; INT＆GT;：迭代我;
对于（I = one.begin（）; I = one.end（！）;我++）{
COUT＆LT;＆LT; 比较＆LT;＆LT; * I＆LT;＆LT; 与＆LT;＆LT; * J＆LT;＆LT; ENDL;
如果（* I＆GT; * j）条{
COUT＆LT;＆LT; 交换＆LT;＆LT; * I＆LT;＆LT; 与＆LT;＆LT; * J＆LT;＆LT; ENDL ;;
INT C = *我;
* I = * D];
* J =℃;
J ++;
}
}
如果（J = two.end（）及！＆安培;我== one.end（））
归并（二）;
COUT＆LT;＆LT; \ npushing向量2用; showvector（二）; COUT＆LT;＆LT; 元件（多个）返回向量中的一个使用; showvector（之一）; COUT＆LT;＆LT; 元素（S）\ N的;
为（J = two.begin（！）; J = two.end（）; J ++）
one.push_back（* j）条;
COUT＆LT;＆LT; 回归排序向量作为\ N的;
showvector（之一）;
返回之一;
}
空隙归并（矢量＆lt; INT＆GT;＆安培;数字）{
如果（numbers.size（）→1）{
矢量＆lt; int的＆GT; halfone（numbers.begin（），numbers.begin（）+ numbers.size（）/ 2）;
归并（halfone）;
矢量＆lt; int的＆GT; halftwo（numbers.begin（）+ numbers.size（）/ 2，numbers.end（））;
归并（halftwo）;
数=合并（halfone，halftwo）;
}
}
诠释的main（）{
矢量＆lt; int的＆GT;号码（getvector（））;
归并（数字）;
COUT＆LT;＆LT; \ nnumbers是：;
showvector（数字）;
的getchar（）;
}
解决方案
下面是一对归并排序的例子，有所优化，也许有点超过你会从学生可以预期的。
顶部的例子是一个自上而下的合并排序。一个[]是进行排序，B []数组被一个临时数组大小相同一个[]。复制数据通过的一对交替根据递归的水平合并的方向递归函数避免。
底部的例子是一个自下而上的合并排序。注意排序阵列可以结束了在任何一个[]或b []。这可避免通过计算遍数和如果遍数是奇数，交换到位第一遍
这两个排序的例子使用两个数组和使用索引合并。主要的区别是自上而下使用递归重复分裂对索引，直到索引重新present 1运行大小，然后其启动实际合并过程，而底部向上跳过此步骤，只是用在运行开始关闭1大小和立即开始合并。大部分时间花在合并，因此相比它需要排序的总时间递归生成索引的额外的开销是很小的。
自顶向下的归并排序
为int * TopDownMergeSort（INT A []，INT B〔]，为size_t N）
{
如果（N 2）//如果大小＆LT; 2回
返回;
TopDownSplitMergeAtoA（A，B，0，n）的;
返回;
}
无效TopDownSplitMergeAtoA（INT A []，INT B〔]，为size_t LL，为size_t EE）
{
如果（（EE - LL）== 1）//如果size == 1回归
返回;
为size_t RR =（LL + EE）＆GT;大于1; //中点，右半开始
TopDownSplitMergeAtoB（A，B，LL，RR）;
TopDownSplitMergeAtoB（A，B，RR，EE）;
TopDownMerge（B，A，LL，RR，EE）; //合并B到A
}
无效TopDownSplitMergeAtoB（INT A []，INT B〔]，为size_t LL，为size_t EE）
{
如果（（EE - LL）== 1）{//如果size == 1份a到b
B〔11] = A [11];
返回;
}
为size_t RR =（LL + EE）＆GT;大于1; //中点，右半开始
TopDownSplitMergeAtoA（A，B，LL，RR）;
TopDownSplitMergeAtoA（A，B，RR，EE）;
TopDownMerge（A，B，LL，RR，EE）; //合并a到b
}
无效TopDownMerge（INT A []，INT B〔]，为size_t LL，为size_t RR，为size_t EE）
{
为size_tØ= 11; // B []指数
为size_t L = LL; //一个[]左手食指
为size_t R = RR; //一个[]右手食指
而（1）{//合并数据
如果（一个[1] = A [R]）{//如果一[1] = A [R]
B〔Ø++] =一个并[+] //复制[L]
如果（L＆LT; RR）//如果没有离开运行结束
继续; //继续（返回时）
而（R＆LT; EE）正确运行{//别的副本休息
B〔Ø++] = A [R ++];
}
打破; //和返回
}其他{//否则使用[1] GT; A [R]
B〔Ø++] = A [R ++]; //复制[R]
如果（R＆LT; EE）//如果没有正确的运行结束
继续; //继续（返回时）
而（L＆LT; RR）左运行{//别的副本休息
B〔Ø++] =一个并[+]
}
打破; //和返回
}
}
}
自下而上归并排序
为int * BottomUpMergeSort（INT A []，INT B〔]，为size_t N）
{
为（为size_t S = 1; S n种; S＆其中;＆其中; = 1）{// S =运行大小
为size_t ee值= 0; //初始化结束索引
而（ee值n种）{//合并对运行的
为size_t LL = EE; // LL =开始离开运行
为size_t RR = 11 + S; // RR =启动权运行
如果（RR GT; = N）{//如果只剩下运行
RR = N;
BottomUpCopy（A，B，LL，RR）; //复制左运行
打破; //传结束
}
EE = RR + S; // EE =正确的运行结束
如果（ee值将N）
EE = N;
BottomUpMerge（A，B，LL，RR，EE）;
}
的std ::交换（A，B）; //交换a和b的师生比
}
返回; //返回排序的数组
}
无效BottomUpCopy（INT A []，INT B〔]，为size_t LL，为size_t RR）
{
而（LL＆LT; RR）{//拷贝左的
B〔11] = A [11];
LL ++;
}
}
无效BottomUpMerge（INT A []，INT B〔]，为size_t LL，为size_t RR，为size_t EE）
{
为size_tØ= 11; // B []指数
为size_t L = LL; //一个[]左手食指
为size_t R = RR; //一个[]右手食指
而（1）{//合并数据
如果（一个[1] = A [R]）{//如果一[1] = A [R]
B〔Ø++] =一个并[+] //复制[L]
如果（L＆LT; RR）//如果没有离开运行结束
继续; //继续（返回时）
而（R＆LT; EE）正确运行{//别的副本休息
B〔Ø++] = A [R ++];
}
打破; //和返回
}其他{//否则使用[1] GT; A [R]
B〔Ø++] = A [R ++]; //复制[R]
如果（R＆LT; EE）//如果没有正确的运行结束
继续; //继续（返回时）
而（L＆LT; RR）左运行{//别的副本休息
B〔Ø++] =一个并[+]
}
打破; //和返回
}
}
}
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();
}
解决方案
Here is a pair of merge sort examples, somewhat optimized, and perhaps a bit more than what would be expected from a student.
The top example is a top down merge sort. a[] is the array to be sorted, b[] is a temp array the same size as a[]. Copying data is avoided via a pair of recursive functions that alternate the direction of the merge depending on the level of recursion.
The bottom example is a bottom up merge sort. Note the sorted array can end up in either a[] or b[]. This can be avoided by calculating the number of passes and if the number of passes is odd, swap in place for the first pass.
Both sort examples use two arrays and merge using indexes. The main difference is top down uses recursion to repeatedly split pairs of indexes until the indexes represent a run size of 1, where it then starts the actual merge process, while bottom up skips this step and just starts off with a run size of 1 and starts merging immediately. Most of the time is spent merging, so the extra overhead of recursively generating indexes is small compared to the total time it takes to sort.
top down merge sort
int * TopDownMergeSort(int a[], int b[], size_t n)
{
if(n < 2) // if size < 2 return
return a;
TopDownSplitMergeAtoA(a, b, 0, n);
return a;
}
void TopDownSplitMergeAtoA(int a[], int b[], size_t ll, size_t ee)
{
if((ee - ll) == 1) // if size == 1 return
return;
size_t rr = (ll + ee)>>1; // midpoint, start of right half
TopDownSplitMergeAtoB(a, b, ll, rr);
TopDownSplitMergeAtoB(a, b, rr, ee);
TopDownMerge(b, a, ll, rr, ee); // merge b to a
}
void TopDownSplitMergeAtoB(int a[], int b[], size_t ll, size_t ee)
{
if((ee - ll) == 1){ // if size == 1 copy a to b
b[ll] = a[ll];
return;
}
size_t rr = (ll + ee)>>1; // midpoint, start of right half
TopDownSplitMergeAtoA(a, b, ll, rr);
TopDownSplitMergeAtoA(a, b, rr, ee);
TopDownMerge(a, b, ll, rr, ee); // merge a to b
}
void TopDownMerge(int a[], int b[], size_t ll, size_t rr, size_t ee)
{
size_t o = ll; // b[] index
size_t l = ll; // a[] left index
size_t r = rr; // a[] right index
while(1){ // merge data
if(a[l] <= a[r]){ // if a[l] <= a[r]
b[o++] = a[l++]; // copy a[l]
if(l < rr) // if not end of left run
continue; // continue (back to while)
while(r < ee){ // else copy rest of right run
b[o++] = a[r++];
}
break; // and return
} else { // else a[l] > a[r]
b[o++] = a[r++]; // copy a[r]
if(r < ee) // if not end of right run
continue; // continue (back to while)
while(l < rr){ // else copy rest of left run
b[o++] = a[l++];
}
break; // and return
}
}
}
bottom up merge sort
int * BottomUpMergeSort(int a[], int b[], size_t n)
{
for(size_t s = 1; s < n; s <<= 1){ // s = run size
size_t ee = 0; // init end index
while(ee < n){ // merge pairs of runs
size_t ll = ee; // ll = start of left run
size_t rr = ll+s; // rr = start of right run
if(rr >= n){ // if only left run
rr = n;
BottomUpCopy(a, b, ll, rr); // copy left run
break; // end of pass
}
ee = rr+s; // ee = end of right run
if(ee > n)
ee = n;
BottomUpMerge(a, b, ll, rr, ee);
}
std::swap(a, b); // swap a and b ptrs
}
return a; // return sorted array
}
void BottomUpCopy(int a[], int b[], size_t ll, size_t rr)
{
while(ll < rr){ // copy left run
b[ll] = a[ll];
ll++;
}
}
void BottomUpMerge(int a[], int b[], size_t ll, size_t rr, size_t ee)
{
size_t o = ll; // b[] index
size_t l = ll; // a[] left index
size_t r = rr; // a[] right index
while(1){ // merge data
if(a[l] <= a[r]){ // if a[l] <= a[r]
b[o++] = a[l++]; // copy a[l]
if(l < rr) // if not end of left run
continue; // continue (back to while)
while(r < ee){ // else copy rest of right run
b[o++] = a[r++];
}
break; // and return
} else { // else a[l] > a[r]
b[o++] = a[r++]; // copy a[r]
if(r < ee) // if not end of right run
continue; // continue (back to while)
while(l < rr){ // else copy rest of left run
b[o++] = a[l++];
}
break; // and return
}
}
}
这篇关于merge_sort使用的载体可以很好地低于9的输入的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
查看全文
