数据结构6种算法排序.docx

数据结构6种算法排序.docx

《数据结构6种算法排序.docx》由会员分享，可在线阅读，更多相关《数据结构6种算法排序.docx（12页珍藏版）》请在冰点文库上搜索。

数据结构6种算法排序

排序测试

代码：

#include

#include

#include"d_random.h"

#include"d_timer.h"

usingnamespacestd;

//#defineNum5000;

template

voidselectionSort（Tarr[],intn）

{intsmallIndex;

intpass,j;

Ttemp;

for（pass=0;pass

{

smallIndex=pass;

for（j=pass+1;j

if（arr[j]

if（smallIndex!

=pass）{

temp=arr[pass];

arr[pass]=arr[smallIndex];

arr[smallIndex]=temp;

}

}

}

template

voidinsertionSort（vector&v）

{

inti,j,n=v.size（）;

Ttemp;

for（i=1;i

{j=i;

temp=v[i];

while（j>0&&temp

v[j]=v[j-1];

j--;

}

v[j]=temp;

}

}

//template

voidexchangesort（vector&v）

{

intvsize=v.size（）,temp,pass,i;

for（pass=0;pass

for（i=pass;i

if（v[pass]>v[i+1]）{

temp=v[pass];

v[pass]=v[i+1];

v[i+1]=temp;

}

}

voidbubblesort（vector&v）

{

inttemp,n=v.size（）,i,j;

for（i=1;i

{

for（j=0;j

if（v[j]>v[j+1]）

{

temp=v[j];

v[j]=v[j+1];

v[j+1]=temp;

}

}

}

template

intpivotIndex（vector&v,intfirst,intlast）

{

intmid,scanUp,scanDown;

Tpivot,temp;

if（first==last）returnlast;

elseif（first==last-1）returnfirst;

else

{mid=（last+first）/2;

pivot=v[mid];

v[mid]=v[first];

v[first]=pivot;

scanUp=first+1;

scanDown=last-1;

while（scanUp

{

while（scanUp<=scanDown&&v[scanUp]

scanUp++;

while（scanUp<=scanDown&&pivot

scanDown--;

if（scanUp

temp=v[scanUp];

v[scanUp]=v[scanDown];

v[scanDown]=temp;

}

}

v[first]=v[scanDown];

v[scanDown]=pivot;

returnscanDown;

}

}

template

voidquicksort（vector&v,intfirst,intlast）

{

intpivotLoc;

Ttemp;

if（last-first<=1）return;

elseif（last-first==2）

{if（v[last-1]

{temp=v[last-1];

v[last-1]=v[first];

v[first]=temp;

}

return;

}

else

{pivotLoc=pivotIndex（v,first,last）;

quicksort（v,first,pivotLoc）;

quicksort（v,pivotLoc+1,last）;

}

}

template

voidmerge（vector&v,intfirst,intmid,intlast）

{

vectortempVector;

intindexA,indexB,indexV;

indexA=first;

indexB=mid;

while（indexA

if（v[indexA]

{

tempVector.push_back（v[indexA]）;indexA++;

}

else

{

tempVector.push_back（v[indexB]）;indexB++;

}

while（indexA

{tempVector.push_back（v[indexA]）;

indexA++;

}

while（indexB

{

tempVector.push_back（v[indexB]）;

indexB++;

}

indexA=first;

for（indexV=0;indexV

{

v[indexA]=tempVector[indexV];

indexA++;

}

}

template

voidmergeSort（vector&v,intfirst,intlast）

{

if（first+1

{

intmidpt=（last+first）/2;

mergeSort（v,first,midpt）;

mergeSort（v,midpt,last）;

merge（v,first,midpt,last）;

}

}

voidmain（）

{

randomNumberrnd;

inttemp;

timertime;

vectortest1,test2,test3,test4,test5,test6,test7,test8,test9,test10,test11,test12,test13,test14,test15,test16;

intarr[5000];

cout<<"以下是六种算法随机排序时间"<

for（intj=0;j<5000;j++）

{

temp=arr[j]=rnd.random（100）;

test1.push_back（temp）;

test2.push_back（temp）;

test3.push_back（temp）;

test4.push_back（temp）;

test5.push_back（temp）;

}

time.start（）;

selectionSort（arr,5000）;

time.stop（）;

cout<<"selectsorttakes"<

time.start（）;

insertionSort（test1）;

time.stop（）;

cout<<"insertsorttakes"<

time.start（）;

exchangesort（test2）;

time.stop（）;

cout<<"exchangesorttakes"<

time.start（）;

bubblesort（test3）;

time.stop（）;

cout<<"bubblesorttakes"<

time.start（）;

quicksort（test4,test4[0],test4[4999]）;

time.stop（）;

cout<<"quicksorttakes"<

time.start（）;

mergeSort（test5,test5[0],test5[4999]）;

time.stop（）;

cout<<"mergesorttakes"<

cout<

cout<<"以下是六种算法升序排序时间"<

for（inti=0;i<5000;i++）

{

arr[i]=i;

test6.push_back（i）;

test7.push_back（i）;

test8.push_back（i）;

test9.push_back（i）;

test10.push_back（i）;

}

time.start（）;

selectionSort（arr,5000）;

XX文库-让每个人平等地提升自我

time.stop（）;

cout<<"selectsorttakes"<

XX文库-让每个人平等地提升自我

XX文库-让每个人平等地提升自我time.start（）;

insertionSort（test6）;

time.stop（）;

cout<<"insertsorttakes"<

time.start（）;

exchangesort（test7）;

time.stop（）;

cout<<"exchangesorttakes"<

time.start（）;

bubblesort（test8）;

time.stop（）;

cout<<"bubblesorttakes"<

time.start（）;

quicksort（test9,test9[0],test9[4999]）;

time.stop（）;

cout<<"quicksorttakes"<

time.start（）;

mergeSort（test10,test10[0],test10[4999]）;

time.stop（）;

cout<<"mergesorttakes"<

cout<

cout<<"以下是六种算法降序排序时间"<

for（intk=4999;k>=0;k--）

{

arr[k]=k;

test11.push_back（k）;

test12.push_back（k）;

test13.push_back（k）;

test14.push_back（k）;

test15.push_back（k）;

}

time.start（）;

selectionSort（arr,5000）;

time.stop（）;

cout<<"selectsorttakes"<

time.start（）;

insertionSort（test11）;

time.stop（）;

cout<<"insertsorttakes"<

time.start（）;

exchangesort（test12）;

time.stop（）;

cout<<"exchangesorttakes"<

time.start（）;

bubblesort（test13）;

time.stop（）;

cout<<"bubblesorttakes"<

time.start（）;

quicksort（test14,test14[4999],test14[0]）;

time.stop（）;

cout<<"quicksorttakes"<

time.start（）;

mergeSort（test15,test15[4999],test15[0]）;

time.stop（）;

cout<<"mergesorttakes"<

}

截图：