c语言排序和查找?
发布网友
发布时间：2022-04-24 11:18
共4个回答
热心网友
时间：2023-08-07 21:16
编写基于数组的顺序查找算法，测试数据量为1万、5万、10万、20万、
30万、40万和50万时的数据查询时间。
算法代码如下：

1 int seqsearch(int a[],int n,int key)
2 {
3 int k=n-1;
4 while(k>=0&&a[k]!=key)
5 k--;
6 return (k);
7 }

2）利用readData()函数从data2.txt中读入不同规模的有序数据存入数组，
编写基于数组的二分查找算法，测试数据量为1万、5万、10万、20万、30万、
40万和50万时的数据查询时间。
算法代码如下：

1 int binSearch(int a[],int n,int key)
2 {
3 int low=0;
4 int high=n-1;
5 int mid;
6 while(low<=high)
7 {
8 mid=(low+high)/2;
9 if(a[mid]==key) return mid;
10 if(a[mid]>key)
11 high=mid-1;
12 else
13 low=mid+1;
14 }
15 return -1;
16 }

3）请设计冒泡排序算法函数void bubbleSort(int a[],int n)，对a[1]..a[n]进行升序排序。
并测试在不同数据规模下的排序效率。
算法代码如下：

1 void bubbleSort(int a[],int n)
2 {
3 int i=1,j,flag=1;
4 while(i<=n-1&&flag)
5 {
6 flag=0;
7 for(j=1;j<=n-1-i;j++)
8 if(a[j+1]<a[j])
9 {
10 a[0]=a[j];
11 a[j]=a[j+1];
12 a[j+1]=a[0];
13 flag=1;
14 }
15 i++;
16 }
17 }
追问是这样？我怎么感觉不对啊？
热心网友
时间：2023-08-07 21:16
热心网友
时间：2023-08-07 21:17
热心网友
时间：2023-08-07 21:17
1.插入排序
2.选择排序
3.冒泡排序
4.希尔排序
5.快速排序
6.归并排序
7.堆排序
*/
/*
1.插入排序
思路：R[0],R[1],...R[i]是已经排序好的序列，要把R[i+1]插入到合适的位置。
template
*/
void insertionSort(vector &a)
{
int j;
T temp;
for(int i=1;i<a.size();i++)
{
temp=a[i];
j=i-1;
while(temp<a[j])
{
a[j+1]=a[j];
j--;
}
a[j+1]=temp;
}
}
/*
2.选择排序：
依次遍历，在合适的位置选择合适的数。每次选择最小的那一个。
*/
template
void selectionSort(vector &a)
{
int num=a.size();
T temp;
int p;
for(int i=0;i<num;i++)
{
temp=a[i];
p=i;
for(int j=i+1;j<num;j++)
{
if(a[j] < a[i]) p=j;
}
if(p != i)
{
temp=a[p];
a[i]=a[p];
a[p]=temp;
}
}
}
/*
3.冒泡排序
思路：从上到下，挨个比较相邻的两个数,较大的放在下面，知道任何两个数都是小在上，大在下。
*/
template
void bubbleSort(vector &a)
{
int num=a.size();
T temp;
bool flag=false;
for(int i=0;i<num-1;i++)
{
flag=false;
for(int j=0;j<num-i;j++)
{
if(a[j] > a[j+1])
{
flag=true;
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}
if(flag==false) break;
}
}
/*
4.希尔排序
思路：不是再每次比较相邻的两个数，而是比较间隔固定距离的两个数，这样一次可以减少。
*/
template
void shellSort(vector &a, int *incre, int ni) //增量存在数组incre里面,ni是数组incre的长度
{
int j;
T temp;
for(int g=0;gi<ni;g++)
{
for(int i=incre[g];i<a.size();i++)
{
temp=a[i];
j=i-incre[g];
while(temp<a[j])
{
a[j+incre[g]]=a[j];
j--;
}
a[j+incre[g]]=temp;
}
}
}
template
void shellSort2(vector &a)
{
int num=a.size();
int i,j,j;
T temp;
( (n/2)%2 ==0)? k=n/2+1 : k=n/2;//保证k为奇数
while(k>0)
{
for(i=k;i<num;i++)
{
temp=a[i];
j=i-k;
while( temp < a[j])
{
a[j+k]=a[j];
j-=k;
}
a[j+k]=temp;
}
(k/2)%2==0 ? k=k/2+1 : k=k/2;
}
}
/*
5.快速排序
思路：选定一个值（可随机，可为a[0]，随机更好），将小于这个数的所有数放在它的左边，大于这个数的放在又变。
*/
template
void quickSort(vector &a, int l, int r)
{
if(l<r)
{
int q=partition(a,l,r);
quickSort(a,l,q-1);
quickSort(q,q+1,r);
}
}
template
void partition(vector &a, int l, int r)
{
T temp=a[l],t;
int i=l,j=r;
while(i<=j)
{
while( a[++i]<temp && i<r);
while( a[j--]>temp);
t=a[i];
a[i]=a[j];
a[j]=t;
}
a[l]=a[j];
a[j]=x;
return j;
}
/*
6.归并排序
思路：将数组分段，分治思想，然后再合并
*/
template
void mergeSort(vector &a)
{
vector tmpArray(a.size());
mergeSort(a, tmpArray, 0, a.size()-1);
}
template
void mergeSort(vector &a, vector &tmpArray,int l, int r)
{
if(l<r)
{
int center=(l+r)/2;
mergeSort(a, tmpArray, l, center);
mergeSort(a, tmpArray, center+1, r);
merge(a,tmpArray,l,center+1,r);
}
}
template
void merge(vector &a, vector &tmpArray,int l, int center, int r)
{
int i=l,j=center;
int k=l;
while(i<center && j<=r)
{
if(a[i] < a[j] )
tmpArray[k++]=a[i++];
else
tmpArray[k++]=a[j++];
}
while(i < center) tmpArray[k++]=a[i++];
while(j <= r) tmpArray[k++]=a[j++];
for(i=l;i<=r;i++)
{
a[i]=tmpArray[i];
}
}
/*
7.堆排序
思路：建立堆，堆顶为最大。交换堆顶与堆底。调节二叉树，使堆顶元素始终为最大元素
*/
template
void heapSort(vector &a)
{
for (int i=a.size()/2;i>=0;--i)//build heap
{
perdown(a, i, a.size());
}
T temp;
for(int j=a.size()-1;j>=0;--j)
{
temp=a[j];
a[j]=a[0];
a[0]=temp;
perdown(a, 0 ,j);
}
}
template
void perdown(vector&a, int i, int n)
{
int child;
T temp;
for(temp=a[i]; 2*i+1<n;i=child)
{
child=2*i+1;
if(child+1<n && a[child]<a[child+1]) ++child;
if(temp <a[child]) a[i]=a[child];
else break;
}
a[i]=temp;
}
int main()
{
vector vi(5);
vi[0]=3;
vi[1]=2;
vi[2]=1;
vi[3]=5;
vi[4]=4;
cout<<"heapSort"<<endl;
heapSort(vi);
for (int i=0;i<vi.size();i++)
{
cout<<vi[i]<<" ";
}
cout<<endl;
cout<<"mergeSort"<<endl;
mergeSort(vi);
for (int i=0;i<vi.size();i++)
{
cout<<vi[i]<<" ";
}
cout<<endl;
getchar();
return 1;
}
