读书人
栏目▼

C#函数式编程入门之快速排序解决方法

发布时间： 2013-09-28 10:01:20 作者： rapoo

C#函数式编程入门之快速排序
本帖最后由 caozhy 于 2013-09-19 19:12:43 编辑 之前有人提出C#实现Currying太难看，也有人提出了F#。于是我又用F#写了下之前的那几个例子程序
第一个

    let add x y = x + y
    let mutable i = add 3 4
    printfn "%d" i


第二个
    let addTen x = add 10 x
    let mutable i = add 3 4
    let mutable j = addTen i
    printfn "%d" j


第三个
    let eval x y z = y x z
    let add x y = x + y
    let mutable i = eval 3 add 5
    printfn "%d" i


第四个
    let eval x y z = y x z
    let sub x y = x - y
    let mutable i = eval 8 sub 1
    printfn "%d" i


最后一个
    let outputArray = Array.iter (fun x -> printfn "%d" x)
    outputArray [| 1; 2; 3; 4; 5 |]


和C#的版本一比较，真是太优雅了！

好了，开始正题：

之前我在论坛贴了一个神奇的程序，用Lisp进行的快速排序
quicksort [] = []
quicksort (p:xs) = (quicksort lesser) ++ [p] ++ (quicksort greater)
    where
        lesser = filter (< p) xs
        greater = filter (>= p) xs


有人表示看天书一样，为了解释原理，我用C#改写了一个，代码稍微猥琐了点，但是还是很简洁的：
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApplication1
{
    class Program
    {        
        static void Main(string[] args)
        {
            Func<Func<int, int, bool>, Func<int[], int[]>> filter =
                x => new Func<int[], int[]>(y => y.Skip(1).Where(z => x(y[0], z)).ToArray());
            Func<int[], int[]> qsort = x => x;
            Func<int[], int[]> lesser = dt => filter((x, y) => y < x)(dt);
            Func<int[], int[]> greater = dt => filter((x, y) => y >= x)(dt);
            qsort = dt => dt.Length > 1 
                ? qsort(lesser(dt)).Concat(new int[] { dt[0] }).Concat(qsort(greater(dt))).ToArray()
                : dt;
            int[] data = { 4, 3, 1, 4, 6, 7, 5, 9, 3, 11, 1, 2, 11 };
            var result = qsort(data);
            foreach (int x in result) Console.WriteLine(x);
        }
    }
}


运行：

1
1
2
3
3
4
4
5
6
7
9
11
11
Press any key to continue . . .

简单解释下，其实这个不用我废话，如果快速排序的原理你没有忘记的话。
快速排序的思路就是根据某个元素（我这里用第一个元素）为参照，把数据分成两堆，小的一堆在左边，大的在右边，参照数据在中间，然后分别对左右两堆递归整理，直到某一堆只有一个元素为止，此时，数据就是排好序的了。

说说程序猥琐在什么地方，复杂的类型声明这个不用提，也不用提数组的连接，因为除非使用代码块，没办法在Lambda表达式内再嵌套定义Lambda表达式，只好让lesser和greater后面跟着难看的(dt)。

最后用F#实现一次：
[<EntryPoint>]
let main argv = 
    let lesser (x: int array) = Array.filter (fun i -> i < x.[0]) x.[1..]
    let greater (x: int array) = Array.filter (fun i -> i >= x.[0]) x.[1..]
    let rec qsort (p: int array) = 
        match p.GetLength(0) with
        | 0 | 1 -> p 
 
        | _ -> Array.concat [ (qsort(lesser p)); [| p.[0] |]; (qsort (greater p)) ]
    let data = [| 4; 3; 1; 4; 6; 7; 5; 9; 3; 11; 1; 2; 11 |]
    printfn "%A" (qsort data)
    0


[|1; 1; 2; 3; 3; 4; 4; 5; 6; 7; 9; 11; 11|]
Press any key to continue . . . 语法很糟糕 python比这简洁多了
[解决办法]
版主的程序还可以省掉一些冗余的写法：

using System;
using System.Linq;

class Program
{
public delegate Func<T2, TResult> Curry<in T1, in T2, out TResult>(T1 x);
public delegate Curry<T2, T3, TResult> Curry<in T1, in T2, in T3, out TResult>(T1 x);

static void Main()
{
Curry<Func<int, bool>, int[], int[]> filter = x => y => y.Skip(1).Where(x).ToArray();
Func<int[], int[]> qsort = null;
qsort = dt =>
{
var lesser = filter(x => x < dt[0]);
var greater = filter(x => x >= dt[0]);
return dt.Length > 1
       ? new[] {qsort(lesser(dt)), new[]{dt[0]}, qsort(greater(dt))}
         .SelectMany(x => x).ToArray()
       : dt;
};

int[] data = {4, 3, 1, 4, 6, 7, 5, 9, 3, 11, 1, 2, 11};
var result = qsort(data);
foreach (int x in result) Console.WriteLine(x);
}
}
当然这样写的quicksort也不quick了。
[解决办法]
我也贴一个自己写的：

