Java、Scala、Go以相同方式实现快速排序代码量比较

i6448038 · · 1885 次点击 · · 开始浏览

这是一个创建于的文章，其中的信息可能已经有所发展或是发生改变。

在程序猿的世界，语言之争是个永恒的话题，在此，我想说：让争论来的更猛烈些吧。

在此，我要用相同的方式实现快速排序。首先，我们简单的回顾一下什么是快速排序。

快速排序：

快排的精髓在于”分治“。注意：这是两个方面，”分“讲的是利用所选的元素（往往是第一个元素，在此命名为Key），以Key为分水岭将列表分为：比Key元素大的和比Key元素小的两部分；”治“讲的是将分开的两部分以同样的方式（”分”的方式）继续排序，直至完全排完。如下图所示：

很显然，用“递归”的方式是很不错的。下面，每个语言用最最简洁的方式实现这个排序，然后比较一下代码量：

给出的需要排序的序列是：6、2、7、3、9、4、8、5

JAVA:

private void setQuickSort(int[] array,int left,int right) {
int i = left;
int j= right;
int key = array[left];
int keyFlag = left;
while (i < j) {
while (i < j&&key <= array[j]) {
j--;
}
if(i < j){
int tmp = array[j];
array[j] = array[i];
array[i] = tmp;
keyFlag = j;
}
while (i < j&&key >= array[i]) {
i++;
}
if(i < j){
int tmp1 = array[j];
array[j] = array[i];
array[i] = tmp1;
keyFlag = i;
}
}
if(keyFlag>left+1){
setQuickSort(array, left, keyFlag - 1);
}
if(keyFlag<right-1){
setQuickSort(array,keyFlag+1,right);
}
}
}

Go:

func setQuickSort(array *[9]int, left, right int) {
i, j := left, right
m := left
key := array[left]
for i < j {
for i < j && key <= array[j] {
j--
}
if i < j {
array[i], array[j] = array[j], array[i]
m = j
}
for i < j && key >= array[i] {
i++
}
if i < j {
array[i], array[j] = array[j], array[i]
m = i
}
}
if m > left+1 {
setQuickSort(array, left, m-1)
}
if m < right-1 {
setQuickSort(array, m+1, right)
}
}

Scala:

def quickSort(array: List[Int]): List[Int] = {
if (array.isEmpty) array
else
quickSort(array.filter(_<array.head)):::array.head::quickSort(array.filter(_>array.head))
}