排序算法课程设计

//各种排序算法汇总.cpp:定义控制台应用程序的入口点。

//

#includestdafx.h

#include

#include

usingnamespacestd;

#include

#include

#include

template

classSqList

{

private:

intlength;

T*r;

public://接口

SqList(intn=0);//构造长度为n的数组

~SqList()

{

length=0;

deleter;

r=NULL;

}

voidInsertSort();//顺序插入排序

voidDisPlay();//输出元素

voidBInsertSort();//折半插入排序

voidShellSort(intdlta[],intt);//希尔排序

voidQuickSort();//快速排序

voidSelectSort();//简单选择排序

voidBubbleSort();//改进冒泡排序

voidBubble_Sort2();//相邻两趟是反方向起泡的冒泡排序算法

voidBubble_Sort3();//对相邻两趟反方向算法进行化简,循环体中只包含一次冒泡

voidHeapSort();//堆排序

voidBuild_Heap_Sort();//堆排序由小到大序号建立大根堆

voidMergeSort();//归并排序

voidOE_Sort();//奇偶交换排序的算法

voidQ_Sort_NotRecurre();//非递归快速排序

voidHeapSort_3();//三叉堆排序

public://调用

voidShellInsert(intdk);//一趟希尔排序

voidQSort(intlow,inthigh);//快速排序

intPartition(intlow,inthigh);//一趟快速排序

intSelectMinKey(inti);//从i到length中选择最小值下标

voidHeapAdjust(ints,intm);//调整s的位置,其中s+1~m有序

voidHeapAdjust_3(ints,intm);//三叉堆****调整s的位置,其中s+1~m有序

voidMerge(TSR[],TTR[],inti,intm,intn);//归并

voidMSort(TSR[],TTR1[],ints,intt);//归并

voidEasy_Sort(intlow,inthigh);//3个数直接排序

voidBuild_Heap(intlen);//从低下标到高下标逐个插入建堆的算法***建立大根堆**但为排序

};

template

SqList::SqList(intn=0)

{

//srand(time(0));

length=n;

r=newT[length+1];

Tt;

cout<<随机生成<<n<<个值:<<endl;

for(inti=1;i<=length;i++)

{

//cin>>t;

r[i]=rand()%1000;

//r[i]=t;

}

for(inti=1;i<=length;i++)

cout<<r[i]<<,;

cout<<endl;

}

template

voidSqList::InsertSort()

{

inti,j;

for(i=2;i<=length;i++)

{

if(r[i]<r[i-1])

{

r[0]=r[i];

r[i]=r[i-1];

for(j=i-2;r[0]<r[i-2];j--)

r[j+1]=r[j];

r[j+1]=r[0];

}

}

}

template

voidSqList::DisPlay()

{

inti;

cout<<length<<元素为：<<endl;

for(i=1;i<length+1;i++)

{

cout<<r[i]<<,;

}

cout<<endl;

}

template

voidSqList::BInsertSort()

{

inti,j,m;

intlow,high;

for(i=2;i<=length;i++)

{

r[0]=r[i];

low=1;

high=i-1;

while(low<=high)

{

m=(low+high)/2;

if(r[0]<r[m])

high=m-1;

else

low=m+1;

}

for(j=i-1;j>=high+1;j--)

{

r[j+1]=r[j];

}

r[high+1]=r[0];

}

}

template

voidSqList::ShellInsert(intdk)

{

inti,j;

for(i=dk+1;i<=length;i++)

if(r[i]<r[i-dk])

{

r[0]=r[i];

for(j=i-dk;j>0&&r[0]<r[j];j-=dk)

{

r[j+dk]=r[j];

}

r[j+dk]=r[0];

}

}

template

voidSqList::ShellSort(intdlta[],intt)

{

intk=0;

for(;k<t;k++)

{

ShellInsert(dlta[k]);

}

}

template

intSqList::Partition(intlow,inthigh)

{

intpivotkey;

r[0]=r[low];//记录枢轴值

pivotkey=r[low];

while(low<high)

{

while(low=pivotkey)

high--;

r[low]=r[high];

while(low<high&&r[low]<=pivotkey)

low++;

r[high]=r[low];

}

r[low]=r[0];//枢轴记录到位

returnlow;//返回枢轴位置

}

template

voidSqList::QSort(intlow,inthigh)

{

intpivotloc;

if(low<high)

{

pivotloc=Partition(low,high);

QSort(low,pivotloc-1);

QSort(pivotloc+1,high);

}

}

template

voidSqList::QuickSort()

{

QSort(1,length);

}

template

intSqList::SelectMinKey(inti)

{

intj,min=i;

for(j=i;j<=length;j++)

{

if(r[min]>r[j])

{

min=j;

}

}

returnmin;

}

template

voidSqList::SelectSort()

