数据结构课设 排序算法比较

/*6、排序算法比较 （必做）

设计要求：利用随机函数产生n个随机整数（n = 500，1000，1500，2500，30000），利用直接插入排序、折半插入排序，起泡排序、快速排序、选择排序堆排序，基数排序七种排序方法。

可添加其它排序方法）进行排序（结果为由小到大的顺序），并统计每一种排序所耗费的时间。

/各个函数均排成非递减。

#include<

#include<

#include<

#include<

#define maxn 100005

#define radix 10//关键字基数。

#define max_key 8//关键字项数最大值。

typedef struct

int keys[max_key];

int next;

slcell;

typedef struct

slcell r[maxn];

int keynum;//记录当前关键字个数。

int recnum;//静态链表当前长度。

slist;

int f[radix],e[radix];

int list[maxn];

int text[5] =

/冒泡排序。

void exchange(int &a,int &b)

int c;

c = a;

a = b;

b = c;

void bubble_sort(int length)

int i,j;

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

if(list[j]

exchange(list[i],list[j]);

/简单选择排序。

void selection_sort(int length)

int i,j,temp;

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

temp = i;

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

if(list[j]

temp = j;

if(i !=temp)

exchange(list[i],list[temp]);

/插入排序。

void insertion_sort(int length)

int i,j;

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

if(list[i]

list[0] =list[i];

list[i] =list[i-1];

for(j = i-2;list[0]

list[j+1] =list[j];

list[j] =list[0];

/折半插入排序。

void binsertion_sort(int length)

int i,j,low,high,mid;

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

list[0] =list[i];

low = 1;

high = i-1;

while(low < high)

mid = low + high)/2;

if(list[0]

high = mid-1;

elselow = mid+1;

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

list[j+1] =list[j];

list[j] =list[0];

/快速排序。

int partition(int low,int high)

int pivotkey;//枢轴记录关键字。

list[0] =list[low];

pivotkey = list[low];

while(low < high)

while(low < high &&list[high] >pivotkey)

high--;

list[low] =list[high];

while(low < high &&list[low]

low++;

list[high] =list[low];

list[low] =list[0];

return low;

void quick_sort(int low,int high)

int pivotloc;

if(low < high)//长度大于1

pivotloc = partition(low,high);

quick_sort(low,pivotloc - 1);

quick_sort(pivotloc +1,high);

堆排序。void heapadjust(int s,int m)

int j,rc;

rc = list[s];

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

if(j < m &&list[j]

j++;if(rc >=list[j])

break;

list[s] =list[j];

s = j;

list[s] =rc;

void heap_sort(int length)

int i;

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

heapadjust(i,length);

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

exchange(list[1],list[i]);

heapadjust(1,i-1基数排序。

void distribute(slist &l,int i)

int j;

int p;

for(j=0; j 0)

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

j = i;

tmp = list[i];

while((j >=k) &list[j - k] >tmp))

list[j] =list[j-k];

j -=k;

list[j] =tmp;

if(k ==2)

k = 1;

else k = int)(k/2.2int mi(int a)//返回10的a+1次方。

int i,b=1;

for(i=0; ilist[i] =rand();

start = clock();

binsertion_sort(text[times]);

end = clock();

duration = double)(end-start)/clocks_per_sec;

printf("折半插入排序：%lf",duration);

for(i=1; i<=text[times]; ilist[i] =rand();

start = clock();

insertion_sort(text[times]);

end = clock();

duration = double)(end-start)/clocks_per_sec;

printf("插入排序：%lf",duration);

for(i=1; i<=text[times]; ilist[i] =rand();

start = clock();

heap_sort(text[times]);

end = clock();

duration = double)(end-start)/clocks_per_sec;

printf("堆排序：%lf",duration);

for(i=1; i<=text[times]; ilist[i] =rand();

start = clock();

quick_sort(1,text[times]);

end = clock();

duration = double)(end-start)/clocks_per_sec;

printf("快速排序：%lf",duration);

for(i=1; i<=text[times]; ilist[i] =rand();

start = clock();

xsort(text[times]);

end = clock();

duration = double)(end-start)/clocks_per_sec;

printf("希尔排序：%lf",duration);

printf("");

/for(i=1; i<=text[times]; i++)

/ printf("%d,",list[i]);

/printf("");

return 0int main()

int a[max_key];

int mid;

int i,j,use;

clock_t start,end;

double duration;

/slist fxw;

for(int m = 0;m < 1;m++)

for(i = 1;i <=text[m];i++)

list[i] =rand();

mid = list[i];

= text[m];

for(j=0; j

if(j ==0)

= mid%10;

continue;

mid = mid%(mi(j+1));

mid = mid/(mi(j));

= midstart = clock();

radix_sort(fxw);

end = clock();

duration = double)(end-start)/clocks_per_sec;

printf("基数排序：%lf",duration);

for(i=1; i<=text[m]; i++)

printf("%d,",list[i

数据结构内部排序算法比较

目录。摘要 1 1绪论 12系统分析 1 2.1 功能需求 1 2.2数据需求 1 2.3 性能需求 2 3总体设计 2 3.1系统设计方案 2 3.2功能模块设计 2 4详细设计 3 4.1 数据结构定义 3 4.2伪随机产生数据模块 4 4.3简单选择排序模块 6 4.4起泡排序模块 7 4.5...

数据结构中各种排序算法比较

1快速排序 quicksort 快速排序是一个就地排序，分而治之，大规模递归的算法。从本质上来说，它是归并排序的就地版本。快速排序可以由下面四步组成。1 如果不多于1个数据，直接返回。2 一般选择序列最左边的值作为支点数据。3 将序列分成2部分，一部分都大于支点数据，另外一部分都小于支点数据。4 对...

数据结构内部排序比较分析

数据结构实训报告。实验名称 数据结构。题目 内部排序比较。专业班级 姓名 学号 实验日期 一 实验目的 通过随机数据比较各内部排序算法的关键字比较次数和关键字移动的次数，以取得直观感受。训练学生综合设计算法能力。二 实验要求 待排序长度不小于100，数据可有随机函数产生，用五组不同输入数据做比较，比...