データ構造――各種並べ替えアルゴリズムの比較
一.実験の目的
一般的な並べ替えアルゴリズムを実現して,これらのアルゴリズムの理解を深め,今後これらのアルゴリズムを実際の問題の解決に応用できる.
実験のテーマ
並べ替えは、実際の問題でよく使われるアルゴリズムであり、快速、選択、挿入の3つの並べ替えアルゴリズムは、並べ替えアルゴリズムの中で最も簡単であり、最もよく使われているものであり、この3つのアルゴリズムを実現し、異なる数値系列で実行し、その後、3つの方法の空間的複雑さと時間的複雑さを比較し、比較結果を分析して、この3つの並べ替えアルゴリズムを選択する一般原則を導き出す.
三.実現ヒント
1.列待ちシーケンスのデータ構造説明:
四.思考と選択
1.他の並べ替えアルゴリズムの比較をさらに検討し、類似の時間複雑度と空間複雑度の分析を得て、特に異なるアルゴリズムに対して、テストデータの構造もできるだけ豊富にするように注意してください.
五.私の実現
(1) ソートアルゴリズムの実装
一般的な並べ替えアルゴリズムを実現して,これらのアルゴリズムの理解を深め,今後これらのアルゴリズムを実際の問題の解決に応用できる.
実験のテーマ
並べ替えは、実際の問題でよく使われるアルゴリズムであり、快速、選択、挿入の3つの並べ替えアルゴリズムは、並べ替えアルゴリズムの中で最も簡単であり、最もよく使われているものであり、この3つのアルゴリズムを実現し、異なる数値系列で実行し、その後、3つの方法の空間的複雑さと時間的複雑さを比較し、比較結果を分析して、この3つの並べ替えアルゴリズムを選択する一般原則を導き出す.
三.実現ヒント
1.列待ちシーケンスのデータ構造説明:
#define MAXSIZE 20 //
typedef int KeyType; //
typedef struct
{
KeyType key; //
InfoType otherifo; //
}RedType; //
typedef struct
{
RedType r[MAXSIZE+1]; //r[0]
int length; //
}SqList; //
四.思考と選択
1.他の並べ替えアルゴリズムの比較をさらに検討し、類似の時間複雑度と空間複雑度の分析を得て、特に異なるアルゴリズムに対して、テストデータの構造もできるだけ豊富にするように注意してください.
五.私の実現
(1) ソートアルゴリズムの実装
#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 20 //
/************************************* *************************************/
typedef int KeyType; //
typedef char InfoType;
typedef struct
{
KeyType key; //
InfoType otherifo; //
}RedType; //
typedef struct
{
RedType r[MAXSIZE+1]; //r[0]
int length; //
}SqList; //
/**************************************** *****************************************/
/*
.
： ， ，
， ，
。
： O（nlogn）， 。
； ，
O（n2） 。 ， 。
， O（nlogn）。 。
*/
void QuickSort(SqList &L,int l,int h)
{
if (l>=h)
return ;
int j ,i,key;
i=l;
j=h;
key=L.r[i].key;
while(i<j)
{
while(i<j&&L.r[j].key>key)
j--;
if (i<j)
L.r[i++].key=L.r[j].key;
while (i<j&&L.r[i].key<key)
i++;
if (i<j)
L.r[j--].key=L.r[i].key;
}
L.r[i].key=key;
if (l<i-1)
QuickSort(L,l,i-1);
if (i+1<h)
QuickSort(L,i+1,h);
}
/*
。
： （ ） ，
， 。 。
*/
void SelectSort(SqList &L)
{
int i,j,m,n=L.length+1 ;
int t ; //
for(i=1;i<n;i++)
{
m=i ;
for(j=i+1;j<n;j++)
{
if(L.r[j].key<L.r[m].key)
m=j;
}
if(m!=i)
{
t=L.r[i].key;
L.r[i].key=L.r[m].key;
L.r[m].key=t ;
}
}
}
/*
。
： ， 、 。
O（n）； O（n2） 、 ，
， 、 。
*/
void InsertSort(SqList &L)
{
// L 。
int i,j;
for (i=2; i<=L.length; ++i)
if (L.r[i].key<L.r[i-1].key)
{
// "<" ， L.r[i]
L.r[0] = L.r[i]; //
for (j=i-1; L.r[0].key<L.r[j].key; --j)
L.r[j+1] = L.r[j]; //
L.r[j+1] = L.r[0]; //
}
}
/*
. .
*/
void myPrint(SqList &L)
{
for(int i = 1;i<MAXSIZE+1;i++)
{
printf("%d ",L.r[i].key);
}
printf("
");
}
/***************************************main *************************************/
int main()
{
//1. 20
SqList s,s1,s2,s3;
s.length=20;
for(int i = 1;i<MAXSIZE+1;i++)
{
scanf("%d",&(s.r[i].key));
}
s1=s2=s3=s;
//2.
printf(" ---> ：
");
myPrint(s);
QuickSort(s3,1,s3.length); //
printf(" :
");
myPrint(s3);
printf(" ---> ：
");
myPrint(s);
SelectSort(s1); //
printf(" :
");
myPrint(s1);
printf(" ---> ：
");
myPrint(s);
InsertSort(s2); //
printf(" :
");
myPrint(s2);
system("PAUSE");
return 0;
}
#include<stdio.h>
#include<stdlib.h>
#include <time.h> //
#define MAXSIZE 10000 //
/************************************* *************************************/
typedef int KeyType; //
typedef char InfoType;
typedef struct
{
KeyType key; //
InfoType otherifo; //
}RedType; //
typedef struct
{
RedType r[MAXSIZE+1]; //r[0]
int length; //
}SqList; //
/**************************************** *****************************************/
/*
.
： ， ，
， ，
。
： O（nlogn）， 。
； ，
O（n2） 。 ， 。
， O（nlogn）。 。
*/
void QuickSort(SqList &L,int l,int h)
{
if (l>=h)
return ;
int j ,i,key;
i=l;
j=h;
key=L.r[i].key;
while(i<j)
{
while(i<j&&L.r[j].key>key)
j--;
if (i<j)
L.r[i++].key=L.r[j].key;
while (i<j&&L.r[i].key<key)
i++;
if (i<j)
L.r[j--].key=L.r[i].key;
}
L.r[i].key=key;
if (l<i-1)
QuickSort(L,l,i-1);
if (i+1<h)
QuickSort(L,i+1,h);
}
/*
。
： （ ） ，
， 。 。
*/
void SelectSort(SqList &L)
{
int i,j,m,n=L.length+1 ;
int t ; //
for(i=1;i<n;i++)
{
m=i ;
for(j=i+1;j<n;j++)
{
if(L.r[j].key<L.r[m].key)
m=j;
}
if(m!=i)
{
t=L.r[i].key;
L.r[i].key=L.r[m].key;
L.r[m].key=t ;
}
}
}
/*
。
： ， 、 。
O（n）； O（n2） 、 ，
， 、 。
*/
void InsertSort(SqList &L)
{
// L 。
int i,j;
for (i=2; i<=L.length; ++i)
if (L.r[i].key<L.r[i-1].key)
{
// "<" ， L.r[i]
L.r[0] = L.r[i]; //
for (j=i-1; L.r[0].key<L.r[j].key; --j)
L.r[j+1] = L.r[j]; //
L.r[j+1] = L.r[0]; //
}
}
/*
10000 。
1 。 。 。
*/
SqList random()
{
SqList s;
s.length=10000;
int i,j;
srand((int)time(0));
for(i=0;i<10000;i++)
{
j=1+(int)(1000.0*rand()/(RAND_MAX+1.0));
s.r[i].key=j;
}
return s;
}
/*************************************** main *************************************/
int main()
{
SqList s1;
s1.length=10000;
clock_t start,end;
//
s1 = random();
start = clock();
QuickSort(s1,1,s1.length);
end = clock();
printf( " 1 %lf
", (double)(end-start)/CLOCKS_PER_SEC);
//
s1 = random();
start = clock();
SelectSort(s1);
end = clock();
printf(" 1 %lf
", (double)(end-start)/CLOCKS_PER_SEC);
//
s1 = random();
start = clock();
InsertSort(s1);
end = clock();
printf(" 1 %lf
", (double)(end-start)/CLOCKS_PER_SEC);
system("PAUSE");
return 0;
}