1

我正在学习 D（我认为它会是比 C++ 更好的初学者友好语言），我决定给自己练习在 D 中实现通用快速排序。我的程序在对整数进行排序时运行良好，但它没有编译并在排序字符串时抛出一个奇怪的错误。

这是我的代码：

import std.stdio, std.algorithm;



T[] quickSort(T)(T[] input) {
   if (input.length <= 1) {return input;}
   ulong i = input.length/2;
   auto pivot = input[i];
   input = input.remove(i);
   T[] lesser = [];
   T[] greater = [];
   foreach (x; input) {
      if (x<=pivot)
      {
         lesser ~= x;
      }
      else 
      {
         greater ~=x;
      }
   }
   return (quickSort(lesser) ~ cast(T)pivot ~ quickSort(greater));
}
void main() {
   //Sort integers, this works fine
   //writeln(quickSort([1,4,3,2,5]));
   //Sort string, throws weird error
   writeln(quickSort("oidfaosnuidafpsbufiadsb"));
}

当我在一个字符串上运行它时，它会抛出这个错误：

/usr/share/dmd/src/phobos/std/algorithm.d(7397): Error: template std.algorithm.move does not match any function template declaration. Candidates are:
/usr/share/dmd/src/phobos/std/algorithm.d(1537):        std.algorithm.move(T)(ref T source, ref T target)
/usr/share/dmd/src/phobos/std/algorithm.d(1630):        std.algorithm.move(T)(ref T source)
/usr/share/dmd/src/phobos/std/algorithm.d(1537): Error: template std.algorithm.move cannot deduce template function from argument types !()(dchar, dchar)
/usr/share/dmd/src/phobos/std/algorithm.d(7405): Error: template std.algorithm.moveAll does not match any function template declaration. Candidates are:
/usr/share/dmd/src/phobos/std/algorithm.d(1786):        std.algorithm.moveAll(Range1, Range2)(Range1 src, Range2 tgt) if (isInputRange!(Range1) && isInputRange!(Range2) && is(typeof(move(src.front, tgt.front))))
/usr/share/dmd/src/phobos/std/algorithm.d(7405): Error: template std.algorithm.moveAll(Range1, Range2)(Range1 src, Range2 tgt) if (isInputRange!(Range1) && isInputRange!(Range2) && is(typeof(move(src.front, tgt.front)))) cannot deduce template function from argument types !()(string, string)
helloworld.d(9): Error: template instance std.algorithm.remove!(cast(SwapStrategy)2, string, ulong) error instantiating
helloworld.d(31):        instantiated from here: quickSort!(immutable(char))
helloworld.d(31): Error: template instance helloworld.quickSort!(immutable(char)) error instantiating
4

2 回答 2

3

问题是字符串是不可变的，所以remove不起作用（因为它操纵字符串）

您可以通过不删除也不在 concat 中插入枢轴来解决此问题：

auto pivot = input[i];
//input = input.remove(i); //<- remove this line
T[] lesser = [];
//...
return (quickSort(lesser) ~ quickSort(greater)); //<- remove cast(T)pivot ~

或通过传入一个副本：

writeln(quickSort("oidfaosnuidafpsbufiadsb".dup));
于 2013-09-27T00:03:27.577 回答
3

您必须在字符串后面加上“d”才能使其成为 utf-32，否则 remove 不会接受它。

writeln(quickSort("oidfaosnuidafpsbufiadsb"d.dup));
于 2013-09-27T01:54:11.380 回答