作者热门文章
- iOS/Objective-C 元类和类别
- objective-c - -1001 错误,当 NSURLSession 通过 httpproxy 和/etc/hosts
- java - 使用网络类获取 url 地址
- ios - 推送通知中不播放声音
我是在自考,想写mergesort,没有实际上网查任何代码,并且在一定时间段内完成。我被困在这一点上,我不能简单地理解我做错了什么,因为据我所知,合并排序是将字符串划分到字符串只有 1 个字符的位置,然后再将它们合并回一起。我在下面编写的代码尝试 做同样的事情。我想知道是我弄错了概念,还是只是我的实现?
string merge(string str1, string str2) {
string final = "";
int i = 0, j = 0;
bool fromStr1 = false;
while(true) {
if(str1[i] < str2[j]) {
final += str1[i];
i++;
if(i == str1.size()) {
break;
}
}
else {
final += str2[j];
j++;
if(j == str2.size()) {
break;
fromStr1 = true;
}
}
}
if(fromStr1) {
for(int t = i; t < str1.size(); t++) {
final += str1[t];
}
}
else {
for(int t = j; t < str2.size(); t++) {
final += str2[t];
}
}
return final;
}
string mergeSort(string str1, int start, int end) {
if(end - start == 1)
return str1;
else {
int pivot = (end - start) / 2;
string newStr1 = mergeSort(str1, start, pivot);
string newStr2 = mergeSort(str1, pivot + 1, end);
return merge(newStr1, newStr2);
}
}
最佳答案
注意变化:
#include <iostream>
#include <string>
using namespace std;
string merge(string str1, string str2) {
string final = "";
int i = 0, j = 0;
bool fromStr1 = false;
while (true) {
if (i >= (int)str1.size()) {
break;
}
if (j >= (int)str2.size()) {
fromStr1 = true; // changed the order of this with break!
break;
}
if (str1[i] < str2[j]) {
final += str1[i];
i++;
}
else {
final += str2[j];
j++;
}
}
if (fromStr1) {
for (int t = i; t < (int)str1.size(); t++) {
final += str1[t];
}
}
else {
for(int t = j; t < (int)str2.size(); t++) {
final += str2[t];
}
}
return final;
}
string mergeSort(string str1) {
int len = str1.size();
if (len <= 1)
return str1;
else {
string newStr1 = mergeSort(str1.substr(0, len / 2));
string newStr2 = mergeSort(str1.substr(len / 2, len - len / 2));
return merge(newStr1, newStr2);
}
}
int main()
{
cout << '"' << mergeSort("") << '"' << endl;
cout << '"' << mergeSort("a") << '"' << endl;
cout << '"' << mergeSort("ba") << '"' << endl;
cout << '"' << mergeSort("132") << '"' << endl;
cout << '"' << mergeSort("4321") << '"' << endl;
cout << '"' << mergeSort("54321") << '"' << endl;
return 0;
}
输出(ideone):
""
"a"
"ab"
"123"
"1234"
"12345"
关于C++:从头开始实现归并排序,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/16071617/
本文实例汇总了Java各种排序算法。分享给大家供大家参考,具体如下: 1. 冒泡排序: ?
1.冒泡排序 它重复地走访过要排序的元素列,依次比较两个相邻的元素,如果顺序错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换,也就是说该元素列已经排序完成。 算法步
前言 平时用惯了高级语言高级工具高级算法,难免对一些基础算法感到生疏。但最基础的排序算法中实则蕴含着相当丰富的优化思维,熟练运用可起到举一反三之功效。 选择排序 选择排序几乎是
我是一名优秀的程序员,十分优秀!