作者热门文章
- iOS/Objective-C 元类和类别
- objective-c - -1001 错误,当 NSURLSession 通过 httpproxy 和/etc/hosts
- java - 使用网络类获取 url 地址
- ios - 推送通知中不播放声音
我在想出一个有效的就地合并排序时遇到了一些麻烦。有没有人有任何算法或提示可以帮助我入门?
最佳答案
合并排序.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();
}
关于c++ - 就地归并排序,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/10360963/
本文实例汇总了Java各种排序算法。分享给大家供大家参考,具体如下: 1. 冒泡排序: ?
1.冒泡排序 它重复地走访过要排序的元素列,依次比较两个相邻的元素,如果顺序错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换,也就是说该元素列已经排序完成。 算法步
前言 平时用惯了高级语言高级工具高级算法,难免对一些基础算法感到生疏。但最基础的排序算法中实则蕴含着相当丰富的优化思维,熟练运用可起到举一反三之功效。 选择排序 选择排序几乎是
我是一名优秀的程序员,十分优秀!