static void QuickSort(int[] arr, int leftindex, int rightindex)
        {
            
            if (leftindex>=rightindex) return;
            int i = leftindex;
            int j = rightindex;
                int middle = arr[leftindex];
                while (i != j)
                {
                    while (j > i && arr[j] > middle)
                        j--;
                    if (j > i)
                    {
                        //找到了小于中轴的元素
                        arr[i] = arr[j];
                        i++;
                    }
                    while (i < j && arr[i] < middle)
                        i++;
                    if (i < j)
                    {
                        //找到了大于中轴的元素 
 
                        arr[j] = arr[i];
                        j--;
                    }
                }
                arr[i] = middle;
                QuickSort(arr, leftindex, i-1);
                QuickSort(arr, i + 1, rightindex);
            
            
        }

[解决办法]
引用:
版主最好分享一个非递归的写法和讲解，因为非递归的做法才能让我们这些菜鸟对分治法有更好的理解，很多人根本就不知道递归调用过程中，栈的操作方式。


不知道计算机的堆栈，就不会写函数递归了吗？我们从小学时就学过解数学方程式了，就学会递归地代入变量值进行求解了，也没有听说什么计算机堆栈。

递归是基本的数学函数概念的体现，跟什么堆栈没有关系。
[解决办法]
            func<int[], int[]> qsort = null;
            qsort = values => values.length() > 1 ? array.concat(qsort(values.getFindArray(value => value < values[0])), values.getFindArray(value => value == values[0]), qsort(values.getFindArray(value => value > values[0]))) : values;
不知道这种临时性代码有什么意义？
        private static valueType[] qsort<valueType>(valueType[] values) where valueType : IComparable<valueType>
        {
            return values.length() > 1 ? array.concat(qsort(values.getFindArray(value => value.CompareTo(values[0]) < 0)), values.getFindArray(value => value.CompareTo(values[0]) == 0), qsort(values.getFindArray(value => value.CompareTo(values[0]) > 0))) : values;
        }
定义一个函数有那么难吗？
教人函数式编程，首先得告诉别人，什么情况下适用，而不是滥用。
[解决办法]
递归神马滴简直弱爆了，三目递归才是王道
[解决办法]
第一次听说函数式编程，感觉挺有意思的
[解决办法]
楼主，请问一下微软的F#主要能干什么？
貌似都没几个人用啊……
[解决办法]
引用:
Quote: 引用:

            func<int[], int[]> qsort = null;
            qsort = values => values.length() > 1 ? array.concat(qsort(values.getFindArray(value => value < values[0])), values.getFindArray(value => value == values[0]), qsort(values.getFindArray(value => value > values[0]))) : values;
不知道这种临时性代码有什么意义？
        private static valueType[] qsort<valueType>(valueType[] values) where valueType : IComparable<valueType>
        {
            return values.length() > 1 ? array.concat(qsort(values.getFindArray(value => value.CompareTo(values[0]) < 0)), values.getFindArray(value => value.CompareTo(values[0]) == 0), qsort(values.getFindArray(value => value.CompareTo(values[0]) > 0))) : values;
        }
定义一个函数有那么难吗？
教人函数式编程，首先得告诉别人，什么情况下适用，而不是滥用。


好，是我没有说清楚，我多说几句。

首先，C#并不是一种函数式编程语言。正因为如此，用C#实现函数式编程显得有些古怪，与此同时，C#程序员理解函数式编程的一些基本思维方式显得困难。我想用C#作为桥梁，介绍F#以及其它的函数式编程语言，以及思维方式。这里我没有说得很具体。在函数式编程语言中，函数是一等公民，什么意思呢，就是函数即变量，变量即函数（这里说的函数即变量，不是严谨的，只是说函数和变量有同等的地位）。

比如 F#的
let x = 3
它既类似于C#的 x = 3; （还是有区别的，在F#中，let叫做绑定）
你也可以解读为，定义了一个无参数，返回常数的函数x
Func<int> x = () => 3;

函数是变量还体现在：
函数的定义可以随时改变，就像变量的值可以随时改变一样
函数可以作为高阶函数的参数传入，就像变量可以作为函数的参数一样
函数可以作为函数的返回值，就像变量可以作为函数的返回值一样
函数可以和函数组合，就像变量可以和变量相加相减一样
函数中可以定义函数，并且此函数的作用域仅在函数内，因此不用担心起名的问题，就像函数中可以定义变量，这个变量是局部变量，因此不用像全局变量那样担心命名一样


这种编程方式有什么优点吗？感觉虽然略显怪异但是还是可以使用，就是可能代码不好维护？
[解决办法]
最近在学算法，我用的C++，快速排序一般直接用<algorithm>里面的sort函数


[解决办法]


func main() {
arr := [...]int{4, 2, 5, 6, 12, 343, 56, 6}
num := len(arr)
for i := 0; i < num; i++ {
for j := i + 1; j < num; j++ {
if arr[i] > arr[j] {
temp := arr[i]
arr[i] = arr[j]
arr[j] = temp
}
}
}

fmt.Println(arr)
}




可以结贴了
[解决办法]
曹版应该写个Demo

读书人网 >C#

热点推荐

触屏版 | 电脑版

读书人网 m.reader8.net