[排序算法]
<P><B>这个是热情的写的。我顺便拿他的来用。其他就是我写的了。整理成一个贴子算了二路归并
</B>#include<iostream>
using namespace std;</P>
<P>template <typename T>struct Node{
T key;</P>
<P>};
template <typename T>class Orderedlist{
int maxsize;
int last;
Node<T> slist[100];
public:
Orderedlist(){last=0;maxsize=100;}
int Length() const{return last+1;}//计算表长度
void Mergesort();
void MergePass(Node<T> *b,int len);
void Merge(Node<T> *b,int low,int mid,int high);
bool Insert(Node<T> & elem,int i);
void print();
};
template <typename T> bool Orderedlist<T>::Insert(Node<T> & elem ,int i){
if (i<0||i>last+1||last==maxsize-1) return false;
else{
for (int j=last;j>i;j--) slist[j]=slist[j-1];
slist[i]=elem;
last++;
return true;
}
}
template <typename T> void Orderedlist<T>::print(){
int i;
for(i=0;i<last;i++){
cout<<slist[i].key<<'\t';
if(i%8==7) cout<<endl;
}
cout<<endl;
}
template<typename T> void Orderedlist<T>::Mergesort(){
int len=1;
Node<T> b[100];
while(len<last){
MergePass(b,len);
len=2*len;
for(int i=0;i<last;i++) slist[i]=b[i];
}
}
template <typename T> void Orderedlist<T>::MergePass(Node<T> *b,int len){
int i,j;
i=0;
while(i+2*len<last){
Merge(b,i,i+len-1,i+2*len-1);
i= i+2*len;
}
if(i+len<last) Merge(b,i,i+len-1,last-1);
else for(j=i;j<last;j++) b[j]=slist[j];
}
template <typename T> void Orderedlist<T>::Merge(Node<T> *b,int low,int mid,int high){
int i,j,k;
i=low;
j=mid+1;
k=low;
while((i<=mid)&&(j<=high)){
if(slist[i].key<=slist[j].key) b[k++]=slist[i++];//取小者复制
else b[k++]=slist[j++];
}
while(i<=mid) b[k++]=slist[i++];//复制第一个文件的剩余元素
while(j<=high) b[k++]=slist[j++];//复制第二个文件的剩余元素
}</P>
<P>void main(){
const int h=5;
int i;
Orderedlist<int> ordlist;
int a[h]={5,4,3,2,1};
Node<int> n[h];
for(i=0;i<h;i++) n[i].key=a[i];
for(i=0;i<h;i++) ordlist.Insert(n[i],i); //建立顺序表
cout<<"未排序表："<<endl;
ordlist.print();
ordlist.Mergesort();
cout<<"已排序表："<<endl;
ordlist.print();
}
----------------------------------------------------------------------------------------------
</P>
<P>堆排序
#include<stdio.h>
void CreatHeap(int a[],int n,int h)
{ int i,j,flag,temp;
i=h;
j=2*i+1;
temp=a[i];
flag=0;
while(j<n && flag!=1)
{ if(j<n-1 && a[j]<a[j+1]) j++;
if(temp>a[j])
flag=1;
else
{ a[i]=a[j];
i=j;
j=2*i+1;
}
}
a[i]=temp;
}
void InitCreatHeap(int a[],int n)
{ int i;
for(i=(n-1)/2;i>=0;i--)
CreatHeap(a,n,i);
}
void HeapSort(int a[],int n)
{ int i,temp;
InitCreatHeap(a,n);
for(i=n-1;i>0;i--)
{ temp=a[0];
a[0]=a[i];
a[i]=temp;
CreatHeap(a,i,0);
}</P>
<P>}
main()
{ int n,i,a[100];
printf("请问你要输入几个排序数:\n");
scanf("%d",&n);
printf("请输入你要排序的数值:\n");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
HeapSort(a,n);
printf("排序后的:\n");
for(i=0;i<n;i++)
printf("%d\t",a[i]);
}
-------------------------------------------------------------
对半排序
#include<stdio.h>
main()
{ int i,j,temp, low,high,mid,a[100],n;
printf("请问你要输入几个数字:\n");
scanf("%d",&n);
printf("请输入数字:\n");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
for(i=1;i<n;i++)
{ temp=a[i];
low=0;
high=i-1;
while(high>=low)
{ mid=(low+high)/2;
if(temp<a[mid]) high=mid-1;
else
low=mid+1;
}
for(j=i-1;j>=low;j--)
a[j+1]=a[j];
a[low]=temp;
}
printf("排序后的:\n");
for(i=0;i<n;i++)
printf("%d\t",a[i]);
}
---------------------------------------------
快速排序
#include<stdio.h>
void QuickSort(int a[],int low,int high){
int i=low,j=high;
int temp=a[low];
while(i<j)
{
while(j>i&&temp<=a[j])
j--;
if(j>i)
{
a[i]=a[j];
i++;
}
while(j>i&&a[i]<temp)
i++;
if(j>i)
{
a[j]=a[i];
j--;
}
}
a[i]=temp;
if(low<i) QuickSort(a,low,i-1);
if(i<high)QuickSort(a,j+1,high);
}
main()
{ int a[100];
int high ,low,i,n;
printf("请问你要输入几个数字:\n");
scanf("%d",&n);
printf("请输入数字:\n");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
low=0;
high=n-1;
QuickSort(a,low,high);
printf("排序后的:\n");
for( i=0;i<n;i++)
printf("%d\t",a[i]);
}
--------------------------------------
冒泡
#include<stdio.h>
main()
{int i,j,temp,n,a[100],flag=1;
printf("请问你要输入几个排序数:\n");
scanf("%d",&n);
printf("请输入你要排序的数值:\n");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
for(i=0;i<n&&flag==1;i++)
{ flag=0;
for(j=1;j<n-i;j++)
if(a[j]<a[j-1])
{ flag=1;
temp=a[j-1];
a[j-1]=a[j];
a[j]=temp;
}
}
printf("排序后的:\n");
for(i=0;i<n;i++)
printf("%d\t",a[i]);
}
---------------------------------------------------------
希尔
#include<stdio.h>
void ShellSort(int a[],int n,int d[],int numOfD)
{ int i,j,k,m,span,temp;
for(m=0;m<=numOfD;m++)
{ span=d[m];
for(k=0;k<span;k++)
{ for(i=k;i<n-span;i=i+span)
{
temp=a[i+span];
j=i;
while(j>-1&&temp<=a[j])
{ a[j+span]=a[j];
j=j-span;
}
a[j+span]=temp;
}
}
}</P>
<P>}
main()
{int a[100], b[10],n,i,k,j;
printf("请问你要输入几个数字:\n");
scanf("%d",&n);
printf("请输入数字:\n");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
j=n;
k=0;
do{
j=j/2;
b[k]=j;
k++;
}while(j>0);
ShellSort(a,n,b,k);
printf("排序后的:\n");
for(i=0;i<n;i++)
printf("%d\t",a[i]);
}
---------------------------------------------
选择排序
#include<stdio.h>
main()
{int a[100], min,i,k,temp,j,cout;
printf("请问你要输入几个数字(不要超过100个！！):\n");
scanf("%d",&cout);
printf("请输入数字:\n");
for(i=0;i<cout;i++)
scanf("%d",&a[i]);
for(i=0;i<cout;i++)
{
min=i;
for(k=i+1;k<cout;k++)
{
if(a[min]>a[k])
{
min=k;
}
}if(i!=min)
{
temp=a[i];
a[i]=a[min];
a[min]=temp;
}
}
for(j=0;j<cout;j++)
printf("%d\t",a[j]);
}
------------------------------------------
直接插入
#include<stdio.h>
main()
{ int i,j,n,temp,a[100];
printf("请问你要输入几个数字:\n");
scanf("%d",&n);
printf("请输入数字:\n");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
for(i=0;i<n-1;i++)
{ j=i;
temp=a[i+1];
while(temp<a[j]&&j>-1)
{ a[j+1]=a[j];
j--;
}
a[j+1]=temp;
}
printf("排序后的:\n");
for(i=0;i<n;i++)
printf("%d\t",a[i]);
}
有什么问题就说出来。我好更改。</P>[em01][em01][em01][em01]
[align=right][color=#000066][此贴子已经被作者于2005-8-25 7:41:05编辑过][/color][/align]
谢谢
我漫漫欣赏分析消化啦。<BR>总之，多谢！！！！ 楼主，你的快排没有考虑退化的情况。 Good! [em34]<BR><FONT color=#3809f7><STRONG>谢谢楼主的代码<BR></STRONG></FONT><BR><FONT color=#1111ee><STRONG>可以转换为C代码吗？<BR><BR></STRONG></FONT> 好东西，正好周末考试用的上<BR>，省得我自己望电脑上打了再测试了<BR>呵呵<BR>谢了<BR>我收藏了～～～～～～～～～·页:
[1]
2