Bubble排序算法的优化
#include <stdio.h>#include <string.h>
#define n 10
void unoptimized_BubbleSort(int a[]);
void BubbleSort(int a[]);
void optimized_BubbleSort(int a[]);
void two_dir_BubberSort(int a[]);
int main()
{
int a, b = {5, 2, 6, 0, 3, 9, 1, 7, 4, 8};
// int a, b = {1, 0, 2, 3, 4, 5, 6, 7, 8, 9};
// int a, b = {0, 1, 2, 3, 4, 9, 6, 7, 8, 5};
// int a, b = {9, 0, 1, 2, 3, 4, 5, 6, 7, 8};
// int a, b = {12, 18, 42, 44, 45, 67, 94, 10};
// int a, b = {94, 10, 12, 18, 42, 44, 45, 67};
// int a, b = {44, 45, 67, 94, 10};
// int a, b = {44, 10, 45, 67, 94};
// int a, b = {8, 7, 6, 5, 4};
memcpy(a, b, n*sizeof(int));
unoptimized_BubbleSort(a);
memcpy(a, b, n*sizeof(int));
BubbleSort(a);
memcpy(a, b, n*sizeof(int));
optimized_BubbleSort(a);
memcpy(a, b, n*sizeof(int));
two_dir_BubberSort(a);
putchar('\n');
return 0;
}
//未优化的单向冒泡排序算法
void unoptimized_BubbleSort(int a[])
{
int i, j, temp, count1 = 0, count2 = 0, count3 = 0;
printf("排序前: \n");
for ( i = 0; i < n; i++ )
{
printf("%d ", a);
}
//轻的气泡上浮
for ( i = 0; i < n - 1; i++ )
{
count1++;
for ( j = n - 1; j > i; j-- )//由下往上扫描
{
count2++;
if ( a < a )
{
count3++;
temp = a;
a = a;
a = temp;
}
}
}
/*
//重的气泡下沉
for ( i = n-1; i >= 1; i-- )
{
count1++;
for ( j = 0; j < i ; j++ )//由上往下扫描
{
count2++;
if ( a > a )
{
count3++;
temp = a;
a = a;
a = temp;
}
}
}
*/
printf("\n排序后: \n");
for ( i = 0; i < n; i++ )
{
printf("%d ", a);
}
printf("\nunoptimized_BubbleSort: 总共进行了%d趟排序, 进行了%d次比较, 进行了%d次移动!\n", count1, count2, count3);
}
//由下往上扫描的冒泡排序算法
void BubbleSort(int a[])
{
int i, j, temp, count1 = 0, count2 = 0, count3 = 0, exchange;
printf("\n排序前: \n");
for ( i = 0; i < n; i++ )
{
printf("%d ", a);
}
for ( i = 0; i < n - 1; i++ )
{
count1++;
exchange = 0;//本趟排序开始前, 交换标志置为0
for ( j = n - 1; j > i; j-- )//由下往上扫描
{
count2++;
if ( a < a )
{
count3++;
temp = a;
a = a;
a = temp;
exchange = 1;//发生了交换, 故将交换标志置为1
}
}
if ( !exchange )//本趟排序未发生交换, 提前终止算法
{
count1--;
break;
}
}
printf("\n排序后: \n");
for ( i = 0; i < n; i++ )
{
printf("%d ", a);
}
printf("\nBubbleSort: 总共进行了%d趟排序, 进行了%d次比较, 进行了%d次移动!\n", count1, count2, count3);
}
//优化后的单向冒泡排序
void optimized_BubbleSort(int a[])
{
//采用lastExchange来记录每趟扫描中进行交换的最后一个元素位置,
//并以lastExchange作为下一趟排序循环终止的控制值
int i = 0, j, temp, exchange = 1, lastExchange, count1 = 0, count2 = 0, count3 = 0;
printf("\n排序前: \n");
for ( j = 0; j < n; j++ )
{
printf("%d ", a);
}
while ( i < n-1 )
{
count1++;
exchange = 0;
lastExchange = n - 1;
for ( j = n-1; j > i; j-- )//由下往上扫描
{
count2++;
if ( a < a )
{
count3++;
temp = a;
a = a;
a = temp;
exchange = 1;
lastExchange = j;
}
}
if ( !exchange )
{
count1--;
}
i = lastExchange;//将i置为最后交换的位置
}
printf("\n排序后: \n");
for ( i = 0; i < n; i++ )
{
printf("%d ", a);
}
printf("\noptimized_BubbleSort: 总共进行了%d趟排序, 进行了%d次比较, 进行了%d次移动!\n", count1, count2, count3);
}
/*void two_dir_BubberSort(int a[])
{
int i, j, k, temp, count1 = 0, count2 = 0, count3 = 0, exchange;
printf("\n排序前: \n");
for ( i = 0; i < n; i++ )
{
printf("%d ", a);
}
i = 0;
j = n - 1;
exchange = 1;
while ( ( i < j ) && exchange )
{
count1++;
k = i++;
exchange = 0;
while ( k < j )
{
count2++;
if ( a > a )
{
count3++;
temp = a;
a = a;
a = temp;
exchange = 1;
}
k++;
}
if ( exchange )
{
k = --j;
while ( k >= i )
{
count2++;
if ( a < a )
{
count3++;
temp = a;
a = a;
a = temp;
exchange = 1;
}
k--;
}
}
if ( !exchange )
{
count1--;
}
}
printf("\n排序后: \n");
for ( i = 0; i < n; i++ )
{
printf("%d ", a);
}
printf("\ntwo_dir_BubberSort: 总共进行了%d趟排序, 进行了%d次比较, 进行了%d次移动!\n", count1, count2, count3);
}*/
//双向冒泡排序算法, 在排序过程中交替改变扫描方向
void two_dir_BubberSort(int a[])
{
int i, k, temp, count1 = 0, count2 = 0, count3 = 0;
int exchange = 1, lastExchange, lastExchange1 = 0, lastExchange2 = n-1;
printf("\n排序前: \n");
for ( i = 0; i < n; i++ )
{
printf("%d ", a);
}
while ( exchange )
{
count1++;
k = lastExchange1;
exchange = 0;
while ( k < lastExchange2 )//由上往下扫描
{
count2++;
if ( a > a )
{
count3++;
temp = a;
a = a;
a = temp;
exchange = 1;
lastExchange = k;
}
k++;
}
if ( exchange )
{
lastExchange2 = lastExchange;
k = lastExchange2;
while ( k > lastExchange1 )//由下往上扫描
{
count2++;
if ( a < a )
{
count3++;
temp = a;
a = a;
a = temp;
exchange = 1;
lastExchange = k;
}
k--;
}
lastExchange1 = lastExchange;
}
else
{
count1--;
}
}
printf("\n排序后: \n");
for ( i = 0; i < n; i++ )
{
printf("%d ", a);
}
printf("\ntwo_dir_BubberSort: 总共进行了%d趟排序, 进行了%d次比较, 进行了%d次移动!\n", count1, count2, count3);
} 看看。。。。。。 顶一个
页:
[1]