小甲鱼 排序算法 冒泡排序
程序员文章站
2022-03-24 15:32:54
...
小甲鱼 排序算法 冒泡排序
冒泡排序
基本思想:两两相邻记录的关键字,如果反序则交换,直到没有反序的记录为止
(PS 反序:大在前,小在后)
下面的代码不是真正意义的冒泡排序(因为比较的不是相邻)
//BubbleSort冒泡排序
#include <stdio.h>
void BubbleSort(int k[], int n)
{
int i, j, temp;
//为什么n-1,因为排序到最后一个,最后一个已经是最大的,不需要再排序
for (i = 0; i < n-1; i++)
{
//j=i+1:下一个元素
for (j = i+1; j < n; j++)
{
//从小到大排序
if (k[i] > k[j])
{
temp = k[j];
k[j] = k[i];
k[i] = temp;
}
}
}
}
int main(void)
{
int i, a[10] = {5, 2, 6, 0, 3, 9, 1, 7, 4, 8};
BubbleSort(a, 10);
printf("排序后的结果是:");
for (i = 0; i < 10; i++)
{
printf("%d", a[i]);
}
printf("\n\n");
return 0;
}
冒泡排序的要点
1、两两注意是相邻的两个元素的意思。
2、如果有n个元素需要比较n-1次,每一轮减少1次比较。
3、既然叫冒泡排序,那就是从下往上两两比较,所以看上去就跟泡泡往上冒一样。
真正意义的冒泡算法
数组从最后面进行比较,每一次排序确定最小的排在前面
//BubbleSort冒泡排序
#include <stdio.h>
void BubbleSort(int k[], int n)
{
int i, j, temp, count1=0, count2=0;
for (i = 0; i < n-1; i++)
{
//为什么是n-1?
//每一次循环后确定的元素不在参与比较
//第一次确定第一大,第二次确定第二大
for (j = n-1; j > i; j--)
{
count1++;
//从小到大排序
if (k[j-1] > k[j])
{
count2++;
temp = k[j-1];
k[j-1] = k[j];
k[j] = temp;
}
}
}
printf("总共进行了%d次比较,进行了%d次移动!\n", count1, count2);
}
int main(void)
{
int i, a[10] = {5, 2, 6, 0, 3, 9, 1, 7, 4, 8};
BubbleSort(a, 10);
printf("排序后的结果是:");
for (i = 0; i < 10; i++)
{
printf("%d", a[i]);
}
printf("\n\n");
return 0;
}
优化冒泡排序算法
//BubbleSort冒泡排序
#include <stdio.h>
void BubbleSort(int k[], int n)
{
int i, j, temp, count1=0, count2=0, flag;
flag = 1;
for (i = 0; i < n-1 && flag; i++)
{
//为什么是n-1?
//每一次循环后确定的元素不在参与比较
//第一次确定第一大,第二次确定第二大
for (j = n-1; j > i; j--)
{
count1++;
flag = 0;//没有执行移动
//从小到大排序
if (k[j-1] > k[j])
{
count2++;
temp = k[j-1];
k[j-1] = k[j];
k[j] = temp;
flag = 1;
}
}
}
printf("总共进行了%d次比较,进行了%d次移动!\n", count1, count2);
}
int main(void)
{
int i, a[10] = {5, 2, 6, 0, 3, 9, 1, 7, 4, 8};
BubbleSort(a, 10);
printf("排序后的结果是:");
for (i = 0; i < 10; i++)
{
printf("%d", a[i]);
}
printf("\n\n");
return 0;
}
下一篇: 小甲鱼 排序算法 直接插入排序