如何对字符串数组进行排序？

我有一个用逗号分隔的输入单词列表.我想按字母和长度对这些单词进行排序.如何在不使用内置排序功能的情况下执行此操作？

好问题!!排序可能是作为一名崭露头角的计算机科学家学习的最重要的概念.

实际上有很多不同的算法可以对列表进行排序.

当你打破所有这些算法时,最基本的操作是比较列表中的两个项目,定义它们的"自然顺序".

例如,为了对整数列表进行排序,我需要一个函数告诉我,给定任意两个整数X和Y,X是否小于,等于或大于Y.

对于你的字符串,你需要相同的东西:一个函数,它告诉你哪些字符串具有"较小"或"较大"值,或者它们是否相等.

传统上,这些"比较器"函数看起来像这样:

int CompareStrings(String a, String b) {
   if (a < b)
      return -1;
   else if (a > b)
      return 1;
   else
      return 0;
}

我遗漏了一些细节(例如,你如何计算a是否小于或大于b？线索:迭代字符),但这是任何比较函数的基本框架.如果第一个元素较小,则返回小于零的值;如果第一个元素较大,则返回大于零的值,如果元素具有相等的值,则返回零.

但这与排序有什么关系？

排序路由将为列表中的元素对调用该函数,使用函数的结果来确定如何将项重新排列为排序列表.比较函数定义"自然顺序","排序算法"定义用于调用和响应比较函数结果的逻辑.

每个算法都像一个大图片策略,用于保证任何输入都能正确排序.以下是您可能想要了解的一些算法:

冒泡排序:

遍历列表,调用所有相邻元素对的比较函数.每当得到大于零的结果(意味着第一个元素大于第二个元素)时,交换这两个值.然后继续前进到下一对.当你到达列表的末尾时,如果你不必交换任何一对,那么恭喜,列表已经排序了!如果您必须执行任何交换,请返回到开头并重新开始.重复此过程,直到没有更多交换.

注意:这通常不是对列表进行排序的非常有效的方法,因为在最坏的情况下,对于包含N个元素的列表,可能需要扫描整个列表多达N次.

合并排序:

这是用于排序列表的最流行的分而治之算法之一.基本思想是,如果你有两个已经排序的列表,很容易合并它们.从每个列表的开头开始,删除具有最小起始值的列表的第一个元素.重复这个过程,直到你消耗了两个列表中的所有项目,然后你就完成了!

1     4        8     10    
   2     5  7     9
------------ becomes ------------> 
1  2  4  5  7  8  9  10

但是如果你没有两个排序列表呢？如果您只有一个列表,其元素是随机顺序怎么办？

这是合并排序的聪明之处.您可以将任何单个列表分成更小的部分,每个部分都是未排序的列表,排序的列表或单个元素(如果你的话,它实际上是一个排序列表,长度为1).

因此,合并排序算法的第一步是将整个列表划分为越来越小的子列表.在最小的级别(每个列表只有一个或两个元素),它们很容易排序.并且一旦排序,很容易将任何两个相邻的排序列表合并到包含两个子列表的所有元素的更大的排序列表中.

注意:就最坏情况场景效率而言,此算法比上面描述的冒泡排序方法要好得多.我不会详细解释(这涉及一些相当简单的数学,但需要一些时间来解释),但提高效率的快速原因是该算法将其问题分解为理想大小的块然后合并那些块的结果.冒泡排序算法一次解决整个问题,因此它没有得到"分而治之"的好处.

这些只是用于排序列表的两种算法,但是还有许多其他有趣的技术,每种技术都有自己的优点和缺点:快速排序,基数排序,选择排序,堆排序,壳排序和桶排序.

互联网上充斥着有关排序的有趣信息.这是一个很好的起点:

http://en.wikipedia.org/wiki/Sorting_algorithms