c++3、借助快速排序的思想,在一组无序的记录中查找给定关键字的值等于key的记录,设此记录存放于数组 r [ 1... n ]中。若查找成功,则返回在 r数组中的位置,否则显示"not find"信息。
时间: 2024-03-18 13:40:46 浏览: 51
可以使用快速排序算法对数组进行排序,然后使用二分查找算法查找给定关键字的值。以下是使用C++实现的代码:
```
#include <iostream>
using namespace std;
// 快速排序算法
void quickSort(int r[], int low, int high) {
if (low < high) {
int i = low, j = high, pivot = r[low];
while (i < j) {
while (i < j && r[j] >= pivot) j--;
if (i < j) r[i++] = r[j];
while (i < j && r[i] <= pivot) i++;
if (i < j) r[j--] = r[i];
}
r[i] = pivot;
quickSort(r, low, i - 1);
quickSort(r, i + 1, high);
}
}
// 二分查找算法
int binarySearch(int r[], int low, int high, int key) {
while (low <= high) {
int mid = (low + high) / 2;
if (r[mid] == key) return mid;
else if (r[mid] > key) high = mid - 1;
else low = mid + 1;
}
return -1;
}
int main() {
int r[] = {5, 2, 3, 1, 4};
int n = sizeof(r) / sizeof(int);
int key = 3;
// 对数组进行快速排序
quickSort(r, 0, n - 1);
// 在排序后的数组中查找给定关键字的值
int pos = binarySearch(r, 0, n - 1, key);
if (pos >= 0) cout << "found at position " << pos << endl;
else cout << "not find" << endl;
return 0;
}
```
在此例中,数组r中存储了待查找的记录,n表示数组的长度,key表示要查找的关键字。首先使用快速排序算法对数组进行排序,然后再使用二分查找算法在排序后的数组中查找给定关键字的值。如果查找成功,则返回在r数组中的位置;否则显示"not find"信息。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)