>
南邮python用户组 南邮python用户组 17成员

quicksort 之 python VS haskell VS c/c++

狼.敬畏生命 2010-07-23
前几天和GF聊起GUI编程,双方因为一个小问题,争执了起来.如下:
GF学的是C#,用的IDE是微软的VS20xx; 我用的是C++, 虽然是用的QtCreator,但是一直坚持在VIM下手动编码.

GF在北京无聊,就打开qt的文档看看,手动编了一个小窗口,然后对我说
gui编程都差不多. 我于是"针锋相对", 如果GUI编程,用IDE的助手精灵之类的
工具,拖拖控件,做做界面,那当然都查不多,而且GUI编程本质的也是事件驱动
(这个貌似是苹果所创),但是, 掩藏在这之下的实现方式就不一样了.于是随手举了个例子 ----quicksort.

quicksort 的思想就是分而治之(没学过算法,还是GF告诉我这么专业的名词)
把小于头部元素的放在前,大的放在后面.但是实现方式,大家看看:
python:
1 def quicksort( toList):
2 if not toList: return []
3 else return quicksort([x for x in toList[1:] if x <toList[0]]) \
4 + quicksort([x for x in toList[1:] if x >= toList[0] ])

haskell:
1 quicksort ::(Ord a) => [a] -> [a]
2 quicksort [] = []
3 quicksort (x:xs) =
4 let smallerSorted = quicksort [a | a <- xs, a < x]
5 biggerSorted = quicksort [a | a... xs , a >= x]
6 in smallerSorted ++ [x] ++biggerSorted

c/c++(以c的方式处理):
void swap(int *a, int *b)
{
int t=*a; *a=*b; *b=t;
}

void quicksort(int arr[],int beg,int end)
{
if (end >< r)
{
if (arr[k] < piv)
k++;
else
swap(&arr[k], &arr[r--]);
}
if (arr[k] < piv){

swap(&arr[k],&arr[beg]);

quicksort(arr, beg, k);
quicksort(arr, r, end);
}else {
if (end - beg == 1)
return;

swap(&arr[--k],&arr[beg]);
quicksort(arr, beg, k);
quicksort(arr, r, end);
}
}

}

呵呵,代码的简洁程度,一看就出来了.python和haskell这里面的思想是一致的,用的都是list comprehension .
前几天和GF聊起GUI编程,双方因为一个小问题,争执了起来.如下:
GF学的是C#,用的IDE是微软的VS20xx; 我用的是C++, 虽然是用的QtCreator,但是一直坚持在VIM下手动编码.

GF在北京无聊,就打开qt的文档看看,手动编了一个小窗口,然后对我说
gui编程都差不多. 我于是"针锋相对", 如果GUI编程,用IDE的助手精灵之类的
工具,拖拖控件,做做界面,那当然都查不多,而且GUI编程本质的也是事件驱动
(这个貌似是苹果所创),但是, 掩藏在这之下的实现方式就不一样了.于是随手举了个例子 ----quicksort.

quicksort 的思想就是分而治之(没学过算法,还是GF告诉我这么专业的名词)
把小于头部元素的放在前,大的放在后面.但是实现方式,大家看看:
python:
1 def quicksort( toList):
2 if not toList: return []
3 else return quicksort([x for x in toList[1:] if x <toList[0]]) \
4 + quicksort([x for x in toList[1:] if x >= toList[0] ])

haskell:
1 quicksort ::(Ord a) => [a] -> [a]
2 quicksort [] = []
3 quicksort (x:xs) =
4 let smallerSorted = quicksort [a | a <- xs, a < x]
5 biggerSorted = quicksort [a | a <- xs , a >= x]
6 in smallerSorted ++ [x] ++biggerSorted

c/c++(以c的方式处理):
void swap(int *a, int *b)
{
int t=*a; *a=*b; *b=t;
}

void quicksort(int arr[],int beg,int end)
{
if (end >= beg + 1)
{
int piv = arr[beg], k = beg + 1, r = end;

while (k < r)
{
if (arr[k] < piv)
k++;
else
swap(&arr[k], &arr[r--]);
}
if (arr[k] < piv){

swap(&arr[k],&arr[beg]);

quicksort(arr, beg, k);
quicksort(arr, r, end);
}else {
if (end - beg == 1)
return;

swap(&arr[--k],&arr[beg]);
quicksort(arr, beg, k);
quicksort(arr, r, end);
}
}

}

呵呵,代码的简洁程度,一看就出来了.python和haskell这里面的思想是一致的,用的都是list comprehension .
0
显示全文

查看更多有趣的豆瓣小组

回应 (5条) 只看楼主

  • 狼.敬畏生命
    豆瓣编辑器好差,缩进全没有了......
  • 狼.敬畏生命
    越来越发现,如果要想理解并且用好递归(recusion) ,得学学用fuctional programming language.
  • catherine
    我还是觉得,你那个什么list的底层肯定也是c的思想本质。
  • 狼.敬畏生命
    @catherine

    神马 ? 没看懂你的意思......
  • 书.记
    同样没看懂……例子跟引言有什么关系吗
添加回应

推荐小组

值得一读

    豆瓣
    我们的精神角落
    免费下载 iOS / Android 版客户端