最大次大.txt

数据结构中的各种各样的排序算法

//8-6.编写一段程序实现在 N 个无序正整数之中的最大的正整数及次最大的正
// 整数 ，并且使用的比较次数不许超过 N＋logN-2次。
#include <iostream.h> 
struct node
{
int data;
int position;
};

int main()
{
int length,
h,i,k,l;

cout << "Input the length of array:" ;
cin >> length;

node *tree=new node[2*length];
for(i=length,l=1;i<2*length;i++,l++)
{
cout << "Input element" << l << " :" ;
cin >> tree[i].data;
tree[i].position=(i%2==0?i+1:i-1); //注意：将兄弟结点position记录为败者位置
}

for(k=(2*length-1)/2;k>=1;k--) //寻找最大---N-1次比较
{
if(tree[2*k].data>=tree[2*k+1].data)
{
tree[k].data=tree[2*k].data;
tree[k].position=tree[2*k].position;
}
else
{
tree[k].data=tree[2*k+1].data;
tree[k].position=tree[2*k+1].position;
}
}
cout << "The biggest is :" << tree[1].data << endl;

h=tree[1].position;
tree[h/2].data=tree[h].data;

for(h/=4;h>=1;h/=2) //寻找次大---logN-1次比较
{
if(tree[2*h].data>=tree[2*h+1].data)
tree[h].data=tree[2*h].data;
else
tree[h].data=tree[2*h+1].data;
}
cout << "The second is :" << tree[1].data << endl;

return 0;
}

 
  网 院 机 考 >> 希 尔 排 序  
 
 //shell排序 
#include <iostream.h> 
void shellSort(int *a, int s);
void shell(int *a, int s,int sl);
void print(int *a,int s);

int main()
{
int size;

cout << "Input the length of array:" ;
cin >> size;

int *array=new int[size+1];
for(int i=1;i<=size;i++)
{
cout << "Input element" << i <<" :" ;
cin >> array[i];
}
cout << "\nBefore Sort:" << endl;
print(array,size);

shellSort(array,size);

cout << "\n After Sort:" << endl;
print(array,size);

return 0;
}

void shellSort(int *a, int s)
{

int steplength[]={9,5,3,2,1};

for(int i=0;i<5;i++)
{
shell(a,s,steplength[i]);
}
}

void shell(int *a, int s,int sl)//一趟步长为steplength的shell sort
{
for(int i=sl+1;i<=s;i++)
{
if(a[i]<a[i-sl])
{
a[0]=a[i];
for(int j=i-sl;j>0 && a[0]<a[j];j-=sl)
{
a[j+sl]=a[j];
}
a[j+sl]=a[0];
}
}
}

void print(int *a,int s)
{
for(int i=1;i<s+1;i++)
{
cout << a[i] << " ";
}
cout << endl;
}


 
  网 院 机 考 >> 折 半 插 入 排 序  
 
 //折半插入排序 
#include <iostream.h>

void binsertSort(int *a,int s);
void print(int *a,int s);

int main()
{
int size;

cout << "Input the length of array:" ;
cin >> size;

int *array=new int[size+1];
for(int i=1;i<=size;i++)
{
cout << "Input element" << i <<" :" ;
cin >> array[i];
}
cout << "\nBefore Sort:" << endl;
print(array,size);

binsertSort(array,size+1);

cout << "\n After Sort:" << endl;
print(array,size);

return 0;
}

void binsertSort(int *a,int s)
{
for(int i=2;i<s;i++)
{
int low=1,
high=i-1,
mid;
a[0]=a[i];
while(low<=high)
{
mid=(low+high)/2;
if(a[0]<a[mid])
high=mid-1;
else
low=mid+1;
}
for(int j=i-1;j>=high+1;j--)
{
a[j+1]=a[j];
}
a[high+1]=a[0];
}
}

void print(int *a,int s)
{
for(int i=1;i<s+1;i++)
{
cout << a[i] << " ";
}
cout << endl;
}

 
  网 院 机 考 >> 堆 排 序 建 堆  
 
 //堆排序
#include <iostream.h> 
void heapSort(int *a,int s);
void heapAdjust(int *a,int l,int h);//建堆和筛选
void print(int *a,int s); 
int main()
{
int size;

cout << "Input the length of array:" ;
cin >> size;

int *array=new int[size+1];
for(int i=1;i<=size;i++)
{
cout << "Input element" << i <<" :" ;
cin >> array[i];
}
cout << "\nBefore Sort:" << endl;
print(array,size);

heapSort(array,size+1);

cout << "\n After Sort:" << endl;
print(array,size);

return 0;
}

void heapSort(int *a,int s)//堆排序
{
int temp=0;

for(int i=s/2;i>0;i--)//建堆
heapAdjust(a,i,s);
for(int j=s-1;j>1;j--)
{
temp=a[j];
a[j]=a[1];
a[1]=temp;

heapAdjust(a,1,j-1);
}
}

void heapAdjust(int *a,int l,int h)//筛选
{
int temp=a[l];

for(int i=2*l;i<=h;i*=2)//原来i<h
{
if(i<h && a[i]<a[i+1])
i++;
if(temp>a[i])//原来a[l]>=a[i]
break;
a[l]=a[i];
l=i;
}
a[l]=temp;
}

void print(int *a,int s)//打印
{
for(int i=1;i<s+1;i++)
{
cout << a[i] << " ";
}
cout << endl;
}