函数式编程思想

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

如果对函数式编程思想进行概括，就是f(x) = na(x) , 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)…这种，可能有人会问面向对象，嗯，对于这种小型精巧的分治算法，使用面向对象有点像是无稽之谈，所以指令式的面向过程往往是一个好选择。

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

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

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

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

过程如下：

#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]);elsebreak;}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;
}

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

函数式编程

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

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

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

代码如下：

#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;
}