排序类算法(堆排,快排,铜排,插入排)汇总分析

时间：2026-01-14

插入排序

一：实验描述：

用插入排序的思想对大量的数据（实数）进行排序，粗略计算出主算法运行时间。二：实验思路：

插入排序是将数组中的元素一个一个的插入一个有序序列中，当最后一个数组元素插入完成后，即实现了所有元素的排序。重要的是插入时的插入位置的寻找，为了节省时间，可以采用折半查找的方法进行。

三：实验复杂度的分析：

实验复杂度为O(n的平方)

四：实验代码：

#include<stdio.h>

#include<stdlib.h>

#include<time.h>

#define N 10000

float a[N];

int Binarysearch(int j,float x)

{

int high,low,mid;

low=0;high=j;

while(low<high){

mid=(low+high)/2;

if(a[mid]<=x)low=mid+1;

if(a[mid]>x)high=mid;

}

if(a[high]>x)return high;

else return high+1;

}

void InsSort()

{

int i,j,num;

float x;

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

{

x=a[i];j=i-1;

num=Binarysearch(j,x);

while(j>num)

{

a[j+1]=a[j];

j--;

}

a[j]=x;

}

int main()

{

int i;clock_t tb,te;

srand((unsigned)time(NULL));

for(i=0;i<N;i++){

a[i]=(float)(rand()%30000+0.01);

printf("%.2f ",a[i]);

}

printf("\n");

tb=clock();

InsSort();

te=clock();

for(i=0;i<N;i++)

printf("%.2f ",a[i]);

printf("\n");

printf("此程序主要算法运行时间：%.2fms\n",(float)(te-tb));

return 0;

}

五：实验结果：

从实验结果运行时间可知主算法排序10000个随机实数的时间：

136ms

堆排序：

一：实验描述：

用堆排序的思想对大量的数据（实数）进行排序，粗略计算出主算法运行时间。二：实验思路：

堆排序巧妙地运用了二叉树的左孩子的数组下标是父亲结点的数组下标的的二倍，最后一个二叉树非终端结点是数组的【n/2】个元素，从此元素开始，一直到第一个元素逐步建立小顶堆，堆建立完后输出堆顶（最后一个元素与堆顶元素交换），然后继续建立大顶堆…直到所有的元素输出完。

三：实验复杂度的分析：

N个结点的完全儿二叉树的深度为[log2n]+1,建立大顶推的时候比较次数不超过4n次，调整新堆时，比较次数：2（log2(n-1)+log2(n-2)+…+log22）<2nlog2n;堆排序的时间复杂度为： O（nlogn）。

四：实验代码：

#include <stdio.h>

#include<time.h>

#include<stdlib.h>

#define MAX 10000

float a[MAX];

void HeadAdjust(int s,int m)

{

int j;

float rc;

rc=a[s];

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

{

if(j==m&&rc>=a[j])break;

if(j<m){

if(a[j]<a[j+1]&&rc<a[j+1])j++;

if(rc>=a[j]&&rc>=a[j+1])break;

}

a[s]=a[j];s=j;

}

a[s]=rc;

}

void main()

{

int i,N;clock_t tb,te;

srand((unsigned)time(NULL));//初始化随机种子

printf("请输入数字的个数：");

scanf("%d",&N);

printf("生成的原始数据为：\n");

for(i=1;i<=N;i++){

a[i]=(rand()%30000+0.01);

printf("%.2f ",a[i]);

}

printf("\n");

tb=clock();

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

HeadAdjust(i,N);

for(i=N;i>1;i--){

a[0]=a[1];

a[1]=a[i];

a[i]=a[0];

HeadAdjust(1,i-1);

}

te=clock();

printf("排序后：\n");

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

printf("%.2f ",a[i]);

printf("\n");

printf("此程序主要算法运行时间：%.2fms\n",(float)(te-tb));

}

五：实验结果：

从实验结果运行时间可知主算法排序10000个随机实数的时间：

3ms

桶排序

一：实验描述：

用堆排序的思想对大量的数据进行排序，粗略计算出主算法运行时间。

二：实验思路：

基数排序是根据关键字把所给的数据穿在不同的串中，比如10000个五位随机数的排序，可将个位按0,1,2,3,4,5,6,7,8,9穿在不同的串中，然后按顺序继续连成数组或链表，然后按十位上的数字按0,1,2,3,4,5,6,7,8,9重新穿在不同的串中，然后按顺序继续连成数组或链表。。。。按此方法直到万位穿起在不同的串中，这样按顺序得到的序列就是一个有序序列。三：实验复杂度：

数据的位数为r,则程序要比扫描r*n次才能得到有序序列，故时间复杂度为：O（rd）空间复杂度：链表建立数据序列，所需空间为n+n,即2n(其中包括指针的空间)。、四：实验代码：

#include<stdio.h>

#include<stdlib.h>

#include<time.h>

typedef struct node{int data;struct node *next;}NODE;

#define CreateNODE(p) p=(NODE *)malloc(sizeof(NODE));

#define DeleteNODE(p) free((void *)p);

int num=5;

void main()

{

NODE *h,*q,*p,*l,*first[11],*last[11];

int i,tep,k,N;clock_t tb,te;