检查字符串是否已排序

我有一个简化的字符串"12345"已排序。该字符串可以包含数字 (0-9) 或字母 (a-z)。如果混合使用自然排序顺序。我需要一种方法来验证这是否属实。

尝试使用 linq 技术：

string items1 = "2349"; //sorted
string items2 = "2476"; //not sorted, 6<>7

bool sorted1 = Enumerable.SequenceEqual(items1.OrderBy(x => x), items1); //true
bool sorted2 = Enumerable.SequenceEqual(items2.OrderBy(x => x), items2); //false

但也可能存在降序排序。

那还有更好的办法吗

string items3 = "4321";
bool sorted3 = Enumerable.SequenceEqual(items3.OrderBy(x => x), items3) || Enumerable.SequenceEqual(items3.OrderByDescending(x => x), items3);

检查字符串是否已排序？也许有一些内置的解决方案？

你的解决方案很好而且非常可读。它的一个问题是它需要订购string 这是O(n * log(n)) https://en.wikipedia.org/wiki/Sorting_algorithm，这可以通过迭代来解决string而不对其进行排序。

例如：

var firstDifs = items1.Zip(items1.Skip(1), (x, y) => y - x);

This Linq第一个项目中每 2 个项目string一个数字来表示它们的差异，所以如果你有items1 = "1245"输出将是：

第一个差异：{1, 2, 1}

现在您需要做的就是验证这一点firstDifs是升序或降序：

bool firstSorted = firstDifs.All(x => x > 0) || firstDifs.All(x => x < 0); //true

Now:

• Skip https://msdn.microsoft.com/en-us/library/bb358985(v=vs.110).aspx is O(1)因为跳过 1 个单元格所需的操作量是 持续的。
• Zip https://msdn.microsoft.com/en-us/library/dd267698(v=vs.110).aspx is O(n).
• All https://msdn.microsoft.com/en-us/library/bb548541(v=vs.110).aspx is O(n).

所以整个解决方案是O(n).

Note that it will be more efficient with a simple loop, also if the first All https://msdn.microsoft.com/en-us/library/bb548541(v=vs.110).aspx has returned false because the 3487th item changes its direction (for example: 1234567891), the second All https://msdn.microsoft.com/en-us/library/bb548541(v=vs.110).aspx will run for no reason with the Zip https://msdn.microsoft.com/en-us/library/dd267698(v=vs.110).aspx running twice as well _{(Until where All https://msdn.microsoft.com/en-us/library/bb548541(v=vs.110).aspx require)} - since there are two iterations of All https://msdn.microsoft.com/en-us/library/bb548541(v=vs.110).aspx and Linq evaluates them lazily.