数据结构考题，有会做的吗？

来源：百度知道 编辑：UC知道 时间：2024/05/24 09:31:38
1.编写一个直接插入排序算法，使得查找插入位置时不是采用顺序的方法而是采用二分的方法。
2.编写一个对整型数组A[n+1]中的A[1]至A[n]元素进行选择排序的算法，使得首先从待排序区间中选择出一个最小值并同第一个元素交换，再从待排序区间中选择出一个最大值并同最后一个元素交换，反复进行直到待排序区间中元素的个数不超过1为止。
3.完成直接选择排序算法。
三道题全会的，分直接拿走。

1.
#include <iostream>
#define n 8
using namespace std;
typedef int KeyType; //假设的关键字类型
typedef struct //记录类型
{
KeyType key; //关键字域
//InfoType otherinfo; //记录的其他域，类型InfoType根据具体应用来定义
}RecType;
//直接插入排序算法
void InsertSort(RecType R[]) //按递增序
{
int i,j;
for(i=2;i<=n;i++)
{
R[0]=R[i];
j=i-1;
while(R[0].key<R[j].key)
{
R[j+1]=R[j];
j--;
}
R[j+1]=R[0];
}
}
int main()
{
int i;RecType R[n+1]; //n为记录个数，SepList为记录数组类型
while(1)
{
for(i=1;i<=n;i++)
cin>>R[i].key;
InsertSort(R);
for(i=1;i<=n;i++)
printf("%d ",R[i]);
return 0;
}
}
2.
template <typename T>
void SelectionSort(T arr[],int n)
{
int smallIndex; //表中最小元素的下标
int pass,j; //用来扫描子表的下标
T temp; //用来交换表元素