非递归归并排序.txt

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

 //非递归归并排序
#include <iostream.h>
#include <stdlib.h> 
void nonMergeSort(int *sr,int *tr,int l); //将sr[l+1]归并排序为tr[l+1]
void mergeDiv(int *sr,int *tr,int l,int step); //将数组sr[l+1]以step为步长合并为tr[l+1]
void merge(int *sr, int *tr, int i, int m, int n); //将有序的sr[i..m]和sr[m+1..n]
void print(int *a,int l); //打印数组 
int main()
{
int length;

cout << "Please input the length of array:";
cin >> length;
int *array=new int[length+1];
for(int i=1; i<=length; i++)
{
cout << "Input element " << i << ":";
cin >> array[i];
}
int *temp=new int[length+1];

cout << "\nBefore non Recursion Sort:" << endl;
print(array,length);
nonMergeSort(array,temp,length);
cout << "\nAfter non Recursion Sort:" << endl;
print(array,length);

return 0;
}

void nonMergeSort(int *sr,int *tr,int l) //将sr[l+1]归并排序为tr[l+1]
{
int step=1;
while(step<=l)
{
mergeDiv(sr,tr,l,step);
step=2*step;
}
}

void mergeDiv(int *sr,int *tr,int l,int step) //将数组sr[l+1]以step为步长合并为tr[l+1]
{
int i;

for(i=1; i<=l-2*step; i+=2*step)
merge(sr,tr,i,i+step-1,i+2*step-1);

if(l-i >= step)
merge(sr,tr,i,i+step-1,l);
else
{
for(;i<=l;i++)
tr[i]=sr[i];
}
for(i=1; i<=l; i++)
sr[i]=tr[i];

}

void merge(int *sr, int *tr, int i, int m, int n) //将有序的sr[i..m]和sr[m+1..n]
{ //归并为有序的tr[i..n]
int j,k;

for(j=m+1,k=i; i<=m && j<=n; k++)
{

if (sr[i]<=sr[j])
tr[k]=sr[i++];
else
tr[k]=sr[j++];
}
while (i<=m)
tr[k++]=sr[i++];
while (j<=n)
tr[k++]=sr[j++];
}

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

 
  网 院 机 考 >> 快 速 排 序(非递归) 
 
 //7-7.写一个"完美"的非递归的快速分类的程序。 
#include <iostream.h>

int quickSort(int *a,int l,int h);
void print(int *a,int l);

int main()
{
int stack[20][2]={0},
length=0,
top=1,
l,
h,
mid;

cout << "Please input the length of array:";
cin >> length;

int *array=new int[length+1];
for(int i=1;i<=length;i++)
{
cout << "Input element " << i << ":";
cin >> array[i];
}

cout << "Before QuickSort: ";
print(array,length);

stack[top][0]=1;
stack[top][1]=length;
top++;
while(top>1)
{
top--;
l=stack[top][0];
h=stack[top][1];
mid=quickSort(array,l,h);
if(mid!=l)
{
stack[top][0]=l;
stack[top][1]=mid-1;
top++;
}
if(mid!=h)
{
stack[top][0]=mid+1;
stack[top][1]=h;
top++;
}
}
cout << "\n After QuickSort: ";
print(array, length);

return 0;
}

int quickSort(int *a,int l,int h) //一趟快速排序
{
a[0]=a[l];

while(l<h)
{
while ( (l < h) && (a[h] >= a[0]) )
h--;
if(l<h)
{
a[l]=a[h];
l++;
}
while ( (l < h) && (a[l] <= a[0]) )
l++;
if(l<h)
{
a[h]=a[l];
h--;
}
} 
a[l]=a[0];

return l;
}

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

 
  网 院 机 考 >> 最 大 次 大  
 
 //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;
}