借助于快速排序的算法思想，在一组无序的记录中查找给定关键字值等于key的记 录。设此组记录存放于数组r[1…n]中。若查找成功，则输出该记录在数组中的位置及其关键字 值，否则显示“not find”信息。请简要说明算法思想并设计c语言算法。

快速排序是一种常用的分治策略，它将待查的关键字值插入到已排序的部分，而不是直接在原地查找。查找过程可以结合快速排序的思想，即先对整个数组进行排序，然后二分查找定位关键字。

算法步骤如下：

1. **数组排序**：首先，对数组r[1...n]进行快速排序，使得所有小于key的元素都在key的左边，大于key的元素在右边。

2. **二分查找**：找到排序后的数组中间元素，如果这个元素恰好等于key，那么返回其索引；如果key小于中间元素，就在左半部分继续查找；如果key大于中间元素，就在右半部分查找。

3. **递归查找**：重复上述过程，直到找到key或搜索范围为空（表示未找到）。

以下是基于上述思路的简单C语言实现（使用了快速排序的Lomuto分区法作为示例）：

#include <stdio.h>

// 快速排序辅助函数
int partition(int arr[], int low, int high) {
    int pivot = arr[high], i = (low - 1);
    
    for (int j = low; j <= high - 1; j++) {
        if (arr[j] <= pivot) {
            i++;
            // 交换元素
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }

    // 将pivot放到正确的位置
    int temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;

    return i + 1;
}

// 快速排序
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);

        // 对左右两个子区间分别进行快速排序
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

// 查找函数
void binarySearch(int arr[], int n, int key) {
    int low = 0, high = n - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;

        if (arr[mid] == key)
            return printf("找到，位置：%d，关键字值：%d\n", mid + 1, arr[mid]);

        else if (arr[mid] < key)
            low = mid + 1;
        else
            high = mid - 1;
    }

    printf("not find\n");
}

int main() {
    int r[] = {5, 2, 8, 1, 9, 4}; // 示例数组
    int n = sizeof(r) / sizeof(r[0]);
    int key = 4; // 要查找的关键字

    quickSort(r, 0, n - 1); // 先排序
    binarySearch(r, n, key); // 然后查找

    return 0;
}