学算法并非和语言无关

1. 写在前面

算法这个东西，本来不是什么特别复杂的东西，就是为了解决某个问题提出的一个解决方案，说白了，就是一种思路。基本上，所有的算法书上都默认选用了伪代码来表达算法，因为这样可以脱离具体的语言，让算法学习者能够直面算法的本质，理解算法的核心，然后使用自己常用的语言来重新表达，写出能够运行的代码。实际上，在我接触到ruby这类高表达力的语言前，我也这么认为。虽然我能够理解很多算法的核心本质，但往往在实际用C或者java来实现时，总是被一些数组索引等细枝末节的问题所折磨，我通常会告诉自己，嗷，我还没有深刻领悟它，再去看看算法图述和伪码。

但是，今天我想说，我错了。也许，有的语言能够更好地表述算法，表述算法的好的语言应该能够以最接近人类语言的方式表达出来，而且基本就能够运行出结果。

2. 基本快速排序

下面是关于快速排序的official描述： 快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。

步骤为：

从数列中挑出一个元素，称为 “基准”（pivot）， 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

简单地说就是，按数组中某个元素为标准，将数组分为大于该数和不大于该数两个组，然后递归地分别处理这两个组，知道所有元素有序。

那么，我们看看算法导论是怎么用伪码来表述该算法的：

QUICKSORT(A,p,r)
  if p<r
    then q <- PARTITION(A,p,r)
      QUICKSORT(A,p,q-1)
      QUICKSORT(A,q+1,r)

PARTITION(A,p,r)
  x<-A[r]
  i <- p-1
  for j <- p to r-1
    do if A[j]<=x
      then i <- i+1
        exchange A[i] <-> A[j]
  exchange A[i+1] <-> A[r]
  return i+1

看看吧，不算空行一共14行代码，这甚至还没有包括没有实现的辅助函数exchange呢。反正看算法导论时，我看到这样一堆伪代码时，我都要先去喝杯水，然后深吸一口气，告诉自己，好吧一口气读完吧。

接着，我希望用我爱的ruby重新实现一遍：

def qs(list)
	if list.size<=1
		list
	else
		left,right=list[0..-2].partition{|x| x<=list.last}
		qs(left)+[list.last]+qs(right)
	end
end

总共8行代码，实际上还可以缩减到5行（可以参考维基百科的ruby实现）。几乎比伪代码节约了一半长度，而且算法表述非常清晰。更重要的是，这是一段可以直接运行的代码，这不是很鼓舞人心吗？

irb(main):056:0> list=[9, 4, 6, 3, 7, 11, 5, 6]
=> [9, 4, 6, 3, 7, 11, 5, 6]
irb(main):066:0> qs list
=> [3, 4, 5, 6, 6, 7, 9, 11]

最终，如果真的希望使用这段代码，那么就在ruby特有语言基础上再走一步，当然这步和算法表述无关了，只是为了在ruby中更为漂亮地使用该实现。

class Array
	def quick_sort
		if self.size<=1
			self
		else
			left,right=self[0..-2].partition{|x| x<=self.last}
			left.quick_sort+[self.last]+right.quick_sort
		end
	end
end

使用示例：

irb(main):069:0> list.quick_sort
=> [3, 4, 5, 6, 6, 7, 9, 11]

3. 关于UE的一点感悟

是的，用户体验。各种和计算机打交道的语言也要有好的用户体验，程序员就是编程语言的用户。有时候程序bug很多，真的有可能是语言不好。各种算法书上的伪码真的很让人恶心，所以，伪码也并不简捷。我相信，最终，计算机编程语言会进化到一种，那就是人类语言，那时，就再也没有程序员了，或者，所有人都是程序员。

ruby
Comments

Comments