内部排序算法比较(2)

结果分析：冒泡排序，直接插入排序以及简单选择排序比较次数较多，快速排序，希尔排序及堆排序比较次数较少；并可得冒泡排序和直接插入排序相对较稳定，其他四种内部排序为不稳定排序。

六．源程序清单 #include\#include\#include\#include\#include%using namespace std;

#define LIST_INIT_SIZE 50000

int bj1=0,yd1=0,bj2=0,yd2=0,bj3=0,yd3=0,bj4=0,yd4=0,bj5=0,yd5=0,bj6=0,yd6=0,n;//yd，bj为记录关键字比较和移动的次数 typedef struct {

int key; }ElemType; typedef struct {

ElemType *elem; int length; }SqList;

void addlist(SqList &L)//初始化顺序表 {

a: printf(\请输入你要输入的个数:\ scanf(\ if(n>50000) {

printf(\超出范围重新输入!!!\\n\ goto a; }

L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType)); if(!L.elem)exit(0); }

void random(SqList &L)//随机数产生程序 {

L.length=0;

static bool first=true; if(first) {

srand(time(0)); first=false;

}//使输入相同个数时每次产生的随机数不同 for(int i=1;i30000) goto a; ++L.length; } }

void memory(SqList &M,SqList &L)//记录L，使每个排序算法都用一组相同的随机数 { M.length=0; for(int i=1;i

void BubbleSort(SqList &L)//冒泡排序 { int i,j; for(i=1;iL.elem[j+1].key) {

L.elem[0].key=L.elem[j].key; L.elem[j].key=L.elem[j+1].key; L.elem[j+1].key=L.elem[0].key; yd1+=3; } } } }

void InsertSort(SqList &L)//直接插入排序 {

int i,j;

for(i=2;i<=L.length;i++) {

if(L.elem[i].key

L.elem[0].key=L.elem[i].key;

yd2++; j=i-1; bj2++;

while(L.elem[0].key

L.elem[j+1].key=L.elem[j].key; j--; yd2++; bj2++; }

L.elem[j+1].key=L.elem[0].key; yd2++; } } }

void SelectSort(SqList &L)//选择排序 {

int i,j,k;

for(i=1;i

for(j=i+1;j

bj3++;

if(L.elem[j].key

if(i!=k) {

L.elem[0].key=L.elem[i].key; L.elem[i].key=L.elem[k].key; L.elem[k].key=L.elem[0].key; yd3+=3; } } }

int Partition(SqList &L,int low,int high)//快速排序 {

int pivotkey;

L.elem[0]=L.elem[low]; yd4++;

pivotkey=L.elem[low].key;

while (low

yd4++;

while(low=pivotkey) --high;

L.elem[low]=L.elem[high]; bj4++; yd4++;

while (low

L.elem[high]=L.elem[low]; bj4++; yd4++; }

L.elem[low]=L.elem[0]; yd4++; return low; }

void QSort(SqList &L,int low,int high) {//对顺序表的子序列作快速排序 int pivotloc; if(low

pivotloc=Partition(L,low,high); QSort(L,low,pivotloc-1); QSort(L,pivotloc+1,high); } }

void QuickSort(SqList &L) {//对顺序表L作快速排序 QSort(L,1,L.length); }

void ShellSort(SqList &L)//希尔排序 {

int i,d=L.length/2,j,w=0,k; while(w

w=1;

for(i=w;i

for(j=i+d;j

if(L.elem[i].key>L.elem[j].key) { k=j; bj5++; } }

if(i!=k) {

L.elem[0].key=L.elem[i].key; L.elem[i].key=L.elem[k].key; L.elem[k].key=L.elem[0].key; yd5+=3; } w++; }

d=d/2; w=1; } }

void HeapAdjust(SqList &L,int s,int m )

{//调整L.elem[s]的关键字，使L.elem[s?..m]成为一个大根堆 SqList rc;

rc.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType)); if(!rc.elem)exit(0); int j;

rc.elem[0]=L.elem[s]; for(j=2*s;j<=m;j*=2) {bj6++; if(j

L.elem[s]=rc.elem[0]; }

void HeapSort(SqList &L) {//对顺序表L进行堆排序 int i; for(i=L.length/2;i>0;--i) HeapAdjust(L,i,L.length); for(i=L.length;i>1;--i)