快速排序算法和二分查找算法整合

# 快速排序算法和二分查找算法整合

```
#include <stdio.h>

// 快速排序函数
void quickSort(int arr[], int low, int high) {
    int i = low, j = high, pivot = arr[(low + high) / 2];
    while (i <= j) {
        while (arr[i] < pivot) i++;
        while (arr[j] > pivot) j--;
        if (i <= j) {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            i++; j--;
        }
    }
    if (low < j) quickSort(arr, low, j);
    if (i < high) quickSort(arr, i, high);
}

// 二分查找函数
int binarySearch(int arr[], int left, int right, int x)
{
    if (right >= left) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == x)
            return mid;
        if (arr[mid] > x)
            return binarySearch(arr, left, mid - 1, x);
        return binarySearch(arr, mid + 1, right, x);
    }
    return -1;
}

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

// 调用快速排序函数对数组进行排序
    quickSort(arr, 0, n - 1);

// 调用二分查找函数查找指定值
    int result = binarySearch(arr, 0, n - 1, x);
    if (result == -1)
        printf("Element is not present in array");
    else
        printf("Element is present at index %d", result);

return 0;
}
```

在该代码中，我们首先定义了一个整数数组和要查找的值。然后，我们调用快速排序函数quickSort对数组进行排序。快速排序函数实现了经典的快速排序算法，该算法将数组划分为两个子数组，其中一个子数组的所有元素都比另一个子数组的所有元素小。然后，它递归地对子数组进行排序，直到整个数组有序。

在排序后，我们调用二分查找函数binarySearch来查找指定值。二分查找算法使用类似于快速排序的递归方法，通过比较中间元素来不断缩小查找范围，直到找到指定值或者查找范围为空。如果查找成功，该函数返回指定值在数组中的索引。否则，返回-1表示该值不存在于数组中。

Angus's Blog

Navigation

Recent Posts

Friend Links