#include<iostream>
using namespace std;
void insertion(int* a);
void main()
{
int arraya[10]={2,4,6,8,7,9,12,1,11,0};
insertion(arraya);
cout<<"the arraya after insertion:";
for(int i=0;i<10;i++)
cout<<" "<<arraya[i];
system("pause");
}
void insertion(int* a )
{
int i,j;
int length=10;
for(i=1;i<length;i++)
{
int key=a[i];
j=i-1;
while(j>=0&&a[j]>key)
{
a[j+1]=a[j];
j--;
}
a[j+1]=key;
}
}
#include<iostream>
using namespace std;
void merge(int a[], int p, int q, int r)
{
int i,j,k,n1,n2;
n1=q-p+2;//n1和n2要多留一位给INT_MAX; 所以一个要加2，一个要加1；
n2=r-q+1;
int l[11];
int m[11];
int pp=p;//P是中间那个数，不能动。所以我们重新复制给PP；
for(i=0;i<n1-1;i++)
{
l[i]=a[pp];
pp++;//别忘了pp也要自加，我之前就忘了这点，同理qq也是
}
l[n1-1]=INT_MAX;//因为我是用数组做的，而不是vector，所以没法动态分配。只能用类库里的INT_MAX来限制每次大小不一样的数组长度
int qq=q+1;
for(j=0;j<n2-1;j++)
{
m[j]=a[qq];
qq++;
}
m[n2-1]=INT_MAX;
i=j=0;
for(k=p;k<=r;k++)
{
if(l[i]<=m[j])//如果数组l的值小就把l数组的值放进原先数组里
{
a[k]=l[i];
i++;
}
else
{
a[k]=m[j];
j++;
}
}
}
void mergesort(int a[], int p, int r)
{
if(p<r)
{
int q;
q=(p+r)/2;
mergesort(a,p,q);
mergesort(a,q+1,r);
merge(a, p,q, r);
}
}
void main()
{
int arraya[10]={1,3,2,5,6,4,7,12,9,10};
mergesort(arraya,0,9);
for(int i=0;i<10;i++)
cout<<arraya[i]<<" ";
cout<<endl;
system("pause");
}
#include<iostream>
using namespace std;
#include<vector>
void merge(vector<int>&A,vector<int>&temp,int p, int q, int r);
void mergesort(vector<int>&A, vector<int>&temp,int p, int r);
void mergeSort(vector<int>&A);
void main()
{
vector<int> ve;
ve.push_back(3);
ve.push_back(5);
ve.push_back(1);
ve.push_back(2);
ve.push_back(6);
ve.push_back(4);
ve.push_back(0);
ve.push_back(9);
ve.push_back(8);
ve.push_back(7);
mergeSort(ve);
for(int i=0;i<ve.size();i++)
cout<<ve[i];
cout<<endl;
}
void merge(vector<int>&A,vector<int>&temp,int p, int q, int r)
{
int i=p;
int j=q+1;
int t=p;
while(i<=q&&j<=r)
{
if(A[i]<A[j])
temp[t++]=A[i++];
else
temp[t++]=A[j++];
}
while(i<=q)
temp[t++]=A[i++];
while(j<=r)
temp[t++]=A[j++];
for(int k = p; k<= r; ++k)
A[k] = temp[k];
}
void mergesort(vector<int>&A, vector<int>&temp,int p, int r)
{
if(p<r)
{
int q;
q=(p+r)/2;
mergesort(A,temp,p,q);
mergesort(A,temp,q+1,r);
merge(A,temp,p,q,r);
}
}
void mergeSort(vector<int>&A)
{
vector<int>temp(A.size());
mergesort(A,temp,0,A.size()-1);
}
#include<iostream>
using namespace std;
struct node
{
node(int v =0, node *n =0 )
:value(v),next(n)
{}
int value;
node* next;
};
void frontbacksplit(struct node* source, struct node **frontRef, struct node **backRef)
{
struct node *slow;
struct node *fast;
slow=source;
fast=source->next;
while(fast!=NULL)
{
fast=fast->next;
if(fast!=NULL)
{
slow=slow->next;
fast=fast->next;
}
}
*frontRef=source;
*backRef=slow->next;
slow->next=NULL;
}
struct node* sortedmerge(struct node *a, struct node *b)
{
struct node *result=NULL;
struct node** lastptrref=&result;
while(a!=0&&b!=0)
{
if(a->value<=b->value)
{
*lastptrref=a;
a=a->next;
lastptrref=&((*lastptrref)->next);
}
else
{
*lastptrref=b;
b=b->next;
lastptrref=&((*lastptrref)->next);
}
}
if(a!=0)
*lastptrref=a;
if(b!=0)
*lastptrref=b;
return(result);
}
void mergesort(struct node** headRef)
{
if((*headRef)==0||(*headRef)->next==0)
return;
struct node* head=*headRef;
struct node* a=NULL;
struct node* b=NULL;
frontbacksplit(head,&a,&b);
mergesort(&a);
mergesort(&b);
*headRef=sortedmerge(a,b);
}
void main()
{
node *node9=new node(1);
node *node8=new node(2,node9);
node *node7=new node(3,node8);
node *node6=new node(4,node7);
node *node5=new node(5,node6);
node *node4=new node(6,node5);
node *node3=new node(7,node4);
node *node2=new node(8,node3);
node *node1=new node(9,node2);
node *head=node1;
node *runner;
runner=head;
while(runner)
{
std::cout<<runner->value<<" ";
runner=runner->next;
}
std::cout<<"\n";
mergesort(&head);
runner=head;
while(runner)
{
std::cout<<runner->value<<" ";
runner=runner->next;
}
std::cout<<"\n";
system("pause");
}
#include<iostream>
using namespace std;
int partition(int A[8],int size,int p, int r)
{
int i,j,x,temp;
x=A[r];
i=p-1;
for(j=p;j<=r-1;j++)
{
if(A[j]<=x)
{
i=i+1;
temp=A[i];
A[i]=A[j];
A[j]=temp;
}
cout<<endl;
for(int z=0;z<8;z++)
cout<<A[z]<<" ";
cout<<endl;
}
temp=A[i+1];
A[i+1]=A[r];
A[r]=temp;
return i+1;
}
void quicksort(int A[8],int size, int p, int r)
{
if(p<r)
{int q=partition(A,size,p,r);
quicksort(A,size,p,q-1);
quicksort(A,size,q+1,r);}
}
int main()
{
int A[8]={2,8,7,1,3,5,6,4};
int z;
cout<<"before quicksort: ";
for(z=0;z<8;z++)
{
cout<<A[z]<<" ";
}
cout<<endl;
quicksort(A,8,0,7);
cout<<"after quicksort: ";
for(z=0;z<8;z++)
{
cout<<A[z]<<" ";
}
cout<<endl;
system("pause");
return 0;
}
#include<iostream>
using namespace std;
#include<ctime>
#include<cstdlib>
int random(int p, int r)
{
int size=r-p+1;
return p+rand()%size;
}
int partition(int A[8],int size,int p, int r)
{
int i,j,x,temp,s;
s=random(p,r);
temp=A[r];
A[r]=A[s];
A[s]=temp;
x=A[r];
i=p-1;
for(j=p;j<=r-1;j++)
{
if(A[j]<=x)
{
i=i+1;
temp=A[i];
A[i]=A[j];
A[j]=temp;
}
cout<<endl;
for(int z=0;z<8;z++)
cout<<A[z]<<" ";
cout<<endl;
}
temp=A[i+1];
A[i+1]=A[r];
A[r]=temp;
return i+1;
}
void quicksort(int A[8],int size, int p, int r)
{
if(p<r)
{int q=partition(A,size,p,r);
quicksort(A,size,p,q-1);
quicksort(A,size,q+1,r);}
}
int main()
{
int A[8]={2,8,7,1,3,5,6,4};
int z;
cout<<"before quicksort: ";
for(z=0;z<8;z++)
{
cout<<A[z]<<" ";
}
cout<<endl;
quicksort(A,8,0,7);
cout<<"after quicksort: ";
for(z=0;z<8;z++)
{
cout<<A[z]<<" ";
}
cout<<endl;
system("pause");
return 0;
}
#include<iostream>
using namespace std;
void countsort(int A[ ], int sizea, int B[], int sizeb,int k)
{
int i;
int C[10];
for(i=0;i<k;i++)
{
C[i]=0;
}
for(i=0;i<sizea;i++)
{
C[A[i]]=C[A[i]]+1;
}
for(i=1;i<k;i++)
{
C[i]=C[i]+C[i-1];
}
for(i=sizea-1;i>=0;i--)
{
B[C[A[i]]-1]=A[i];
C[A[i]]=C[A[i]]-1;
}
}
void main()
{
int i;
int A[]={2,5,3,0,2,3,0,3};
int B[]={0,0,0,0,0,0,0,0};
countsort(A,8,B,8,6);
for(i=0;i<8;i++)
{
cout<<B[i]<<" ";
}
}
#include<iostream>
using namespace std;
void maxheapify(int A[],int i,int size)
{
int l=2*i+1;
int r=2*i+2;
int large=i;
int temp;
if(l<=size-1&&A[l]>A[i])
large=l;
if(r<=size-1 && A[r]>A[large])
large=r;
if(large!=i)
{
temp=A[large];
A[large]=A[i];
A[i]=temp;
maxheapify(A,large,size);
}
}
void buildmaxheap(int A[],int size)
{
int i;
for(i=size/2;i>=0;i--)
{
maxheapify(A,i,size);
}
}
void heapsort(int A[],int size)
{
int i;
buildmaxheap(A,size);
for(i=0;i<size;i++)
cout<<A[i]<<" ";
cout<<endl;
for(i=size-1;i>0;i--)
{
int temp;
temp=A[0];
A[0]=A[i];
A[i]=temp;
size--;
maxheapify(A,0,size);
}
}
void main()
{
int i;
int AA[10]={2,4,23,1,3,5,6,9,7,10};
heapsort(AA,10);
for(i=0;i<10;i++)
{cout<<AA[i]<<" ";}
}
![笔试面试题目：滑动窗口(二)[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)