我们经常会用到各种各样的编程思想，例如面向过程、面向对象。不过笔者在该博客简单介绍一下函数式编程思想.

如果对函数式编程思想进行概括，就是y=uf(x)。至于其他的编程思想，可能是y=a(x)+b(x)+c(x)……，也有可能是y=f(x)=f(x)/a + f(x)/b+f(x)/c……..

面向过程的指令式编程

面向过程，就是y=a(x)+b(x)+c(x)……这种，当然，对于这种小型精巧的分治算法，使用面向对象有点像是无稽之谈，所以指令式的面向过程往往是一个好选择。

下面以快速排序为例，现在我们需要对数组进行从小到大排序。

快速排序的核心就是：将数组划分为左右两个子集，保证右边的元素比左边大，然后不断递归重复这个过程。

我们要实现排序的过程如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
graph TD
s(全集)-->|分割与交换|l(左子集);
s-->|分割与交换|r(右子集);
l--分割与交换-->ll(左子集的左子集);
ll-->|分割与交换|lll(左左左子集);
ll-->|分割与交换|llr(左左右子集);

l-->|分割与交换|lr(左子集的右子集)
lr-->|分割与交换|lrl(左右左子集)
lr-->|分割与交换|lrr(左右右子集)

r--分割与交换-->rl(右子集的左子集);
rl-->|分割与交换|rll(右左左子集)
rl-->|分割与交换|rlr(右左右子集)

r-->|分割与交换|rr(右子集的右子集)
rr-->|分割与交换|rrl(右右左子集)
rr-->|分割与交换|rrr(右右右子集)




显然，这是一个不断递归的过程，但是我们可以观察到，程序总是在重复分割交换这个过程，因此将交换和分割单独写一个函数，作为基本指令。因此我们需要有三个函数：交换函数、分区函数、排序函数。

过程如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <stdio.h>

// 交换两个元素
void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// 分区函数
int partition(int arr[], int low, int high) {
    int pivot = arr[high]; // 选择最后一个元素作为枢轴
    int i = (low - 1); 

    for (int j = low; j <= high - 1; j++) {
        // 如果当前元素小于或等于枢轴
        if (arr[j] <= pivot) {
            i++; //j查找比枢纽小的元素，i++后必然指向比枢纽大的元素，否则i与j会同步更新
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}


/*
//笔者更喜欢使用下面这种，分析源码就可以知道，下面更接近二分查找的形式，而上面更接近从头遍历。
//经过笔者测试，上面的平均耗时几乎是下面的1.7倍

int partition(int arr[], int low, int high) {
    int pivot = arr[high]; // 选择最后一个元素作为枢轴
    int i = low - 1; // 较小元素的索引
    int j = high ;
    for( ; ; )
    {
        while( arr[++i] < pivot){ }
        while( arr[--j] > pivot && j > low){ }
        if( i < j)
            swap(&arr[i],&arr[j]);
        else
            break;
    }
    swap(&arr[i], &arr[high]);
    return i ;
}

 */



// 快速排序函数
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        // pi 是分区索引，arr[pi] 已经排好序
        int pi = partition(arr, low, high);

        // 分别排序两个子数组
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

// 打印数组
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    quickSort(arr, 0, n - 1);
    printf("Sorted array: \n");
    printArray(arr, n);
    return 0;
}

现在让我们来看看函数式编程：

函数式编程

函数式编程的重点在于数组，简单用该图理解：

简单来说就是，重点关心输入和输出，屏蔽其他因素。

图中的过程是，输入全集数组，输出结果是无数个小数组，输入小数组，输出结果是合并后的全集数组。所以我们需要有两个函数：排序分割函数、合并函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
graph TD


s(全集)-->|分割与交换|lll(左左左子集);
s-->|分割与交换|llr(左左右子集);

s-->|分割与交换|lrl(左右左子集)
s-->|分割与交换|lrr(左右右子集)

s-->|分割与交换|rll(右左左子集)
s-->|分割与交换|rlr(右左右子集)

s-->|分割与交换|rrl(右右左子集)
s-->|分割与交换|rrr(右右右子集)


lll-->|合并|all(排序后的数组)
llr-->|合并|all(排序后的数组)
lrl-->|合并|all(排序后的数组)
lrr-->|合并|all(排序后的数组)
rll-->|合并|all(排序后的数组)
rlr-->|合并|all(排序后的数组)
rrl-->|合并|all(排序后的数组)
rrr-->|合并|all(排序后的数组)

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <stdio.h>
#include <stdlib.h>

//排序的本质是对数组的操作，它将数组划分为一个个的小单元
typedef struct {
    int* array;
    int length;
} SubArray;

//合并小单元
SubArray concatenate(SubArray left, int pivot, SubArray right) {
    int* new_array = (int*)malloc((left.length + right.length + 1) * sizeof(int));
    for (int i = 0; i < left.length; i++) {
        new_array[i] = left.array[i];
    }
    new_array[left.length] = pivot;
    for (int i = 0; i < right.length; i++) {
        new_array[left.length + 1 + i] = right.array[i];
    }
    return (SubArray){new_array, left.length + right.length + 1};
}


SubArray quicksort(int* array, int length) {
    if (length <= 1) {
        return (SubArray){array, length};
    }

    int pivot = array[0];

    int* left_array = (int*)malloc(length * sizeof(int));
    int* right_array = (int*)malloc(length * sizeof(int));
    int left_size = 0, right_size = 0;

    for (int i = 1; i < length; i++) {
        if (array[i] <= pivot) {
            left_array[left_size++] = array[i];
        } else {
            right_array[right_size++] = array[i];
        }
    }

    SubArray left_sorted = quicksort(left_array, left_size);
    SubArray right_sorted = quicksort(right_array, right_size);

    SubArray result = concatenate(left_sorted, pivot, right_sorted);

    free(left_sorted.array);
    free(right_sorted.array);

    return result;
}

void printArray(int* array, int length) {
    for (int i = 0; i < length; i++) {
        printf("%d ", array[i]);
    }
    printf("\n");
}

int main() {
    int array[] = {10, 7, 8, 9, 1, 5};
    int length = sizeof(array) / sizeof(array[0]);

    SubArray sorted = quicksort(array, length);

    printf("Sorted array: ");
    printArray(sorted.array, sorted.length);
    free(sorted.array);

    return 0;
}