我在提出一个工作就地合并排序时遇到了一些麻烦。有没有人有任何算法或技巧可以帮助我入门?
问问题
8364 次
2 回答
1
合并排序.cpp
#include "mergesort.h"
#include <limits>
#include <vector>
#include <iostream>
using namespace std;
void merge_sort(int *data, int start, int end){
if (start < end){
int middle = int((end + start) / 2);
merge_sort(data, start, middle);
merge_sort(data, middle+1, end);
merge(data, start, middle+1, end);
}
}
void merge(int *data, int start, int middle, int end){
int left[middle-start+1];
for (int l_cnt=0; l_cnt<middle-start; l_cnt++){
left[l_cnt] = data[start+l_cnt];
}
left[middle-start] = numeric_limits<int>::max();
int right[end-middle+2];
for (int r_cnt=0; r_cnt<end-middle+1; r_cnt++){
right[r_cnt] = data[middle+r_cnt];
}
right[end-middle+1] = numeric_limits<int>::max();
int i = 0;
int j = 0;
for (int k=start; k<=end; k++){
if (left[i] < right[j]){
data[k] = left[i];
i++;
}
else{
data[k] = right[j];
j++;
}
}
}
合并排序.h
#ifndef INSERTIONSORT_H_
#define INSERTIONSORT_H_
void merge_sort(int *data, int start, int end);
void merge(int *data, int start, int middle, int end);
#endif
和单元测试文件
#include "mergesort.h"
#include "gtest/gtest.h"
template<typename T, size_t size>
::testing::AssertionResult ArraysMatch(const T (&expected)[size],
const T (&actual)[size]){
for (size_t i(0); i < size; ++i){
if (expected[i] != actual[i]){
return ::testing::AssertionFailure() << "array[" << i
<< "] (" << actual[i] << ") != expected[" << i
<< "] (" << expected[i] << ")";
}
}
return ::testing::AssertionSuccess();
}
namespace{
class MergeSortTest : public ::testing::Test{
protected:
MergeSortTest() {}
virtual ~MergeSortTest() {}
virtual void SetUp() {}
virtual void TearDown() {}
};
TEST(MergeSortTest, MergeTwo){
int raw_array[] = {6,0,5,2,4,1,9,7};
merge(raw_array, 2, 3, 3);
int sorted_array[] = {6,0,2,5,4,1,9,7};
EXPECT_TRUE(ArraysMatch(sorted_array, raw_array));
}
TEST(MergeSortTest, MergeFive){
int raw_array[] = {6,0,2,5,1,4,9,7};
merge(raw_array, 2, 4, 6);
int sorted_array[] = {6,0,1,2,4,5,9,7};
EXPECT_TRUE(ArraysMatch(sorted_array, raw_array));
}
TEST(MergeSortTest, SortTwo){
int raw_array[] = {5, 2};
int sorted_array[] = {2, 5};
merge_sort(raw_array, 0, 1);
EXPECT_TRUE(ArraysMatch(sorted_array, raw_array));
}
TEST(MergeSortTest, SortThree){
int raw_array[] = {5, 2, 4};
int sorted_array[] = {2, 4, 5};
merge_sort(raw_array, 0, 2);
EXPECT_TRUE(ArraysMatch(sorted_array, raw_array));
}
TEST(MergeSortTest, Five){
int raw_array[] = {5, 2, 4, 1, 9};
int sorted_array[] = {1, 2, 4, 5, 9};
merge_sort(raw_array, 0, 4);
EXPECT_TRUE(ArraysMatch(sorted_array, raw_array));
}
}
int main(int argc, char **argv){
::testing::InitGoogleTest(&argc, argv);
return RUN_ALL_TESTS();
}
于 2012-04-28T06:17:32.963 回答
0
就地合并排序是关于使用限制大小的缓冲区进行合并排序。最后是如何将两个排序列表与小于结果的缓冲区合并。
STL 有一个就地合并排序的实现。
于 2012-04-28T09:07:26.283 回答