2.起泡排察配知序的基本算法
3.template<classT>
4.voidBubbleSort(T arr[],intn){
5.起泡排序的时间复杂度分析 起泡排序算法中,第i趟起泡需卖山要执行n-i次比较和交换 *** 作。因此,i从1到n-1,执行的比较 *** 作的败消次数为: (n-1)+(n-2)+ …...
冒泡法我是这样理解的，便于掌握和记忆。首先冒泡是n长度的数组开始的两位开侍皮洞始，逐位双双比较一直到最后两个，所以最外循环比较了n-1次。第一个数比较了以后就不比了，从第二个开始，一直比较到数组末尾，于是内循环的起始位置不同，每次都是外侧i的值加0，也就是i。但结束老枯的限制和外握芹层循环是相同的。于是写法为for (i=0i<n-1i++){
for(j=ij<n-1j++)
//有多种排序法。你看一下#include <stdio.h>#include <stdlib.h>
#include <time.h>
#define MAXSIZE 200000typedef int keytype
typedef struct
{
keytype key
}recordtypetypedef struct
{
recordtype r[MAXSIZE + 1]
int length
}table/**************************************************************/
/* 二 分 法 插 入 排 序 算 法*/
/**************************************************************/
void binarysort(table *tab)
{
FILE *fa
fa = fopen("二分法插入排序.txt","w")
int i,j,left,right,mid
for (i = 2i <= tab->lengthi++) //依次插入从第2个开始的所有元素
{
tab->r[0].key = tab->r[i].key //保存待插入的元素
left = 1
right = i - 1
while (left <= right)//查找第i个元素的插入位置
{
mid = (left + right)/2 //取中间位置
if (tab->r[i].key <tab->r[mid].key)
right = mid - 1
else
left = mid + 1
} //弯弯插入位置为left
for (j = i - 1j >= leftj--)
tab->r[j + 1].key = tab->r[j].key //后移、空出埋洞闷插入位置
tab->r[left].key = tab->r[0].key //插入第i个元素的副本
}
fprintf(fa,"经过二分法插入排序之后的结果为: \n")
for( i = 1i <= tab->lengthi++)
fprintf(fa,"%d ",tab->r[i].key)
fclose(fa)
}/**************************************************************/
/* 冒 泡 排 序 算 */
/**************************************************************/
void bubblesort(table *tab)
{
FILE *fb
fb = fopen("冒泡排序.txt","w")
int i,j,done
i = 1
done = 1
while(i <= tab->length &&done) //最多进行tab->length 次冒泡、如果没有发生交换则结束
{
done = 0
for (j = 1j <= tab->length - ij++)
if(tab->r[j + 1].key <tab->r[j].key)
{
tab->r[0].key = tab->r[j].key //以第0个元素颤猛作为中间单元进行交换
tab->r[j].key = tab->r[j + 1].key
tab->r[j + 1].key = tab->r[0].key
done = 1
}
i++
}
fprintf(fb,"\n经过冒泡排序之后的结果为: \n")
for( i = 1i <= tab->lengthi++)
fprintf(fb,"%d ",tab->r[i].key)
fclose(fb)
}/**************************************************************/
/* 快 速 排 序 算 法 */
/**************************************************************/
void quicksort(table *tab,int left,int right)
{
int i,j
if (left <right)
{
i = left
j = right
tab->r[0].key = tab->r[i].key //准备以本次最左边的元素值为标准进行划分、先保存其值
do
{
while(tab->r[j].key >tab->r[0].key &&i <j) //从右向左找第1个不小于标准值的位置j
j--
if (i <j)
{
tab->r[i].key = tab->r[j].key //将第j个元素置于左端并重置i
i++
}
while(tab->r[i].key = tab->r[0].key &&i <j) //从左向右找第1个不小于标准值的位置i
i++
if (i <j)
{
tab->r[j].key = tab->r[i].key //将第i个元素置于左端并重置j
j--
}
} while (i != j)
tab->r[i].key = tab->r[0].key//将标准值放入它的最终位置、本次划分结束
quicksort(tab,left,i - 1) //对标准值左边递归调用本函数
quicksort(tab,i + 1,right) //对标准值右边递归调用本函数
}
}/**************************************************************/
/*直 接 选 择 排 序 算 法 */
/**************************************************************/
void simpleselectsort(table *tab)
{
FILE *fc
fc = fopen("直接选择排序.txt","w")
int i,j,k
for (i = 1i <= tab->length -1i++)//每次选择一个最小的元素（的位置）、和第i个元素交换
{
k = i//记下当前最小元素的位置
for (j = i + 1j <= tab->lengthj++) //向右查找更小的元素
if (tab->r[j].key <tab->r[k].key) //修改当前最小元素的位置
k = j
if (k != i) /*如果第i次选到的最小元素位置k不等于i、则将第k、i个元素交换*/
{
tab->r[0].key = tab->r[k].key //以没有用到的第0个元素作为中间单元进行交换
tab->r[k].key = tab->r[i].key
tab->r[i].key = tab->r[0].key
}
}
fprintf(fc,"\n经过直接选择排序之后的结果为: \n")
for( i = 1i <= tab->lengthi++)
fprintf(fc,"%d ",tab->r[i].key)
fclose(fc)
}/**************************************************************/
/* 堆 排 序 算 法 */
/**************************************************************/
void sift(table *tab,int k,int m)
{
int i,j,finished
i = k
j = 2 * i
tab->r[0].key = tab->r[k].key
finished = 0
while ((j <= m) &&(!finished))
{
if((j <m) &&(tab->r[j + 1].key <tab->r[j].key))
j++
if(tab->r[0].key <= tab->r[j].key)
finished = 1
else
{
tab->r[i].key = tab->r[j].key
i = j
j = 2 * j
}
}
tab->r[i].key = tab->r[0].key
}
void heapsort(table *tab)
{
FILE *fd
fd = fopen("堆排序.txt","w")
int i
for (i = tab->length/2i >= 1i--)
sift(tab,i,tab->length) //对所有元素建堆
for (i = tab->lengthi >= 2i--) //i表示当前堆的大小、即等待排序的元素的个数
{
tab->r[0].key = tab->r[i].key
tab->r[i].key = tab->r[1].key
tab->r[1].key = tab->r[0].key /*上述3条语句为将堆中最小元素和最后一个元素交换*/
sift(tab,1,i - 1)
}
fprintf(fd,"\n经过堆排序之后的结果为: \n")
for( i = 1i <= tab->lengthi++)
fprintf(fd,"%d ",tab->r[i].key)
fclose(fd)
}
/**************************************************************/
/* 归 并 排 序 算 法 */
/**************************************************************/
void merge(table *tabs,table *tabg,int u,int m,int v)
{
int i,j,k,t
i = u
j = m + 1
k = u
while(i <= m &&j <= v)
{
if (tabs->r[i].key <= tabs->r[j].key)
{
tabg->r[k].key = tabs->r[i].key
i++
}
else
{
tabg->r[k].key = tabs->r[j].key
j++
}
k++
}
if(i <= m)
for(t = it <= mt++)
tabg->r[k + t - i].key = tabs->r[t].key
else
for(t = jt <= vt++)
tabg->r[k + t - j].key = tabs->r[t].key}
void mergepass(table *tabs, table *tabg, int len)
{
int i,j,n
n = tabg->length = tabs->length
i = 1
while(i <= n - 2 * len + 1)
{
merge(tabs,tabg,i,i + len - 1,i + 2 * len - 1)
i = i + 2 * len
}
if (i + len - 1 <n)
merge(tabs,tabg,i,i + len - 1,n)
else
for(j = ij <= nj++)
tabg->r[j].key = tabs->r[j].key
}
void mergesort(table *tab)
{
FILE *fe
fe = fopen("归并排序.txt","w")
int len,i
table temp //中间变量
len = 1 //初始时有序段的长度为1
while (len <tab->length) //有序段的长度小于待排序元素的个数、继续归并
{
mergepass(tab,&temp,len)//一趟归并、结果在temp中
len = 2 * len
mergepass(&temp,tab,len)//一趟归并、结果在tab中
len = 2 * len
}
fprintf(fe,"\n经过归并排序之后的结果为: \n")
for( i = 1i <= tab->lengthi++)
fprintf(fe,"%d ",tab->r[i].key)
}
double max(double x,double y)
{
double z
z =(x>y)?x:y
return z
}
/**************************************************************/
/* 主 函 数 */
/**************************************************************/
void main()
{
printf("\n\n\n\n")
printf(" /**********************************************************/\n")
printf(" /*****************本程序使用了二分法插入排序***************/\n")
printf(" /****冒泡排序、快速排序、直接选择排序、堆排序、归并排序****/\n")
printf(" /**************运用六种方法找出三种较快的方法**************/\n")
printf(" /***************结果已经保存在各文件的.txt中***************/\n")
printf(" /**********************************************************/\n")
int i
double max1,max2,max3
table tab
FILE *fs
fs = fopen("快速排序及其各种排序的速度.txt","w")srand(10)
for(i = 1i <= MAXSIZEi++)
tab.r[i].key = rand() + 2000
tab.length = MAXSIZE
clock_t start, finish
double duration[6]
start = clock()
binarysort(&tab)
finish = clock()
duration[0] = (double)(finish - start) / CLOCKS_PER_SEC
printf( "二分法插入排序所花费的时间 %f seconds：\n ", duration[0])
start = clock()
bubblesort(&tab)
finish = clock()
duration[1] = (double)(finish - start) / CLOCKS_PER_SEC
printf( "冒泡排序所花费的时间 %f seconds：\n ", duration[1])
fprintf(fs,"\n经过快速排序之后的结果为: \n")
for( i = 1i <= tab.lengthi++)
fprintf(fs,"%d ",tab.r[i].key)
start = clock()
quicksort(&tab,1,10)
finish = clock()
duration[2] = (double)(finish - start) / CLOCKS_PER_SEC
printf( "快速排序所花费的时间 %f seconds：\n ", duration[2])
start = clock()
simpleselectsort(&tab)
finish = clock()
duration[3] = (double)(finish - start) / CLOCKS_PER_SEC
printf( "直接选择排序所花费的时间 %f seconds：\n ", duration[3])
start = clock()
heapsort(&tab)
finish = clock()
duration[4] = (double)(finish - start) / CLOCKS_PER_SEC
printf( "堆排序所花费的时间 %f seconds：\n ", duration[4])
start = clock()
mergesort(&tab)
finish = clock()
duration[5] = (double)(finish - start) / CLOCKS_PER_SEC
printf( "归并排序所花费的时间 %f seconds：\n ", duration[5])
fprintf( fs,"\n\n 二分法插入排序所花费的时间 %f seconds：\n ", duration[0])
fprintf( fs,"冒泡排序所花费的时间 %f seconds：\n ", duration[1])
fprintf( fs,"快速排序所花费的时间 %f seconds：\n ", duration[2])
fprintf( fs,"直接选择排序所花费的时间 %f seconds：\n ", duration[3])
fprintf( fs,"堆排序所花费的时间 %f seconds：\n ", duration[4])
fprintf( fs,"归并排序所花费的时间 %f seconds：\n ", duration[5])
max1 = max(duration[0],duration[1])
max2 = max(duration[2],duration[3])
max3 = max(duration[4],duration[5])printf("\n\n\n")
printf(" /**********************************************************/\n")
if(max1 == duration[0])
printf(" /***********************冒泡排序排序快*********************/\n")
else
printf(" /**********************二分法插入排序快********************/\n")
if(max2 == duration[2])
printf(" /***********************直接选择排序快*********************/\n")
else
printf(" /*************************快速排序快***********************/\n")
if(max3 == duration[4])
printf(" /*************************归并排序快***********************/\n")
else
printf(" /************************堆排序排序快**********************/\n")
printf(" /**********************************************************/\n")fclose(fs) //system("pause")}
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）