{

inti,j;

Tt;

for(i=1;i<length;i++)//循环length-1次不是length次

{

j=SelectMinKey(i);

if(i!=j)

{

t=r[j];

r[j]=r[i];

r[i]=t;

}

}

}

template

voidSqList::BubbleSort()

{

inti,j;

intflag=1;//标识位，如果出现0，则没有交换，立即停止

Tt;

for(i=1;i<length&i++)

{

flag=0;

for(j=length-1;j>=i;j--)

if(r[j]>r[j+1])

{

t=r[j];

r[j]=r[j+1];

r[j+1]=t;

flag=1;

}

}

}

template

voidSqList::Bubble_Sort2()

{

boolchange=true;

intlow=1,high=length;

inti;

Tt;

while((low<high)&&change)

{

change=false;

for(i=low;i<high;i++)

{

if(r[i]>r[i+1])

{

t=r[i];

r[i]=r[i+1];

r[i+1]=t;

change=true;

}

}

high-=1;

for(i=high;i>low;i--)

{

if(r[i]<r[i-1])

{

t=r[i];

r[i]=r[i-1];

r[i-1]=t;

change=true;

}

}

low+=1;

}

}

template

voidSqList::Bubble_Sort3()

{

inti,d=1;

boolchange=true;

intb[3]={1,0,length};//b[0]为冒泡的下界,b[2]为上界,b[1]无用

Tt;

while(change)//如果一趟无交换，则停止

{

change=false;

for(i=b[1-d];i!=b[1+d];i=i+d)//统一的冒泡算法

{

if((r[i]-r[i+d])*d>0)///注意这个交换条件

{

t=r[i];

r[i]=r[i+d];

r[i+d]=t;

change=true;

}

}

d=d*(-1);//换个方向

}

}

template

voidSqList::HeapAdjust(ints,intm)

{

/*已知H.r[s..m]中记录的关键字除H.r[s].key之外均满足堆的定义，本函数*/

/*调整H.r[s]的关键字,使H.r[s..m]成为一个大顶堆(对其中记录的关键字而言)*/

intj;

Trc=r[s];

for(j=2*s;j<=m;j*=2)

{

/*沿key较大的孩子结点向下筛选*/

if(j<m&&r[j]<r[j+1])

j++;/*j为key较大的记录的下标*/

if(rc>=r[j])

break;/*rc应插入在位置s上,无需移动*/

r[s]=r[j];

s=j;

}

r[s]=rc;/*插入*/

}

template

voidSqList::HeapSort()

{

/*对顺序表H进行堆排序。算法10.11*/

Tt;

inti;

for(i=length/2;i>0;i--)/*把H.r[1..H.length]建成大顶堆*/

HeapAdjust(i,length);

for(i=length;i>1;i--)

{

/*将堆顶记录和当前未经排序子序列H.r[1..i]中最后一个记录相互交换*/

t=r[1];

r[1]=r[i];

r[i]=t;

HeapAdjust(1,i-1);/*将H.r[1..i-1]重新调整为大顶堆*/

}

}

template

voidSqList::Build_Heap_Sort()

{

inti;

Build_Heap(length);

for(i=length;i>1;i--)

{

Tt;

t=r[i];

r[i]=r[1];

r[1]=t;

Build_Heap(i-1);

}

}

template

voidSqList::Build_Heap(intlen)

{

Tt;

for(inti=2;i<=len;i++)

{

intj=i;

while(j!=1)

{

intk=j/2;

if(r[j]>r[k])

{

t=r[j];

r[j]=r[k];

r[k]=t;

}

j=k;

}

}

}

template

voidSqList::Merge(TSR[],TTR[],inti,intm,intn)

{

/*将有序的SR[i..m]和SR[m+1..n]归并为有序的TR[i..n]算法10.12*/

intj,k,x;

for(j=m+1,k=i;j<=n&&i<=m;k++)/*将SR中记录由小到大地并入TR*/

{

if(SR[i]<SR[j])

TR[k]=SR[i++];

else

TR[k]=SR[j++];

}

if(i<=m)

for(x=0;x<=m-i;x++)

TR[k+x]=SR[i+x];/*将剩余的SR[i..m]复制到TR*/

if(j<=n)

for(x=0;x<=n-j;x++)

TR[k+x]=SR[j+x];/*将剩余的SR[j..n]复制到TR*/

}

template

voidSqList::MSort(TSR[],TTR1[],ints,intt)

{

/*将SR[s..t]归并排序为TR1[s..t]。算法10.13*/

intm;

T*TR2=newT[length+1];

if(s==t)

TR1[s]=SR[s];

else

{

m=(s+t)/2;/*将SR[s..t]平分为SR[s..m]和SR[m+1..t]*/

MSort(SR,TR2,s,m);/*递归地将SR[s..m]归并为有序的TR2[s..m]*/

MSort(SR,TR2,m+1,t);/*递归地将SR[m+1..t]归并为有序的TR2[m+1..t]*/

Merge(TR2,TR1,s,m,t);/*将TR2[s..m]和TR2[m+1..t]归并到TR1[s..t]*/

}

}

