|
|
马上注册，结交更多好友，享用更多功能^_^
您需要 登录 才可以下载或查看，没有账号？立即注册
x
#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[n], b[n] = {5, 2, 6, 0, 3, 9, 1, 7, 4, 8};
// int a[n], b[n] = {1, 0, 2, 3, 4, 5, 6, 7, 8, 9};
// int a[n], b[n] = {0, 1, 2, 3, 4, 9, 6, 7, 8, 5};
// int a[n], b[n] = {9, 0, 1, 2, 3, 4, 5, 6, 7, 8};
// int a[n], b[n] = {12, 18, 42, 44, 45, 67, 94, 10};
// int a[n], b[n] = {94, 10, 12, 18, 42, 44, 45, 67};
// int a[n], b[n] = {44, 45, 67, 94, 10};
// int a[n], b[n] = {44, 10, 45, 67, 94};
// int a[n], b[n] = {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[i]);
}
//轻的气泡上浮
for ( i = 0; i < n - 1; i++ )
{
count1++;
for ( j = n - 1; j > i; j-- ) //由下往上扫描
{
count2++;
if ( a[j] < a[j-1] )
{
count3++;
temp = a[j];
a[j] = a[j-1];
a[j-1] = temp;
}
}
}
/*
//重的气泡下沉
for ( i = n-1; i >= 1; i-- )
{
count1++;
for ( j = 0; j < i ; j++ ) //由上往下扫描
{
count2++;
if ( a[j] > a[j+1] )
{
count3++;
temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
}
}
}
*/
printf("\n排序后: \n");
for ( i = 0; i < n; i++ )
{
printf("%d ", a[i]);
}
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[i]);
}
for ( i = 0; i < n - 1; i++ )
{
count1++;
exchange = 0; //本趟排序开始前, 交换标志置为0
for ( j = n - 1; j > i; j-- ) //由下往上扫描
{
count2++;
if ( a[j] < a[j-1] )
{
count3++;
temp = a[j];
a[j] = a[j-1];
a[j-1] = temp;
exchange = 1; //发生了交换, 故将交换标志置为1
}
}
if ( !exchange ) //本趟排序未发生交换, 提前终止算法
{
count1--;
break;
}
}
printf("\n排序后: \n");
for ( i = 0; i < n; i++ )
{
printf("%d ", a[i]);
}
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[j]);
}
while ( i < n-1 )
{
count1++;
exchange = 0;
lastExchange = n - 1;
for ( j = n-1; j > i; j-- ) //由下往上扫描
{
count2++;
if ( a[j] < a[j-1] )
{
count3++;
temp = a[j];
a[j] = a[j-1];
a[j-1] = temp;
exchange = 1;
lastExchange = j;
}
}
if ( !exchange )
{
count1--;
}
i = lastExchange; //将i置为最后交换的位置
}
printf("\n排序后: \n");
for ( i = 0; i < n; i++ )
{
printf("%d ", a[i]);
}
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]);
}
i = 0;
j = n - 1;
exchange = 1;
while ( ( i < j ) && exchange )
{
count1++;
k = i++;
exchange = 0;
while ( k < j )
{
count2++;
if ( a[k] > a[k+1] )
{
count3++;
temp = a[k];
a[k] = a[k+1];
a[k+1] = temp;
exchange = 1;
}
k++;
}
if ( exchange )
{
k = --j;
while ( k >= i )
{
count2++;
if ( a[k] < a[k-1] )
{
count3++;
temp = a[k];
a[k] = a[k-1];
a[k-1] = temp;
exchange = 1;
}
k--;
}
}
if ( !exchange )
{
count1--;
}
}
printf("\n排序后: \n");
for ( i = 0; i < n; i++ )
{
printf("%d ", a[i]);
}
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[i]);
}
while ( exchange )
{
count1++;
k = lastExchange1;
exchange = 0;
while ( k < lastExchange2 ) //由上往下扫描
{
count2++;
if ( a[k] > a[k+1] )
{
count3++;
temp = a[k];
a[k] = a[k+1];
a[k+1] = temp;
exchange = 1;
lastExchange = k;
}
k++;
}
if ( exchange )
{
lastExchange2 = lastExchange;
k = lastExchange2;
while ( k > lastExchange1 ) //由下往上扫描
{
count2++;
if ( a[k] < a[k-1] )
{
count3++;
temp = a[k];
a[k] = a[k-1];
a[k-1] = temp;
exchange = 1;
lastExchange = k;
}
k--;
}
lastExchange1 = lastExchange;
}
else
{
count1--;
}
}
printf("\n排序后: \n");
for ( i = 0; i < n; i++ )
{
printf("%d ", a[i]);
}
printf("\ntwo_dir_BubberSort: 总共进行了%d趟排序, 进行了%d次比较, 进行了%d次移动!\n", count1, count2, count3);
} |
|
( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)
狗仔卡
发表于 2015-3-27 16:51:31
置顶卡
千斤顶
显身卡