[Case Study]Sorting using Scala

是 否 +2 论坛币

k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

送您一个全额奖学金名额~ !

立即领取

感谢您参与论坛问题回答

经管之家送您两个论坛币！

+2 论坛币

1. 早就听闻Haskell的三行快排优雅简洁，被其强大的表达能力深深折服。但目前看来，另一门函数式编程语言-Scala，其表达能力毫不逊色，用它来表达算法，形式上可以和伪代码一样简洁，不至于迷失到算法的细节中。想想当年学快排的时候，花了一下午还没有搞定。现在看来，用C语言来表达算法虽然效率很高，但却容易过早地纠结于算法细节，而忽略了算法的整体思想。这里用几行Scala的代码来展示一下，如何优雅地排序。
   
2. 
   
3. 插入排序
   
4. 插入排序可谓是最经典的排序算法，效率不高，但实现简单，可用于小规模的排序。其基本思想是从前往后遍历，通过把第n的元素插入到前n的列表中并保持有序，来达到整个链表的有序性。
   
5. 
   
6. def insertionSort[T](list: List[T])(implicit order: Ordering[T]): List[T] = {
   
7.   def insert(list: List[T], x: T) = {
   
8.     val (init, tail) = list.span(order.lt(_, x))
   
9.     init ::: x :: tail
   
10.   }
    
11. 
    
12.   if (list.isEmpty) list
    
13.   else  insert(insertionSort(list.init), list.last)
    
14. }
    
15. 
    
16. 归并排序
    
17. 归并排序实用性也很高，尤其适合分布式排序，假如有万亿个数，以至于无法放进内存，用归并来排序是再是和不过了。其基本思想是分而治之，把大的链表分成两部分，分别排序之后再合并起来。
    
18. 
    
19. 
    
20. def mergeSort[T](list: List[T])(implicit order: Ordering[T]): List[T] = {
    
21.   def merge(x: List[T], y: List[T]): List[T] = {
    
22.     x match {
    
23.       case Nil => y
    
24.       case (head:: tail) if order.lt(head, y.head) => head :: merge(tail, y)
    
25.       case xs => y.head :: merge(y.tail, xs)
    
26.     }
    
27.   }
    
28. 
    
29.   if (list.length <= 1) list
    
30.   else {
    
31.     val (init, tail) = list.splitAt(list.length / 2)
    
32.     merge(mergeSort(init), mergeSort(tail))
    
33.   }
    
34. }
    
35. 
    
36. 快速排序
    
37. 用快速排序来展现函数式编程的魅力是再适合不过了，如果写的简单一点仅仅需要三行，从此再也不用担心不会写快排了！其思想和归并排序很像，不过略有区别。找一个枢纽点，将所有元素分成比枢纽点小的以及比它大的两堆，分别进行排序，再合并起来。
    
38. 
    
39. def qsort[T](list: List[T])(implicit order: Ordering[T]): List[T] = {
    
40.   if (list.isEmpty) list
    
41.   else
    
42.     qsort(list.filter(order.lt(_, list.head))) :::
    
43.       list.head :: qsort(list.filter(order.gt(_, list.head)))
    
44. }
    
45. 注解
    
46. 这里实现的三个排序算法都是用泛型来表达的，其比较函数用了Ordering的比较函数，并且作为隐式参数，也可以显示提供，默认实现升序排序。
    
47. 为了测试其排序的性能，我们可以再写一个计时函数，这里用到了Scala的另一个特性，按名称求值（call by name），也就是可以把一个表达式直接当做函数参数传递，而不是传递表达式的值。
    
48. 
    
49. def timer(fun: => List[Any]): Long = {
    
50.   val start = System.currentTimeMillis()
    
51.   fun
    
52.   System.currentTimeMillis() - start
    
53. }
    
54. 
    
55. val list = (1000 to 1 by -1).toList
    
56. timer(qsort(list))
    
57. timer(mergeSort(list))
    
58. timer(insertionSort(list))
    
59. 这样就可以看到三个排序的时间了，但比较尴尬的是，最慢的是快速排序，插入排序第二，而归并排序则是最快的。不出意外应该是快速排序那个枢纽点选择的不好，所以我试着把枢纽点换成了中位数，再测试之后性能果然好了很多。不过比较遗憾的是，这里的三个实现都不是工业级的实现，递归层数会成为最大的限制，当数量级达到10万的时候，它们的表现都很吃力了

复制代码

扫码加我 拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

分享0 收藏0 回帖

关键词：Case study Sorting SCALA Using study 编程语言 经典的 C语言 规模 能力