template

voidSqList::MergeSort()

{

MSort(r,r,1,length);

}

template

voidSqList::OE_Sort()

{

inti;

Tt;

boolchange=true;

while(change)

{

change=false;

for(i=1;i<length;i+=2)

{

if(r[i]>r[i+1])

{

t=r[i];

r[i]=r[i+1];

r[i+1]=t;

change=true;

}

}

for(i=2;i<length;i+=2)

{

if(r[i]>r[i+1])

{

t=r[i];

r[i]=r[i+1];

r[i+1]=t;

change=true;

}

}

}

}

typedefstruct

{

intlow;

inthigh;

}boundary;

template

voidSqList::Q_Sort_NotRecurre()

{

intlow=1,high=length;

intpiv;

boundarybo1,bo2;

stackst;

while(low<high)

{

piv=Partition(low,high);

if((piv-low2))

{

bo1.low=piv+1;

bo1.high=high;

st.push(bo1);

high=piv-1;

}

elseif((piv-low>high-piv)&&(piv-low>2))

{

bo1.low=low;

bo1.high=piv-1;

st.push(bo1);

low=piv+1;

}

else

{

Easy_Sort(low,high);

high=low;

}

}

while(!st.empty())

{

bo2=st.top();

st.pop();

low=bo2.low;

high=bo2.high;

piv=Partition(low,high);

if((piv-low2))

{

bo1.low=piv+1;

bo1.high=high;

st.push(bo1);

high=piv-1;

}

elseif((piv-low>high-piv)&&(piv-low>2))

{

bo1.low=low;

bo1.high=piv-1;

st.push(bo1);

low=piv+1;

}

else

{

Easy_Sort(low,high);

}

}

}

template

voidSqList::Easy_Sort(intlow,inthigh)

{

Tt;

if((high-low)==1)

{

if(r[low]>r[high])

{

t=r[low];

r[low]=r[high];

r[high]=t;

}

}

else

{

if(r[low]>r[low+1])

{

t=r[low];

r[low]=r[low+1];

r[low+1]=t;

}

if(r[low+1]>r[high])

{

t=r[low+1];

r[low+1]=r[high];

r[high]=t;

}

if(r[low]>r[low+1])

{

t=r[low];

r[low]=r[low+1];

r[low+1]=t;

}

}

}

template

voidSqList::HeapAdjust_3(ints,intm)

{

Trc=r[s];

for(intj=3*s-1;j<=m;j=j*3-1)

{

if(j+1<m)//有3个孩子结点

{

if(rc>=r[j]&&rc>=r[j+1]&&rc>=r[j+2])

break;

else

{

if(r[j]>r[j+1])

{

if(r[j]>r[j+2])

{

r[s]=r[j];

s=j;

}

else//r[j]<=r[j+2]

{

r[s]=r[j+2];

s=j+2;

}

}

else//r[j]<=r[j+1]

{

if(r[j+1]>r[j+2])

{

r[s]=r[j+1];

s=j+1;

}

else//r[j+1]<=r[j+2]

{

r[s]=r[j+2];

s=j+2;

}

}

}

}

if(j+1==m)//有2个孩子结点

{

if(rc>=r[j]&&rc>=r[j+1])

break;

else

{

if(r[j]>r[j+1])

{

r[s]=r[j];

s=j;

}

else//r[j]<=r[j+1]

{

r[s]=r[j+1];

s=j+1;

}

}

}

if(j==m)//有1个孩子结点

{

if(rc>=r[j])

break;

else

{

r[s]=r[j];

s=j;

}

}

}

r[s]=rc;

}

template

voidSqList::HeapSort_3()

{

inti;

Tt;

for(i=length/3;i>0;i--)

HeapAdjust_3(i,length);

for(i=length;i>1;i--)

{

t=r[i];

r[i]=r[1];

r[1]=t;

HeapAdjust_3(1,i-1);

}

}

int_tmain(intargc,_TCHAR*argv[])

{

SqListSq(15);

//Sq.InsertSort();

//Sq.BInsertSort();

/*希尔排序*/

//inta[5]={5,4,3,2,1};

//Sq.ShellSort(a,5);

/*Sq.QuickSort();*/

//Sq.SelectSort();

/*Sq.BubbleSort();*/

/*Sq.HeapSort();*/

/*Sq.MergeSort();*/

/*Sq.Q_Sort_NotRecurre();*/

/*Sq.Bubble_Sort2();*/

/*Sq.OE_Sort();*/

/*Sq.Bubble_Sort3();*/

/*Sq.Build_Heap_Sort();*/

Sq.HeapSort_3();

Sq.DisPlay();

system(pause);

return1;

}