设计四
查找和排序
一、 设计目的
1．掌握顺序查找，二分法查找，分块查找的算法； 2．掌握各种排序算法及其性能的比较。
二、 设计内容
1. 任务描述
任务1：编写一个程序输出在顺序表{13，22，35，43，54，68，71，82，98，1005}中采用顺序方法和折半方法查找某个关键字的过程。
任务2：编写一个程序实现直接插入排序过程，并输出{94，28，57，66，35，84，63，42，71，10}的排序过程。
任务3：编写一个程序实现快速排序算法，并输出{94，28，57，66，35，84，63，42，71，10}的排序过程。
2. 问题的表示方案
使用一个顺序表存储所有输入数据，一个整型变量存储数据长度
3. 主要数据类型与变量
int data[MAXSIZE]; int Count;
4. 算法或程序模块
任务1：
void Sequence(ostream &out, int key)
功能：顺序查找
void Half(ostream &out, int key)
功能：折半查找 任务2：
void InsertSort(ostream &out)
功能：直接插入排序 任务3：
int Partition(int low, int high)
功能：把待排序数组分为两部分，使基准元素左边的元素都小于基准元素，右边的都大于基准元素。
void QuickSort(ostream &out, int left, int right)
功能：快速排序
三、 测试
1. 方案
任务1：
测试方案：输入表中存在的元素，输入表中不存在的元素
测试数据：顺序表{13，22，35，43，54，68，71，82，98，1005}，key=68,key=32。 任务2、3：
测试数据：数组{94，28，57，66，35，84，63，42，71，10}
2. 结果
四、 总结与讨论
本设计还存在的问题有：
1、 使用int型的一维数组存储数据，未考虑数据不为整型等情况。 可以做的改进：
1、 使用double类型进行存放
附：程序模块的源代码
class Find {
protected:
int data[MAXSIZE]; int Count; //初始化查找实例 //Data：数组数据 //length：数组长度
Find(int Data[], int length) { }
//顺序查找 //out：输出流 //key：查找的关键字
void Sequence(ostream &out, int key) { }
//折半查找 //out：输出流 //key：查找的关键字
void Half(ostream &out, int key) {
int high = Count - 1; int low = 0; int mid = 0; while(low <= high) {
mid = (low + high) / 2; out << data[mid] << \; //小于则向后查找
for(int i = 0; i < Count; i++) { }
out << endl;
out << data[i] << \; if(data[i] == key)
break;
Count = length;
for(int i = 0; i < length; i++) { }
data[i] = Data[i];
public:
};
}
}
if(data[mid] < key)
low = mid + 1; //大于则向前查找
else if(data[mid] > key)
high = mid - 1; //相等则停止 else { }
out << \查找成功！\ << endl; return;
out << \查找失败！\ << endl;
class Sort {
protected:
int data[MAXSIZE]; int Count;
int Partition(int low, int high) { }
void Swap(int i, int j) { }
int temp = data[i]; data[i] = data[j]; data[j] = temp; int i, k = low; int pivot = data[low];
for(i = low + 1; i <= high; i++) { }
data[low] = data[k]; data[k] = pivot; return k;
if(data[i] < pivot) { }
k++; if(k != i)
Swap(i, k);
public: