一、【实验目的】
- 掌握二分查找过程及其实现算法;
- 掌握快速排序过程及其实现算法;
二、【实验要求】
- 实现整型数组的快速排序算法的程序;
- 在排序的基础上进行折半(二分)查找算法的实现;
- 要求:提交实验报告,附排序函数、折半查找函数的源代码,提供实验结果和数据。
三、【实验内容】
- 给定关键字序列32,75,29,63,48,94,25,46,18,70,调用快速排序函数进行排序并输出。
- 读入一个元素,比如32(成功找到)、27(不能成功查找到),用折半查找的方法判断该元素是否在已排序的数组内,输出是否找到,最好能统计比较的次数并输出。
[title]代码[/title]
#include <iostream> using namespace std; //快速排序 void quick_sort(int s[], int l, int r) { if (l < r) { int i = l, j = r, x = s[l]; while (i < j) { while(i < j && s[j] >= x) j--; if(i < j) s[i++] = s[j]; while(i < j && s[i] < x) i++; if(i < j) s[j--] = s[i]; } s[i] = x; quick_sort(s, l, i - 1); quick_sort(s, i + 1, r); } } //折半查找 void binarySearch(int arr[], int n, int target){ int l = 0, r = n - 1, i = 0; //在[l,r]区间查找 while( l <= r){ i++; int mid = l + (r-l)/2; if(target == arr[mid]){ cout << "目标元素在arr[" << mid << "]的位置," << "查找了" << i << "次"; break; } if (target < arr[mid]) r = mid -1; if (target > arr[mid]) l = mid + 1; } if ( l > r) cout << "找不到啊!"; } int main() { int s[] = {32,75,29,63,48,94,25,46,18,70}, l = 0, r = 9, target; quick_sort(s,l, r); for(int i=0;i<=r;i++) cout << s[i] << " "; cout << endl << "请输入查找的数字:"; cin >> target; binarySearch(s, r+1, target); return 0; }
ps:快排看一个博主的真是茅塞顿开(大佬就是大佬),附上链接——链接
:huaji13: