欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

小甲鱼 排序算法 冒泡排序

程序员文章站 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;
}

 

相关标签: 冒泡排序